fastbin과 smallbin의 fd와 bk

ptmalloc2는 총 128개의 bin을 가지고있고
이중
62개는 small bin
63개는 large bin
1개는 unsorted bin
2개는 사용하지 않는다는 것을보고

  1. fastbin은 물리적으로 smallbin의 32~128바이트 청크를 보관하는 인덱스에 해당하는 부분이라고 이해하였는데 이것이 맞나요? 아니면 별도로 fastbin을 위한 공간이 물리적으로 존재하나요?
  2. 강의 자료의 사진을 보면 small bin에는 chunk를 해제할때 fd와 bk 모두 기록이 되지만 fast bin에는 fd만 기록이 되는데, 이는 각각 이중 연결리스트 / 단일 연결리스트로 구현이 되기에 단일연결리스트인 fast bin은 뒷 청크에 대한 정보인 bk는 필요없다.. 라고 이해하였는데 맞나요?
#시스템해킹 #배경지식 #ptmalloc2
작성자 정보
답변 1
Karatus
워게임: 50

(A1) fastbin과 smallbin을 나누는 기준은 할당되는 청크의 사이즈입니다. 둘이 사이즈가 다르니 다른 종류의 청크입니다. 즉 smallbin의 인덱스 개념과는 무관합니다. 애초에 리스트 자료구조로 관리되는 bin에서는 배열 자료구조에서 쓰이는 인덱스라는 말과는 어울리지 않습니다.

(A2) fastbin은 특별히 작은 크기의 데이터를 보관할 때 재할당의 속도 퍼포먼스를 높이기 위해 존재하는 것이므로 head 포인터로만 바로 접근하면 되는 싱글 링크드 리스트 자료구조를 채택했습니다. 같은 말로 bk를 따로 두지 않는 것입니다. 더블 링크드 리스트 형태로 존재하는 smallbin은 아무래도 싱글 링크드 리스트보다는 접근할 때 오버헤드가 더 많이 들겠죠. 하지만 fastbin과는 달리 청크 크기의 범위가 좀 더 다양하므로 재할당을 위한 사이즈 서치 루틴과 사이즈별 재배치 루틴이 존재하고 그렇기 때문에 더블 링크드 리스트 형태를 띠고 있는 것입니다.

2022.02.10. 18:42
질문에 대한 답을 알고 계신가요?
지식을 나누고 포인트를 획득해보세요.
답변하고 포인트 받기