TIL
2021 06 01 (화) 본문
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를 통해 정렬하는 과정에서 불필요한 연산이 생긴다.
맨 처음 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을 하기로 한다.
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
일 때는, 함수를 분리하여 따로 처리하도록 한다.
- dataset이
- 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 |