Notice
Recent Posts
Recent Comments
Link
«   2025/07   »
일 월 화 수 목 금 토
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
Tags more
Archives
Today
Total
관리 메뉴

TIL

2021 06 01 (화) 본문

2021/일일 기록

2021 06 01 (화)

ililillllllliilli 2021. 6. 2. 13:41

20210601(화)


1. 학습 날짜 : 20210601(화)



2. 학습 시간 : 12:00 ~ 15:00, 15:40 ~ 22:00



3. 학습 주제 : push_swap 마무리, 프로그램 디버깅



4. 동료 학습 방법 : 개인



5. 학습 목표 : push_swap 마무리

  • 프로그램 디버깅 -> 프로그램 구동됨
  • 음수를 인자로 받을 수 있도록 변경
  • 명령어 개수 진단. 5/3 logn 의 명령어 개수를 사용하여 과제의 기준을 충족하는지?
  • push_swap Tester :




6. 학습 내용 :


프로그램 디버깅

어제 짜다 만

int **assign_piv_array_b(int **piv_arr, int *arr, int left, int right)
int **assign_piv_array_a(int **piv_arr, int *arr, int left, int right)

를 고치고 나서


프로그램을 돌렸는데, heap-buffer-overflow 에러가 났다.

일정 개수 이하일 때(35개)*는 프로그램이 정상 작동하고 정렬까지 잘 되지만, 특정 개수(35개)를* 넘어가면 프로그램이 heap-buffer-overflow 에 의해 죽는 문제가 발생한다.


heap-buffer-overflow 가 발생하는 이유 :

일단, 출력물로 로그파일을 만들어, 어디서 문제가 발생하는지 찾아보았다.

Heap-buffer-overflow는 일반적인 경우, 잘못된 배열 인덱스를 참조하거나 할 때 생기고, 아래 에러메시지를 보았을 때, create_pivot_array pivot_array.c:58 에서 에러 메시지가 나는 것으로 보아, pivot_array에서 잘못된 배열 인덱스를 참조했다고 추측했다.


==92877==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60b000000158 at pc 0x00010e39b059 bp 0x7ffee186a5d0 sp 0x7ffee186a5c8
READ of size 8 at 0x60b000000158 thread T0
    #0 0x10e39b058 in sort_a sort_a.c:73
    #1 0x10e39b639 in sort_a sort_a.c:97
    #2 0x10e39b639 in sort_a sort_a.c:97
    #3 0x10e39b639 in sort_a sort_a.c:97
    #4 0x10e39b639 in sort_a sort_a.c:97
    #5 0x10e39b639 in sort_a sort_a.c:97
    #6 0x10e39d422 in sort_b sort_b.c:98
    #7 0x10e39b6cc in sort_a sort_a.c:98
    #8 0x10e397ee1 in main main.c:41
    #9 0x7fff71859cc8 in start+0x0 (libdyld.dylib:x86_64+0x1acc8)

0x60b000000158 is located 0 bytes to the right of 104-byte region [0x60b0000000f0,0x60b000000158)
allocated by thread T0 here:
    #0 0x10e3f917d in wrap_malloc+0x9d (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x4917d)
    #1 0x10e39aad9 in create_pivot_array pivot_array.c:58
    #2 0x10e39a88a in init_piv_array pivot_array.c:115
    #3 0x10e397e49 in main main.c:34
    #4 0x7fff71859cc8 in start+0x0 (libdyld.dylib:x86_64+0x1acc8)

SUMMARY: AddressSanitizer: heap-buffer-overflow sort_a.c:73 in sort_a
Shadow bytes around the buggy address:
  0x1c15ffffffd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1c15ffffffe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1c15fffffff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1c1600000000: fa fa fa fa fa fa fa fa 00 00 00 00 00 00 00 00
  0x1c1600000010: 00 00 00 00 00 04 fa fa fa fa fa fa fa fa 00 00
=>0x1c1600000020: 00 00 00 00 00 00 00 00 00 00 00[fa]fa fa fa fa
  0x1c1600000030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c1600000040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c1600000050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c1600000060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c1600000070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==92877==ABORTING
zsh: abort      ./push_swap 24 16 12 8 7 6 46 18 26 31 25 10 11 19 22 50 48 42 33 9 5 49 37 3

혹시 pivot_array의 pivot과 분할정복시에 사용되는 sort_a(), sort_b()의 pivot 사용 순서가 다르기 때문에 생긴 에러는 아닐까... 해서

1 ~ 50까지의 공차가 1인 순열을 랜덤하게 뽑아 ./push_swap의 인자로 넣어준 후, pivot_array의 순서와 sorting 알고리즘의 pivot 사용 순서와 비교해봤다.

이 때, 확실히 에러가 생기는게 맞았다.


sorting 알고리즘의 피벗사용순서와 pivot_array의 피벗 사용 순서가 달랐기 때문에 생긴 문제엿다.

따라서, pivot_array의 sorting 알고리즘을 모방한 재귀함수

int **assign_piv_array_b(int **piv_arr, int *arr, int left, int right), int **assign_piv_array_a(int **piv_arr, int *arr, int left, int right), 의 재귀과정을 손봤고,

결과, 프로그램이 정상 작동했다.



프로그램 정상 작동 테스트

위에서 1 ~ 50 데이터셋을 사용해서 프로그램을 돌렸고, 더 랜덤하고, 정수의 개수를 달리한 뒤에 프로그램을 돌려, 프로그램의 정상작동을 확인해봤다.


1~50 셔플 데이터셋에서 오류가 났다.

void    sort_b_213(t_ll **ab_array)
{
    rev_ab(ab_array, STACK_B);
    swap_ab(ab_array, STACK_B);
    push_ab(ab_array, STACK_A);
    rrev_ab(ab_array, STACK_B);
    push_ab(ab_array, STACK_A);
    push_ab(ab_array, STACK_A);

    //push_ab(ab_array, STACK_B);
    //push_ab(ab_array, STACK_B);
}

아래 두 줄이 주석처럼 되어있어 오류가 났었다.

STACK_A에 옮겨줄것을 STACK_B로 옮겨주었기 때문에 문제가 생겼는데, 옮기는 위치를 바꾸는 실수를 고쳐주었더니 모든 에러가 잡혀보였다.



n = k일 때 프로그램 정상 작동 테스트 : 각각 약 5회

https://onlinenumbertools.com/generate-integers

온라인 난수 생성기.


데이터셋 수 (n) 1회 2회 3회 4회 5회
50 o o o o o
100 o o o o o
300
500
1000 o o o o o
1500
2000 o
4000 o o
5000 o o o
데이터 셋 수 (n) - 음수, 양수, 0 1회 2회 3회 4회 5회
50 - - - - -
1000 - - - - -
5000 - - - - -
- - - - -



음수를 인자로 받을 수 있도록 변경

static int    is_arg_digit(char *ch)
{
    while (*ch)
    {
        if (!ft_isdigit(*ch))
            return (0);
        ch++;
    }
    return (1);
}

위 함수는 임시로 만들어 놓았지만, 프로그램이 완성에 가까워지는 시점에서는 음수를 인자로 받을 수 있게 바꾸어주어야한다.

현재는 -123이 인자로 들어왔을 경우, return (0) 을 반환한다.

static int    is_arg_digit(char *ch)
{
  // 추가
  if (*ch == '-')
        ch++;
  // 추가 끝
    while (*ch)
    {
        if (!ft_isdigit(*ch))
            return (0);
        ch++;
    }
    return (1);
}

아래와 같은 줄 을 추가해주면, -123 을 인자로 받은 경우에 처리가 가능해지고, --123 , -12abc 를 받은 경우에도 처리가 가능해진다.

  if (*ch == '-')
        ch++;
    if (*ch == '-' && *(ch + 1) == '\0')
        return (0);

약간의 수정을 가해 위의 코드도 추가해서 - 만 인자로 들어온 경우, digit_checker 에 걸리도록 했다.



데이터 셋 (n) / instruction 수 (k) 1회 2회 3회 4회 5회
100 701 689 702 707 705
500 4664 4650 4650 4651 4656

  • 에러 처리
    • 매개변수가 숫자가 아닐 경우
    • 매개변수가 중복
    • 매개변수가 int 범위를 넘어감
    • 매개변수가 없을 때
  • Identity Test : 이미 정렬된 목록이 주어졌을 때 아무것도 표시하지 않기 :
    is_already_sorted 함수로 연결리스트 traverse하면서 확인해보기.
  • data set이 2 1 0일 때, instruction_count 가 2개 또는 3개여야함. :
    Data set이 3개 이하일 경우
  • 1 5 2 4 3의 data set의 instruction_count 가 13을 넘지 않아야 함
    • 48 167 75 -281 -670 : 3 5 4 2 1 의 데이터셋이 딱 13개 명령어를 배출함.
    • -585 56 -289 18 -711 : 2 4 3 5 1의 데이터셋이 딱 13개 명령어를 배출.
  • 불필요한 연산 수 (초기 push_a)를 줄이면 5개 일 때 경우가 해결된다고 들었다.
    • 정확히 어떻게 불필요한 연산 수를 줄이면 되는지에 대해서는 stack을 조작해주면서 따라해봐야할 것 같다.



불필요한 연산을 줄이는 방법 :

데이터 셋 (n) / instruction 수 (k) 1회 2회 3회 4회 5회
100 701 689 702 707 705

데이터셋 n = 5일 때 instruction_count < 13, 그리고 n = 100 일 때, instruction_count < 700이 되게 하는 방법 이 존재한다.


[1], [2]. [3]은 무작위로 섞여있는 정수들(or 데이터들)의 크기를 [1] <[2] < [3] 으로 가상으로 분류해놓음.

sort_a에서 일반적인 경우(귀납적으로) 아래 사진과 같은 과정을 거쳐서,
무작위로 섞여 들어온 input인 [1], [2], [3]의 data를 옮기는데, 맨 처음 sort_a를 통해 정렬하는 과정에서 불필요한 연산이 생긴다.


img


맨 처음 sort_a 가 불려지는 과정에서 스택 A에는 [1]. [2]. [3] 만 존재하는 상태이며, 스택 B는 비어있다.

이 상태에서 굳이 sort_a 의 연산 과정을 그대로 거칠 이유가 없다.

스택 A에는 [3]만 남겨야하는데, 스택 A는 이미 [3]이 top에 있기 때문에 굳이 ra 연산을 사용할 이유가 없고,

스택 B에는 [2]를 top으로 옮겨야하고, [1]을 top의 바로 아랫부분으로 옮겨주기만 하면 되므로,

sort_a 과정에서 [2]에 대해서 rb 후 rrb 연산을 해주어야 할 이유가 없다.

처음부터 [1]에 대해서 rb 연산만 해주면 초기상태에서의 정렬은 끝나기 때문이다.



따라서, sort_a_initial() 함수에서 instruction을 덜 사용하는 초기 데이터 정렬을 한 뒤에, 진짜 sort_a 함수와 sort_b함수를 사용하여
sorting을 하기로 한다.



Screen-Shot-2021-06-02-at-1-19-37-PM


def A_to_B(r)
    if r < 3
        적절히 정렬
        return
    스택A 원소 중에서 "적절한" 피봇을 2개 선택한다
    for r개의 원소에 대해서
        if (스택A의 top) >= 피봇[큰것]
            ra명령으로 뒤로 넘긴다
            ra호출횟수++
        else
            pb명령으로 b로 보낸다
            pb호출횟수++
            if (스택B의 top) >= 피봇 [작은것]
                rb명령으로 뒤로 넘긴다
                rb호출횟수++
    for ra호출횟수, rb호출횟수
        rrr호출 #[3]과 [2]를 스택 앞으로 가져온다
    A_to_B(ra호출 횟수) #[3]
    B_to_A(rb호출 횟수) #[2]
    B_to_A(pb호출 횟수 - rb 호출 횟수) #[1]



학습에 도움된 사이트 :



주제 사이트
랜덤 난수 생성기 https://onlinenumbertools.com/generate-integers

오늘 발견한 문제와 해결방안:

  • data set이 2 1 0일 때, instruction_count 가 2개 또는 3개여야 하는데, 그러지 못함.
    • dataset이 n ==3일 때는, 함수를 분리하여 따로 처리하도록 한다.
  • 1 5 2 4 3의 data set의 instruction_count 가 13을 넘지 않아야 함 :
    • 불필요한 연산을 줄이는 방법 에 설명했다.



7. 학습 총평 :


  • 프로그램을 어느정도 완성했다고 생각했는데, 생각지도 못한 곳에서 기준을 충족시키지 못했고, 주변 동료에게 질문하여 해결 방법을 물어봤는데,

    나는 왜 해결방법을 떠올리지 못했을까 생각해봤다.


    왜..?
    다른 동료는, 과정을 하나하나 다 따라해봤다고 했는데,
    나는 그렇지 않았고, 개념만 안 상태로, 코딩을 해봤다. 하나하나 다 따라해보면 하수라고 생각했는데, 실상은 그렇지 않았고,
    어느 정도는 하나하나 알고리즘의 과정을 밟아보는게 중요하지 않았나 싶다.


8. 다음 학습 계획 :

  • ​

  • data set이 2 1 0일 때, instruction_count 가 2개 또는 3개여야함. :
    Data set이 3개 이하일 경우

  • 1 5 2 4 3의 data set의 instruction_count 가 13을 넘지 않아야 함

    • 48 167 75 -281 -670 : 3 5 4 2 1 의 데이터셋이 딱 13개 명령어를 배출함.
    • -585 56 -289 18 -711 : 2 4 3 5 1의 데이터셋이 딱 13개 명령어를 배출.

  • 불필요한 연산 수 (초기 push_a)를 줄이면 5개 일 때 경우가 해결된다고 들었다.

    • 정확히 어떻게 불필요한 연산 수를 줄이면 되는지에 대해서는 stack을 조작해주면서 따라해봐야할 것 같다.

저작자표시 (새창열림)

'2021 > 일일 기록' 카테고리의 다른 글

2021 06 03 (목)  (0) 2021.06.05
2021 06 02(화)  (0) 2021.06.05
2021 05 31(월)  (0) 2021.06.01
2021 05 28 (금)  (0) 2021.05.31
2021 05 27 (목)  (0) 2021.05.28
'2021/일일 기록' Related Articles more
Comments

티스토리툴바