K&R 책에서 malloc의 이 구현에 대해 설명합니다.
이것은 커니헌과 리치의 C에 관한 책에서 발췌한 것입니다.의 버전을 구현하는 방법을 보여줍니다.malloc좋은 평을 받았지만, 저는 그것을 이해하는 데 큰 어려움을 겪고 있습니다.누가 설명 좀 해주시겠어요?
typedef long Align; /* for alignment to long boundary */
union header { /* block header */
struct {
union header *ptr; /* next block if on free list */
unsigned size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
};
typedef union header Header;
static Header base; /* empty list to get started */
static Header *freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void *malloc(unsigned nbytes)
{
Header *p, *prevp;
Header *morecore(unsigned);
unsigned nunits;
nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;
if ((prevp = freep) == NULL) { /* no free list yet */
base.s.ptr = freeptr = prevptr = &base;
base.s.size = 0;
}
for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
if (p->s.size >= nunits) { /* big enough */
if (p->s.size == nunits) /* exactly */
prevp->s.ptr = p->s.ptr;
else { /* allocate tail end */
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits
}
freep = prevp;
return (void *)(p+1);
}
if (p == freep) /* wrapped around free list */
if ((p = morecore(nunits)) == NULL)
return NULL; /* none left */
}
}
#define NALLOC 1024 /* minimum #units to request */
/* morecore: ask system for more memory */
static Header *morecore(unsigned nu)
{
char *cp, *sbrk(int);
Header *up;
if (nu < NALLOC)
nu = NALLOC;
cp = sbrk(nu * sizeof(Header));
if (cp == (char *) -1) /* no space at all */
return NULL;
up = (Header *) cp;
up->s.size = nu;
free((void *)(up+1));
return freep;
}
/* free: put block ap in free list */
void free(void *ap) {
Header *bp, *p;
bp = (Header *)ap - 1; /* point to block header */
for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
break; /* freed block at start or end of arena */
if (bp + bp->size == p->s.ptr) {
bp->s.size += p->s.ptr->s.size;
bp->s.ptr = p->s.ptr->s.ptr;
} else
bp->s.ptr = p->s.ptr;
if (p + p->size == bp) {
p->s.size += bp->s.size;
p->s.ptr = bp->s.ptr;
} else
p->s.ptr = bp;
freep = p;
}
자, 여기에 있는 것은 정말 엉망으로 쓰여진 코드 덩어리입니다.제가 이 게시물에서 할 일은 소프트웨어 고고학으로 가장 잘 설명될 수 있습니다.
1단계: 포맷을 수정합니다.
의도적이고 간결한 형식은 아무에게도 도움이 되지 않습니다.다양한 공백과 빈 행을 삽입해야 합니다.댓글은 좀 더 읽기 쉬운 방식으로 작성될 수 있습니다.제가 그걸 고치는 것부터 시작하겠습니다.
동시에 저는 K&R 스타일에서 브레이스 스타일을 바꾸고 있습니다. K&R 브레이스 스타일은 받아들일 수 있습니다. 이것은 저의 개인적인 취향일 뿐입니다.다른 개인적인 선호 사항은 가리키는 유형 옆에 포인터 *를 쓰는 것입니다.저는 여기서 (주관적인) 스타일 문제에 대해 논쟁하지 않겠습니다.
또한, 유정의 는 다음과 .Header완전히 읽을 수 없습니다. 근본적인 해결책이 필요합니다.
그리고 저는 완전히 알려지지 않은 것을 발견했습니다. 그들은 함수 내부에 함수 프로토타입을 선언한 것 같습니다.Header* morecore(unsigned);이것은 매우 오래되고 형편 없는 스타일이고, C가 더 이상 허용할지도 모르겠습니다.그 선을 제거해 봅시다. 그 기능이 무엇을 하든지 간에, 그것은 다른 곳에서 정의해야 합니다.
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
unsigned size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base; /* empty list to get started */
static Header* freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* malloc (unsigned nbytes)
{
Header* p;
Header* prevp;
unsigned nunits;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;
if ((prevp = freep) == NULL) /* no free list yet */
{
base.s.ptr = freeptr = prevptr = &base;
base.s.size = 0;
}
for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr)
{
if (p->s.size >= nunits) /* big enough */
{
if (p->s.size == nunits) /* exactly */
prevp->s.ptr = p->s.ptr;
else /* allocate tail end */
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits
}
freep = prevp;
return (void *)(p+1);
}
if (p == freep) /* wrapped around free list */
if ((p = morecore(nunits)) == NULL)
return NULL; /* none left */
}
}
자, 이제 코드를 읽을 수 있을지도 모릅니다.
2단계: 널리 알려진 나쁜 관행을 제거합니다.
이 코드는 요즘 나쁜 관행으로 간주되는 것들로 가득 차 있습니다.코드의 안전성, 가독성 및 유지관리를 위협하기 때문에 제거해야 합니다.만약 당신이 나와 같은 관행을 설교하는 권위자에 대한 언급을 원한다면, 널리 알려진 코딩 표준 MISRA-C를 확인하세요.
다음과 같은 잘못된 관행을 발견하고 제거했습니다.
냥그 기하입력을 입력합니다.unsigned코드에서 혼란을 초래할 수 있습니다: 이것은 프로그래머에 의한 오타입니까, 아니면 쓰려고 의도한 것입니까?unsigned int우리는 모든 것을 교체해야 합니다.unsigned와 함께unsigned int하지만 그렇게 함으로써, 우리는 그것이 다양한 이진 데이터의 크기를 제공하기 위해 이 맥락에서 사용된다는 것을 알게 되었습니다.은 C 유형 C입니다.size_t이는 기본적으로 서명되지 않은 int이지만 특정 플랫폼에 대해 "충분히 큰" 크기를 보장합니다.sizeof연산자가 유형의 결과를 반환합니다.size_t그리고 우리가 진짜 말록에 대한 C 표준의 정의를 본다면, 그것은.void *malloc(size_t size);.그렇게size_t사용하기에 가장 적합한 유형입니다.
stdlib.h에 있는 것과 같은 이름을 우리만의 malloc 함수에 사용하는 것은 좋지 않습니다.stdlib.h를 포함해야 한다면 상황이 엉망이 될 것입니다.경험상 C 표준 라이브러리 함수의 식별자 이름을 사용자 코드에 사용하지 마십시오.이름을 kr_malloc으로 변경하겠습니다.
코드는 모든 정적 변수가 0으로 초기화되도록 보장한다는 사실을 악용하고 있습니다.이것은 C 표준에 의해 잘 정의되지만 다소 미묘한 규칙입니다.모든 통계를 명시적으로 초기화하여 실수로 초기화하는 것을 잊지 않았음을 보여줍니다.
조건 내에서 할당하는 것은 위험하고 읽기 어렵습니다.고전적인 = 대 == 버그와 같은 버그도 발생할 수 있으므로 가능하면 피해야 합니다.
동일한 행에 여러 개의 할당이 있을 경우 평가 순서 때문에 읽기 어렵고 위험할 수도 있습니다.
동일한 행에 있는 여러 선언은 읽기 어렵고 위험합니다. 데이터와 포인터 선언을 혼합할 때 버그가 발생할 수 있기 때문입니다.항상 각 변수를 해당 행에 선언합니다.
모든 문 뒤에 항상 중괄호를 사용합니다.그렇게 하지 않으면 버그 버그 버그로 이어질 수 있습니다.
void*에는 특정 포인터 유형에서 cast를 입력하지 마십시오.C에서는 불필요하며 컴파일러가 감지했을 버그를 숨길 수 있습니다.
함수 내에서 반환문을 여러 개 사용하지 않도록 합니다.때때로 그것들은 더 명확한 코드로 이어지지만, 대부분의 경우 그것들은 스파게티로 이어집니다.코드 상태로는 루프를 다시 작성하지 않고는 변경할 수 없기 때문에 나중에 수정하겠습니다.
10) 루프를 단순하게 유지합니다.하나의 init 문, 하나의 루프 조건 및 하나의 반복을 포함해야 합니다.이것은 쉼표 연산자와 모든 것을 포함하는 루프에 대한 것으로 매우 모호합니다.다시, 우리는 이 루프를 제정신인 것으로 다시 쓸 필요성을 발견합니다.다음 단계에서는 이 작업을 수행하지만, 현재로서는 다음과 같은 작업이 수행됩니다.
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
size_t size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base = {0}; /* empty list to get started */
static Header* freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
Header* p;
Header* prevp;
size_t nunits;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;
prevp = freep;
if (prevp == NULL) /* no free list yet */
{
base.s.ptr = &base;
freeptr = &base;
prevptr = &base;
base.s.size = 0;
}
for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr)
{
if (p->s.size >= nunits) /* big enough */
{
if (p->s.size == nunits) /* exactly */
{
prevp->s.ptr = p->s.ptr;
}
else /* allocate tail end */
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits
}
freep = prevp;
return p+1;
}
if (p == freep) /* wrapped around free list */
{
p = morecore(nunits);
if (p == NULL)
{
return NULL; /* none left */
}
}
} /* for */
}
3단계: 모호한 루프를 다시 작성합니다.
앞에서 언급한 이유로.우리는 이 루프가 영원히 지속되고, 할당이 완료되거나 메모리가 남아 있지 않을 때 함수에서 반환됨으로써 종료된다는 것을 알 수 있습니다.루프 조건으로 생성하고 함수의 끝 부분을 원래의 위치로 되돌립니다.그리고 그 못생긴 콤마 연산자를 제거합시다.
두 가지 새로운 변수를 소개하겠습니다. 하나는 결과 포인터를 고정하는 결과 변수이고 다른 하나는 루프가 계속되어야 하는지 여부를 추적하는 결과 변수입니다.K&R의 마음을 날려버리겠습니다.bool1999.부터 C
(나는 내가 이 변경으로 알고리즘을 변경하지 않았기를 바란다, 나는 내가 변경하지 않았다고 믿는다)
#include <stdbool.h>
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
size_t size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base = {0}; /* empty list to get started */
static Header* freep = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
Header* p;
Header* prevp;
size_t nunits;
void* result;
bool is_allocating;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(header) + 1;
prevp = freep;
if (prevp == NULL) /* no free list yet */
{
base.s.ptr = &base;
freeptr = &base;
prevptr = &base;
base.s.size = 0;
}
is_allocating = true;
for (p = prevp->s.ptr; is_allocating; p = p->s.ptr)
{
if (p->s.size >= nunits) /* big enough */
{
if (p->s.size == nunits) /* exactly */
{
prevp->s.ptr = p->s.ptr;
}
else /* allocate tail end */
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits
}
freep = prevp;
result = p+1;
is_allocating = false; /* we are done */
}
if (p == freep) /* wrapped around free list */
{
p = morecore(nunits);
if (p == NULL)
{
result = NULL; /* none left */
is_allocating = false;
}
}
prevp = p;
} /* for */
return result;
}
4단계: 이 쓰레기를 컴파일합니다.
K&R에서 온 거라 오타가 가득합니다.sizeof(header)야 .sizeof(Header)세미콜론이 누락되었습니다.이들은 frep, prepp 대 freptr, preptr이라는 다른 이름을 사용하지만 분명히 동일한 변수를 의미합니다.저는 후자가 실제로 더 나은 이름이었다고 생각합니다, 그러니 그것들을 사용합시다.
#include <stdbool.h>
typedef long Align; /* for alignment to long boundary */
typedef union header /* block header */
{
struct
{
union header *ptr; /* next block if on free list */
size_t size; /* size of this block */
} s;
Align x; /* force alignment of blocks */
} Header;
static Header base = {0}; /* empty list to get started */
static Header* freeptr = NULL; /* start of free list */
/* malloc: general-purpose storage allocator */
void* kr_malloc (size_t nbytes)
{
Header* p;
Header* prevptr;
size_t nunits;
void* result;
bool is_allocating;
nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
prevptr = freeptr;
if (prevptr == NULL) /* no free list yet */
{
base.s.ptr = &base;
freeptr = &base;
prevptr = &base;
base.s.size = 0;
}
is_allocating = true;
for (p = prevptr->s.ptr; is_allocating; p = p->s.ptr)
{
if (p->s.size >= nunits) /* big enough */
{
if (p->s.size == nunits) /* exactly */
{
prevptr->s.ptr = p->s.ptr;
}
else /* allocate tail end */
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits;
}
freeptr = prevptr;
result = p+1;
is_allocating = false; /* we are done */
}
if (p == freeptr) /* wrapped around free list */
{
p = morecore(nunits);
if (p == NULL)
{
result = NULL; /* none left */
is_allocating = false;
}
}
prevptr = p;
} /* for */
return result;
}
그리고 이제 우리는 수많은 위험한 관행 없이 어느 정도 읽을 수 있고 유지할 수 있는 코드를 가지고 있습니다. 심지어 컴파일할 수도 있습니다!이제 우리는 코드가 실제로 무엇을 하고 있는지 생각해 볼 수 있습니다.
목록에 Header" 구조는 여러분이 추측한 것처럼 링크된 목록에 있는 노드의 선언입니다.이러한 각 노드에는 다음 노드에 대한 포인터가 포함되어 있습니다.저는 더 핵심적인 기능이나 "랩-어라운드"를 잘 이해하지 못합니다. 저는 이 기능을 사용한 적이 없고,sbrk그러나 이 구조체에 지정된 대로 헤더를 할당하고, 그 헤더 뒤에 있는 원시 데이터 덩어리도 할당한다고 가정합니다.그렇다면 실제 데이터 포인터가 없는 이유를 설명합니다. 데이터는 메모리에서 헤더를 따라가는 것으로 가정됩니다.그래서 각 노드에 대해, 우리는 헤더를 얻고, 헤더 뒤에 있는 원시 데이터 덩어리를 얻습니다.
반복 자체는 매우 간단하며, 한 번에 하나의 노드로 연결된 목록을 통과합니다.
루프의 끝에서, 그들은 포인터를 "청크"의 끝을 지나도록 설정한 다음 정적 변수에 저장하여 프로그램이 다음에 함수가 호출될 때 이전에 메모리를 할당한 위치를 기억하도록 합니다.
이들은 머리글이 정렬된 메모리 주소로 끝나도록 하기 위해 트릭을 사용하고 있습니다. 즉, 플랫폼의 정렬 요구 사항에 대응할 수 있을 정도로 큰 변수와 함께 모든 오버헤드 정보를 하나의 연합에 저장합니다.따라서 "ptr"의 크기와 "size"의 크기가 너무 작아서 정확한 정렬을 제공할 수 없는 경우, 유니온은 최소 크기의 (Align) 바이트가 할당되도록 보장합니다.저는 C 표준이 자동 구조/연합 패딩을 요구하기 때문에 이 모든 속임수가 오늘날 쓸모가 없다고 생각합니다.
저는 OP가 이런 질문을 했을 때 K&R을 공부하고 있습니다. 그리고 저는 이러한 구현들이 혼란스럽다고 생각했기 때문에 여기에 왔습니다.승인된 답변이 매우 상세하고 도움이 되지만, 저는 코드를 원래 작성된 대로 이해하는 다른 방침을 취하려고 노력했습니다. 코드를 검토하고 코드 섹션에 제가 어려워하는 의견을 추가했습니다.. (은 " " " " " (으) " " 입니다.free그리고.memcore이름을 바꿨습니다.kandr_malloc그리고.kandr_freestdlib와의 충돌을 방지하기 위해).저는 이것이 도움이 될 수 있는 다른 학생들을 위해 받아들여진 답에 대한 보충으로 여기에 남겨둘 것이라고 생각했습니다.
저는 이 코드의 코멘트가 과도하다는 것을 인정합니다.제가 이것을 단지 학습 연습으로만 하고 있고 이것이 실제로 코드를 작성하는 좋은 방법이라고 제안하는 것은 아니라는 것을 알아주세요.
저는 몇 가지 변수 이름을 제가 좀 더 직관적으로 보이는 이름으로 변경할 수 있었습니다. 다만 코드가 기본적으로 그대로 남아 있다는 점은 제외하고는 말이죠.발그랜드가 일부 애플리케이션에 불만이 있었지만 제가 사용한 테스트 프로그램에 대해서는 잘 컴파일되고 실행되는 것 같습니다.
또한: 댓글의 일부 텍스트는 K&R 또는 맨 페이지에서 직접 삭제되었습니다. 저는 이 섹션에 대해 어떠한 크레딧도 받을 생각이 없습니다.
#include <unistd.h> // sbrk
#define NALLOC 1024 // Number of block sizes to allocate on call to sbrk
#ifdef NULL
#undef NULL
#endif
#define NULL 0
// long is chosen as an instance of the most restrictive alignment type
typedef long Align;
/* Construct Header data structure. To ensure that the storage returned by
* kandr_malloc is aligned properly for the objects that are stored in it, all
* blocks are multiples of the header size, and the header itself is aligned
* properly. This is achieved through the use of a union; this data type is big
* enough to hold the "widest" member, and the alignment is appropriate for all
* of the types in the union. Thus by including a member of type Align, which
* is an instance of the most restrictive type, we guarantee that the size of
* Header is aligned to the worst-case boundary. The Align field is never used;
* it just forces each header to the desired alignment.
*/
union header {
struct {
union header *next;
unsigned size;
} s;
Align x;
};
typedef union header Header;
static Header base; // Used to get an initial member for free list
static Header *freep = NULL; // Free list starting point
static Header *morecore(unsigned nblocks);
void kandr_free(void *ptr);
void *kandr_malloc(unsigned nbytes) {
Header *currp;
Header *prevp;
unsigned nunits;
/* Calculate the number of memory units needed to provide at least nbytes of
* memory.
*
* Suppose that we need n >= 0 bytes and that the memory unit sizes are b > 0
* bytes. Then n / b (using integer division) yields one less than the number
* of units needed to provide n bytes of memory, except in the case that n is
* a multiple of b; then it provides exactly the number of units needed. It
* can be verified that (n - 1) / b provides one less than the number of units
* needed to provide n bytes of memory for all values of n > 0. Thus ((n - 1)
* / b) + 1 provides exactly the number of units needed for n > 0.
*
* The extra sizeof(Header) in the numerator is to include the unit of memory
* needed for the header itself.
*/
nunits = ((nbytes + sizeof(Header) - 1) / sizeof(Header)) + 1;
// case: no free list yet exists; we have to initialize.
if (freep == NULL) {
// Create degenerate free list; base points to itself and has size 0
base.s.next = &base;
base.s.size = 0;
// Set free list starting point to base address
freep = &base;
}
/* Initialize pointers to two consecutive blocks in the free list, which we
* call prevp (the previous block) and currp (the current block)
*/
prevp = freep;
currp = prevp->s.next;
/* Step through the free list looking for a block of memory large enough to
* fit nunits units of memory into. If the whole list is traversed without
* finding such a block, then morecore is called to request more memory from
* the OS.
*/
for (; ; prevp = currp, currp = currp->s.next) {
/* case: found a block of memory in free list large enough to fit nunits
* units of memory into. Partition block if necessary, remove it from the
* free list, and return the address of the block (after moving past the
* header).
*/
if (currp->s.size >= nunits) {
/* case: block is exactly the right size; remove the block from the free
* list by pointing the previous block to the next block.
*/
if (currp->s.size == nunits) {
/* Note that this line wouldn't work as intended if we were down to only
* 1 block. However, we would never make it here in that scenario
* because the block at &base has size 0 and thus the conditional will
* fail (note that nunits is always >= 1). It is true that if the block
* at &base had combined with another block, then previous statement
* wouldn't apply - but presumably since base is a global variable and
* future blocks are allocated on the heap, we can be sure that they
* won't border each other.
*/
prevp->s.next = currp->s.next;
}
/* case: block is larger than the amount of memory asked for; allocate
* tail end of the block to the user.
*/
else {
// Changes the memory stored at currp to reflect the reduced block size
currp->s.size -= nunits;
// Find location at which to create the block header for the new block
currp += currp->s.size;
// Store the block size in the new header
currp->s.size = nunits;
}
/* Set global starting position to the previous pointer. Next call to
* malloc will start either at the remaining part of the partitioned block
* if a partition occurred, or at the block after the selected block if
* not.
*/
freep = prevp;
/* Return the location of the start of the memory, i.e. after adding one
* so as to move past the header
*/
return (void *) (currp + 1);
} // end found a block of memory in free list case
/* case: we've wrapped around the free list without finding a block large
* enough to fit nunits units of memory into. Call morecore to request that
* at least nunits units of memory are allocated.
*/
if (currp == freep) {
/* morecore returns freep; the reason that we have to assign currp to it
* again (since we just tested that they are equal), is that there is a
* call to free inside of morecore that can potentially change the value
* of freep. Thus we reassign it so that we can be assured that the newly
* added block is found before (currp == freep) again.
*/
if ((currp = morecore(nunits)) == NULL) {
return NULL;
}
} // end wrapped around free list case
} // end step through free list looking for memory loop
}
static Header *morecore(unsigned nunits) {
void *freemem; // The address of the newly created memory
Header *insertp; // Header ptr for integer arithmatic and constructing header
/* Obtaining memory from OS is a comparatively expensive operation, so obtain
* at least NALLOC blocks of memory and partition as needed
*/
if (nunits < NALLOC) {
nunits = NALLOC;
}
/* Request that the OS increment the program's data space. sbrk changes the
* location of the program break, which defines the end of the process's data
* segment (i.e., the program break is the first location after the end of the
* uninitialized data segment). Increasing the program break has the effect
* of allocating memory to the process. On success, brk returns the previous
* break - so if the break was increased, then this value is a pointer to the
* start of the newly allocated memory.
*/
freemem = sbrk(nunits * sizeof(Header));
// case: unable to allocate more memory; sbrk returns (void *) -1 on error
if (freemem == (void *) -1) {
return NULL;
}
// Construct new block
insertp = (Header *) freemem;
insertp->s.size = nunits;
/* Insert block into the free list so that it is available for malloc. Note
* that we add 1 to the address, effectively moving to the first position
* after the header data, since of course we want the block header to be
* transparent for the user's interactions with malloc and free.
*/
kandr_free((void *) (insertp + 1));
/* Returns the start of the free list; recall that freep has been set to the
* block immediately preceeding the newly allocated memory (by free). Thus by
* returning this value the calling function can immediately find the new
* memory by following the pointer to the next block.
*/
return freep;
}
void kandr_free(void *ptr) {
Header *insertp, *currp;
// Find address of block header for the data to be inserted
insertp = ((Header *) ptr) - 1;
/* Step through the free list looking for the position in the list to place
* the insertion block. In the typical circumstances this would be the block
* immediately to the left of the insertion block; this is checked for by
* finding a block that is to the left of the insertion block and such that
* the following block in the list is to the right of the insertion block.
* However this check doesn't check for one such case, and misses another. We
* still have to check for the cases where either the insertion block is
* either to the left of every other block owned by malloc (the case that is
* missed), or to the right of every block owned by malloc (the case not
* checked for). These last two cases are what is checked for by the
* condition inside of the body of the loop.
*/
for (currp = freep; !((currp < insertp) && (insertp < currp->s.next)); currp = currp->s.next) {
/* currp >= currp->s.ptr implies that the current block is the rightmost
* block in the free list. Then if the insertion block is to the right of
* that block, then it is the new rightmost block; conversely if it is to
* the left of the block that currp points to (which is the current leftmost
* block), then the insertion block is the new leftmost block. Note that
* this conditional handles the case where we only have 1 block in the free
* list (this case is the reason that we need >= in the first test rather
* than just >).
*/
if ((currp >= currp->s.next) && ((currp < insertp) || (insertp < currp->s.next))) {
break;
}
}
/* Having found the correct location in the free list to place the insertion
* block, now we have to (i) link it to the next block, and (ii) link the
* previous block to it. These are the tasks of the next two if/else pairs.
*/
/* case: the end of the insertion block is adjacent to the beginning of
* another block of data owned by malloc. Absorb the block on the right into
* the block on the left (i.e. the previously existing block is absorbed into
* the insertion block).
*/
if ((insertp + insertp->s.size) == currp->s.next) {
insertp->s.size += currp->s.next->s.size;
insertp->s.next = currp->s.next->s.next;
}
/* case: the insertion block is not left-adjacent to the beginning of another
* block of data owned by malloc. Set the insertion block member to point to
* the next block in the list.
*/
else {
insertp->s.next = currp->s.next;
}
/* case: the end of another block of data owned by malloc is adjacent to the
* beginning of the insertion block. Absorb the block on the right into the
* block on the left (i.e. the insertion block is absorbed into the preceeding
* block).
*/
if ((currp + currp->s.size) == insertp) {
currp->s.size += insertp->s.size;
currp->s.next = insertp->s.next;
}
/* case: the insertion block is not right-adjacent to the end of another block
* of data owned by malloc. Set the previous block in the list to point to
* the insertion block.
*/
else {
currp->s.next = insertp;
}
/* Set the free pointer list to start the block previous to the insertion
* block. This makes sense because calls to malloc start their search for
* memory at the next block after freep, and the insertion block has as good a
* chance as any of containing a reasonable amount of memory since we've just
* added some to it. It also coincides with calls to morecore from
* kandr_malloc because the next search in the iteration looks at exactly the
* right memory block.
*/
freep = currp;
}
malloc()의 기본.
Linux에서는 sbrk와 mmap의 두 가지 일반적인 메모리 요청 방법이 있습니다.이러한 시스템 호출은 빈번한 작은 할당에 심각한 제한이 있습니다. malloc()는 이 문제를 해결하기 위한 라이브러리 함수입니다.sbrk/mmap으로 큰 메모리 청크를 요청하고 큰 청크 안에 작은 메모리 블록을 반환합니다.이는 sbrk/mmap을 직접 호출하는 것보다 훨씬 효율적이고 유연합니다.
K&R malloc()
K&R 구현에서 코어(일반적으로 아레나라고 함)는 큰 메모리 덩어리입니다.morecore()합니다.sbrk()malloc()/free()를 여러 번 호출하면 코어의 일부 블록이 사용/할당되고 다른 블록은 비어 있습니다.K&R malloc은 무료 블록의 주소를 원형 단일 연결 목록에 저장합니다.이 목록에서 각 노드는 사용 가능한 메모리 블록입니다.첫번째sizeof(Header)바이트는 블록의 크기와 포인터를 다음 빈 블록으로 유지합니다.사용 가능한 블록의 나머지 바이트는 초기화되지 않습니다.교과서의 일반적인 목록과 달리 빈 목록의 노드는 코어에서 사용되지 않는 일부 영역에 대한 포인터일 뿐이며 코어를 제외한 각 노드는 실제로 할당하지 않습니다.이 목록은 알고리즘을 이해하는 열쇠입니다.
다음 다이어그램은 두 개의 코어/아레나가 있는 메모리 레이아웃의 예를 보여줍니다.다이어그램에서 각 문자는 다음과 같습니다.sizeof(Header) 수@입니다.Header,+와 할된메표니다를 합니다.-코어 내부의 빈 메모리를 표시합니다.이 예에서는 세 개의 할당된 블록과 세 개의 사용 가능한 블록이 있습니다.세 개의 빈 블록이 순환 목록에 저장됩니다.의 할당된 블록에 만 세된블록경크저다니에 됩니다.Header.
This is core 1 This is core 2
@---------@+++++++++@++++++++++++ @----------@+++++++++++++++++@------------
| | |
p->ptr->ptr p = p->ptr->ptr->ptr p->ptr
코드에서, 신당코서에드,,freep무료 목록의 진입점입니다.반복적으로 다음을 수행하는 경우freep->ptr당신은 돌아올 것입니다.freep그것은 원형입니다.순환 단일 연결 목록을 이해하면 나머지는 비교적 쉽습니다.malloc()사용 가능한 블록을 찾아서 분할할 수 있습니다.free()사용 가능한 블록을 목록에 다시 추가하고 인접한 사용 가능한 블록에 병합할 수 있습니다.그들은 둘 다 목록의 구조를 유지하려고 노력합니다.
구현에 대한 기타 의견
은 랩드주언급는 "어라운드같다"에서 "랩 어라운드언급했습니다.
malloc()해당 줄은 전체 빈 목록을 이동했지만 요청한 길이보다 큰 빈 블록을 찾을 수 없는 경우에 발생합니다.이 경우 다음을 사용하여 새 코어를 추가해야 합니다.morecore().base는 항상 사용 가능 목록에 포함되는 0 크기 블록입니다.특수 케이스를 피하기 위한 요령입니다.그것은 꼭 필요한 것은 아닙니다.free()새로 해제된 블록을 목록의 다른 자유 블록에 병합하려면 네 가지 경우를 고려해야 하므로 약간 복잡해 보일 수 있습니다.이 세부 사항은 직접 구현하지 않는 한 그다지 중요하지 않습니다.
PS: K&R malloc은 제가 보기에 가장 우아한 코드 중 하나입니다.제가 처음 코드를 이해했을 때는 정말 눈이 번쩍 뜨였습니다.이 구현의 기본을 이해하지 못하는 일부 현대 프로그래머들이 오로지 코딩 스타일에 근거하여 걸작을 쓰레기라고 부르는 것은 저를 슬프게 합니다.
저는 또한 이 운동이 훌륭하고 흥미로웠습니다.
제 생각에는 구조를 시각화하는 것이 논리를 이해하는 데 많은 도움이 될 수도 있고 적어도 이것은 저에게 효과가 있었습니다.아래는 K&R malloc의 흐름에 대해 가능한 한 많이 출력하는 제 코드입니다.
제가 K&R malloc에서 한 가장 중요한 변화는 일부 오래된 포인터가 다시 사용되지 않도록 'free'를 변경한 것입니다.그 외에 코멘트를 추가하고 작은 오타를 수정했습니다.
NALOC, MAXMEM, 'main'의 테스트 변수로 실험하는 것도 도움이 될 수 있습니다.
내 컴퓨터(Ubuntu 16.04.3)에서 오류 없이 컴파일되었습니다.
gcc -g -std=c99 -Wall -Wextra -pedantic-errors krmalloc.c
krmalloc.c :
#include <stdio.h>
#include <unistd.h>
typedef long Align; /* for alignment to long boundary */
union header { /* block header */
struct {
union header *ptr; /* next block if on free list */
size_t size; /* size of this block */
/* including the Header itself */
/* measured in count of Header chunks */
/* not less than NALLOC Header's */
} s;
Align x; /* force alignment of blocks */
};
typedef union header Header;
static Header *morecore(size_t);
void *mmalloc(size_t);
void _mfree(void **);
void visualize(const char*);
size_t getfreem(void);
size_t totmem = 0; /* total memory in chunks */
static Header base; /* empty list to get started */
static Header *freep = NULL; /* start of free list */
#define NALLOC 1 /* minimum chunks to request */
#define MAXMEM 2048 /* max memory available (in bytes) */
#define mfree(p) _mfree((void **)&p)
void *sbrk(__intptr_t incr);
int main(void)
{
char *pc, *pcc, *pccc, *ps;
long *pd, *pdd;
int dlen = 100;
int ddlen = 50;
visualize("start");
/* trying to fragment as much as possible to get a more interesting view */
/* claim a char */
if ((pc = (char *) mmalloc(sizeof(char))) == NULL)
return -1;
/* claim a string */
if ((ps = (char *) mmalloc(dlen * sizeof(char))) == NULL)
return -1;
/* claim some long's */
if ((pd = (long *) mmalloc(ddlen * sizeof(long))) == NULL)
return -1;
/* claim some more long's */
if ((pdd = (long *) mmalloc(ddlen * 2 * sizeof(long))) == NULL)
return -1;
/* claim one more char */
if ((pcc = (char *) mmalloc(sizeof(char))) == NULL)
return -1;
/* claim the last char */
if ((pccc = (char *) mmalloc(sizeof(char))) == NULL)
return -1;
/* free and visualize */
printf("\n");
mfree(pccc);
/* bugged on purpose to test free(NULL) */
mfree(pccc);
visualize("free(the last char)");
mfree(pdd);
visualize("free(lot of long's)");
mfree(ps);
visualize("free(string)");
mfree(pd);
visualize("free(less long's)");
mfree(pc);
visualize("free(first char)");
mfree(pcc);
visualize("free(second char)");
/* check memory condition */
size_t freemem = getfreem();
printf("\n");
printf("--- Memory claimed : %ld chunks (%ld bytes)\n",
totmem, totmem * sizeof(Header));
printf(" Free memory now : %ld chunks (%ld bytes)\n",
freemem, freemem * sizeof(Header));
if (freemem == totmem)
printf(" No memory leaks detected.\n");
else
printf(" (!) Leaking memory: %ld chunks (%ld bytes).\n",
(totmem - freemem), (totmem - freemem) * sizeof(Header));
printf("// Done.\n\n");
return 0;
}
/* visualize: print the free list (educational purpose) */
void visualize(const char* msg)
{
Header *tmp;
printf("--- Free list after \"%s\":\n", msg);
if (freep == NULL) { /* does not exist */
printf("\tList does not exist\n\n");
return;
}
if (freep == freep->s.ptr) { /* self-pointing list = empty */
printf("\tList is empty\n\n");
return;
}
printf(" ptr: %10p size: %-3lu --> ", (void *) freep, freep->s.size);
tmp = freep; /* find the start of the list */
while (tmp->s.ptr > freep) { /* traverse the list */
tmp = tmp->s.ptr;
printf("ptr: %10p size: %-3lu --> ", (void *) tmp, tmp->s.size);
}
printf("end\n\n");
}
/* calculate the total amount of available free memory */
size_t getfreem(void)
{
if (freep == NULL)
return 0;
Header *tmp;
tmp = freep;
size_t res = tmp->s.size;
while (tmp->s.ptr > tmp) {
tmp = tmp->s.ptr;
res += tmp->s.size;
}
return res;
}
/* mmalloc: general-purpose storage allocator */
void *mmalloc(size_t nbytes)
{
Header *p, *prevp;
size_t nunits;
/* smallest count of Header-sized memory chunks */
/* (+1 additional chunk for the Header itself) needed to hold nbytes */
nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
/* too much memory requested? */
if (((nunits + totmem + getfreem())*sizeof(Header)) > MAXMEM) {
printf("Memory limit overflow!\n");
return NULL;
}
if ((prevp = freep) == NULL) { /* no free list yet */
/* set the list to point to itself */
base.s.ptr = freep = prevp = &base;
base.s.size = 0;
}
/* traverse the circular list */
for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
if (p->s.size >= nunits) { /* big enough */
if (p->s.size == nunits) /* exactly */
prevp->s.ptr = p->s.ptr;
else { /* allocate tail end */
/* adjust the size */
p->s.size -= nunits;
/* find the address to return */
p += p->s.size;
p->s.size = nunits;
}
freep = prevp;
return (void *)(p+1);
}
/* back where we started and nothing found - we need to allocate */
if (p == freep) /* wrapped around free list */
if ((p = morecore(nunits)) == NULL)
return NULL; /* none left */
}
}
/* morecore: ask system for more memory */
/* nu: count of Header-chunks needed */
static Header *morecore(size_t nu)
{
char *cp;
Header *up;
/* get at least NALLOC Header-chunks from the OS */
if (nu < NALLOC)
nu = NALLOC;
cp = (char *) sbrk(nu * sizeof(Header));
if (cp == (char *) -1) /* no space at all */
return NULL;
printf("... (sbrk) claimed %ld chunks.\n", nu);
totmem += nu; /* keep track of allocated memory */
up = (Header *) cp;
up->s.size = nu;
/* add the free space to the circular list */
void *n = (void *)(up+1);
mfree(n);
return freep;
}
/* mfree: put block ap in free list */
void _mfree(void **ap)
{
if (*ap == NULL)
return;
Header *bp, *p;
bp = (Header *)*ap - 1; /* point to block header */
if (bp->s.size == 0 || bp->s.size > totmem) {
printf("_mfree: impossible value for size\n");
return;
}
/* the free space is only marked as free, but 'ap' still points to it */
/* to avoid reusing this address and corrupt our structure set it to '\0' */
*ap = NULL;
/* look where to insert the free space */
/* (bp > p && bp < p->s.ptr) => between two nodes */
/* (p > p->s.ptr) => this is the end of the list */
/* (p == p->p.str) => list is one element only */
for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
/* freed block at start or end of arena */
break;
if (bp + bp->s.size == p->s.ptr) { /* join to upper nbr */
/* the new block fits perfect up to the upper neighbor */
/* merging up: adjust the size */
bp->s.size += p->s.ptr->s.size;
/* merging up: point to the second next */
bp->s.ptr = p->s.ptr->s.ptr;
} else
/* set the upper pointer */
bp->s.ptr = p->s.ptr;
if (p + p->s.size == bp) { /* join to lower nbr */
/* the new block fits perfect on top of the lower neighbor */
/* merging below: adjust the size */
p->s.size += bp->s.size;
/* merging below: point to the next */
p->s.ptr = bp->s.ptr;
} else
/* set the lower pointer */
p->s.ptr = bp;
/* reset the start of the free list */
freep = p;
}
언급URL : https://stackoverflow.com/questions/13159564/explain-this-implementation-of-malloc-from-the-kr-book
'programing' 카테고리의 다른 글
| 도커 이미지에 대한 빌드 컨텍스트 매우 큼 (0) | 2023.08.15 |
|---|---|
| 도커 구성에서 포트와 노출의 차이점은 무엇입니까? (0) | 2023.08.15 |
| .git 디렉터리 웹에 액세스할 수 없도록 설정 (0) | 2023.08.15 |
| jQuery : 사용자 지정 특성이 있는 모든 요소 선택 (0) | 2023.08.15 |
| jQuery Validation 플러그인: 지정된 제출 단추에 대해 유효성 검사 사용 안 함 (0) | 2023.08.15 |