uClibc heap malloc 분석

struct malloc_state { /* The maximum chunk size to be eligible for fastbin */ size_t max_fast; /* low 2 bits used as flags */ // 하위 2bits는 flags로 설정 // 첫 하위 1bit[FASTCHUNKS_BIT] -> any free 청크가 있는지 체크. 있다면 1로 세팅 // ㄴ오로지 malloc_consolidate시 에만 0으로 설정됨 // 그 다음 1bit[ANYCHUNKS_BIT] -> fastbin에 free청크가 존재한다면 1로 세팅. /* Fastbins */ mfastbinptr fastbins[NFASTBINS]; // NFASTBINS==10, fastbins[10] /* Base of the topmost chunk -- not otherwise kept in a bin */ mchunkptr top; /* The remainder from the most recent split of a small request */ mchunkptr last_remainder; /* Normal bins packed as described above */ mchunkptr bins[NBINS * 2]; // NBINS==96, bins[192] /* Bitmap of bins. Trailing zero map handles cases of largest binned size */ unsigned int binmap[BINMAPSIZE+1]; ...

void* malloc(size_t bytes) { mstate av; size_t nb; /* normalized request size */ unsigned int idx; /* associated bin index */ mbinptr bin; /* associated bin */ mfastbinptr* fb; /* associated fastbin */ mchunkptr victim; /* inspected/selected chunk */ size_t size; /* its size */ int victim_index; /* its bin index */ mchunkptr remainder; /* remainder from a split */ unsigned long remainder_size; /* its size */ unsigned int block; /* bit map traverser */ unsigned int bit; /* bit map traverser */ unsigned int map; /* current word of binmap */ mchunkptr fwd; /* misc temp for linking */ mchunkptr bck; /* misc temp for linking */ void * sysmem; void * retval; av = get_malloc_state(); // main_arena 객체 가져오기. checked_request2size(bytes, nb); // 매크로 함수. 아래 주석 참조 /* #define checked_request2size(req, sz) \ if (REQUEST_OUT_OF_RANGE(req)) { \ errno = ENOMEM;// 12 \ return 0; \ } //요청 크기가 REQUEST_OUT_OF_RANGE 보다 크면 안됨. //최대 요청 크기는 0x0xFFFFFFDF (sz) = request2size(req); // 요청크기 + 메타데이터(prev_size,size) 8bytes를 포함할 수 있는 크기 반환. // ex) 요청크기 0x20 -> 0x28 반환. 상세 구조는 request2size 매크로 확인. */ /* av->max_fast의 하위 1bit가 1이면 현재 free된 청크가 없다는 의미. 아직 free된 청크가 없는 경우, top 청크에서 split 하여 할당. */ if (!have_anychunks(av)) { if (av->max_fast == 0) /* initialization check */ __malloc_consolidate(av); goto use_top; }

void* malloc(size_t bytes) { ... /* If the size qualifies as a fastbin, first check corresponding bin. #define fastbin_index(sz) ((((unsigned int)(sz)) >> 3) - 2) */ if ((unsigned long)(nb) <= (unsigned long)(av->max_fast)) { fb = &(av->fastbins[(fastbin_index(nb))]); if ( (victim = *fb) != 0) { *fb = victim->fd; // fastbin에 들어있는 청크를 재할당 해주고 fd에 들어있는 // 다음 free 청크를 앞으로 땡겨야하기 때문에 fb에 해당 청크 주소 저장 check_remalloced_chunk(victim, nb); //재할당 하려는 청크 사이즈 유효성 검증 retval = chunk2mem(victim); // 청크헤더+8 주소 반환 goto DONE; } }

/* If a small request, check regular bin. Since these "smallbins" hold one size each, no searching within bins is necessary. (For a large request, we need to wait until unsorted chunks are processed to find best fit. But for small ones, fits are exact anyway, so we can check now, which is faster.) MIN_LARGE_SIZE = 256 #define in_smallbin_range(sz) ((unsigned long)(sz) < (unsigned long)MIN_LARGE_SIZE) #define smallbin_index(sz) (((unsigned)(sz)) >> 3) /* addressing -- note that bin_at(0) does not exist */ #define bin_at(m, i) ((mbinptr)((char*)&((m)->bins[(i)<<1]) - ((sizeof(size_t))<<1))) #define first(b) ((b)->fd) #define last(b) ((b)->bk) */ if (in_smallbin_range(nb)) { // 최대 smallbin 크기는 255 idx = smallbin_index(nb); bin = bin_at(av,idx); // 인덱스에 맞는 bin 주소 가져오기 if ( (victim = last(bin)) != bin) { // 재할당 하려는 bin에 연결된 다른 free 청크들이 있다면 연결 해제 bck = victim->bk; set_inuse_bit_at_offset(victim, nb); bin->bk = bck; bck->fd = bin; // A -> B -> C 구조에서 B를 재할당 하려면 // A -> C 로 free list 재구성 // B를 재할당 하기 때문에 C 청크의 inuse bit 설정 check_malloced_chunk(victim, nb); retval = chunk2mem(victim); //청크헤더+8 주소 반환 goto DONE; } } else { idx = __malloc_largebin_index(nb); if (have_fastchunks(av)) __malloc_consolidate(av); }

/* If a small request, check regular bin. Since these "smallbins" hold one size each, no searching within bins is necessary. (For a large request, we need to wait until unsorted chunks are processed to find best fit. But for small ones, fits are exact anyway, so we can check now, which is faster.) MIN_LARGE_SIZE = 256 #define in_smallbin_range(sz) ((unsigned long)(sz) < (unsigned long)MIN_LARGE_SIZE) #define smallbin_index(sz) (((unsigned)(sz)) >> 3) #define bin_at(m, i) ((mbinptr)((char*)&((m)->bins[(i)<<1]) - ((sizeof(size_t))<<1))) #define first(b) ((b)->fd) #define last(b) ((b)->bk) # */ if (in_smallbin_range(nb)) { // 최대 smallbin 크기는 255 idx = smallbin_index(nb); bin = bin_at(av,idx); // 인덱스에 맞는 bin 주소 가져오기 ... } } else { // 요청 사이즈가 255보다 크다면 largebin에서 검색 // __malloc_largebin_index -> bin[32] 부터 각 bin당 64bytes 크기 idx = __malloc_largebin_index(nb); if (have_fastchunks(av)) __malloc_consolidate(av); }

/* Process recently freed or remaindered chunks, taking one only if it is exact fit, or, if this a small request, the chunk is remainder from the most recent non-exact fit. Place other traversed chunks in bins. Note that this step is the only place in any routine where chunks are placed in bins. #define unsorted_chunks(M) (bin_at(M, 1)) // -> bin[0] #define bin_at(m, i) ((mbinptr)((char*)&((m)->bins[(i)<<1]) - ((sizeof(size_t))<<1))) */ while ( (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) { // unsortedbin에 가용 가능한 청크가 존재하는 경우. 소진 될 때 까지 반복 bck = victim->bk; // unsorted bin의 맨 뒤 청크 size = chunksize(victim); /* If a small request, try to use last remainder if it is the only chunk in unsorted bin. This helps promote locality for runs of consecutive small requests. This is the only exception to best-fit, and applies only when there is no exact fit for a small chunk. */ if (in_smallbin_range(nb) && // 요청 크기가 smallbin 크기고 bck == unsorted_chunks(av) && // unsorted bin에 한 개의 청크만 있고 victim == av->last_remainder && // 그 청크가 last_remainder라면 (unsigned long)(size) > (unsigned long)(nb + MINSIZE)) { // unsorted bin에 있는 청크 크기가 요청크기+MINSIZE보다 크다면 // last_remainder 청크를 split 수행 /* split and reattach remainder */ remainder_size = size - nb; // split 후 남은 크기 remainder = chunk_at_offset(victim, nb); // split 한 청크 unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder; // split 하고 남은 청크를 새로운 unsorted bin으로 등록 av->last_remainder = remainder; remainder->bk = remainder->fd = unsorted_chunks(av); // split 하고 남은 청크는 또한 last_remainder 청크가 된다. set_head(victim, nb | PREV_INUSE); set_head(remainder, remainder_size | PREV_INUSE); set_foot(remainder, remainder_size); check_malloced_chunk(victim, nb); // split하여 만든 청크 재할당 retval = chunk2mem(victim); goto DONE; } /* remove from unsorted list */ // 요청크기가 smallbin 크기가 아니거나 // unsorted bin에 여러개의 청크가 있거나 // victim이 last_remainder가 아닐경우 // unsorted bin 탐색에 알맞는 청크 검색이 실패했다는 의미 // unsorted bin에서 제거한다 unsorted_chunks(av)->bk = bck; bck->fd = unsorted_chunks(av); /* Take now instead of binning if exact fit */ // 제거한 거를 일단 처리를 해야하니까 // victim의 크기가 요청 크기와 딱 맞다면 해당 청크 반환 if (size == nb) { set_inuse_bit_at_offset(victim, size); check_malloced_chunk(victim, nb); retval = chunk2mem(victim); goto DONE; } /* place chunk in bin */ // 여기까지 왔다면 unsorted bin의 탐색 실패를 의미. 각자의 bin으로 집어넣기 수행 if (in_smallbin_range(size)) { // smallbin일 경우 smallbin에 넣기 victim_index = smallbin_index(size); bck = bin_at(av, victim_index); fwd = bck->fd; } else {//largebin일 경우 largebin에 넣기 victim_index = __malloc_largebin_index(size); bck = bin_at(av, victim_index); fwd = bck->fd; if (fwd != bck) { /* if smaller than smallest, place first */ //largebin 크기 정렬 수행 if ((unsigned long)(size) < (unsigned long)(bck->bk->size)) { fwd = bck; bck = bck->bk; } else if ((unsigned long)(size) >= (unsigned long)(FIRST_SORTED_BIN_SIZE)) { /* maintain large bins in sorted order */ size |= PREV_INUSE; /* Or with inuse bit to speed comparisons */ while ((unsigned long)(size) < (unsigned long)(fwd->size)) fwd = fwd->fd; bck = fwd->bk; } } } mark_bin(av, victim_index); victim->bk = bck; victim->fd = fwd; fwd->bk = victim; bck->fd = victim; }

/* If a large request, scan through the chunks of current bin to find one that fits. (This will be the smallest that fits unless FIRST_SORTED_BIN_SIZE has been changed from default.) This is the only step where an unbounded number of chunks might be scanned without doing anything useful with them. However the lists tend to be short. */ if (!in_smallbin_range(nb)) { //smallbin 크기가 아니면 largebin에서 검색 bin = bin_at(av, idx); for (victim = last(bin); victim != bin; victim = victim->bk) { size = chunksize(victim); if ((unsigned long)(size) >= (unsigned long)(nb)) { remainder_size = size - nb; unlink(victim, bck, fwd); /* Exhaust */ if (remainder_size < MINSIZE) { set_inuse_bit_at_offset(victim, size); check_malloced_chunk(victim, nb); retval = chunk2mem(victim); goto DONE; } /* Split */ //split하여 남은 청크를 unsortedbin에 삽입 else { remainder = chunk_at_offset(victim, nb); unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder; remainder->bk = remainder->fd = unsorted_chunks(av); set_head(victim, nb | PREV_INUSE); set_head(remainder, remainder_size | PREV_INUSE); set_foot(remainder, remainder_size); check_malloced_chunk(victim, nb); retval = chunk2mem(victim); // 세팅 끝난 청크 반환 goto DONE; } } } }

/* Search for a chunk by scanning bins, starting with next largest bin. This search is strictly by best-fit; i.e., the smallest (with ties going to approximately the least recently used) chunk that fits is selected. The bitmap avoids needing to check that most blocks are nonempty. */ ++idx; bin = bin_at(av,idx); block = idx2block(idx); map = av->binmap[block]; bit = idx2bit(idx); for (;;) { /* Skip rest of block if there are no more set bits in this block. */ if (bit > map || bit == 0) { do { if (++block >= BINMAPSIZE) /* out of bins */ goto use_top; } while ( (map = av->binmap[block]) == 0); bin = bin_at(av, (block << BINMAPSHIFT)); bit = 1; } /* Advance to bin with set bit. There must be one. */ while ((bit & map) == 0) { bin = next_bin(bin); bit <<= 1; assert(bit != 0); } /* Inspect the bin. It is likely to be non-empty */ victim = last(bin); /* If a false alarm (empty bin), clear the bit. */ if (victim == bin) { av->binmap[block] = map &= ~bit; /* Write through */ bin = next_bin(bin); bit <<= 1; } else { size = chunksize(victim); /* We know the first chunk in this bin is big enough to use. */ assert((unsigned long)(size) >= (unsigned long)(nb)); remainder_size = size - nb; /* unlink */ bck = victim->bk; bin->bk = bck; bck->fd = bin; /* Exhaust */ if (remainder_size < MINSIZE) { set_inuse_bit_at_offset(victim, size); check_malloced_chunk(victim, nb); retval = chunk2mem(victim); goto DONE; } /* Split */ else { remainder = chunk_at_offset(victim, nb); unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder; remainder->bk = remainder->fd = unsorted_chunks(av); /* advertise as last remainder */ if (in_smallbin_range(nb)) av->last_remainder = remainder; set_head(victim, nb | PREV_INUSE); set_head(remainder, remainder_size | PREV_INUSE); set_foot(remainder, remainder_size); check_malloced_chunk(victim, nb); retval = chunk2mem(victim); goto DONE; } } }

use_top: /* If large enough, split off the chunk bordering the end of memory (held in av->top). Note that this is in accord with the best-fit search rule. In effect, av->top is treated as larger (and thus less well fitting) than any other available chunk since it can be extended to be as large as necessary (up to system limitations). We require that av->top always exists (i.e., has size >= MINSIZE) after initialization, so if it would otherwise be exhuasted by current request, it is replenished. (The main reason for ensuring it exists is that we may need MINSIZE space to put in fenceposts in sysmalloc.) */ victim = av->top; size = chunksize(victim); if ((unsigned long)(size) >= (unsigned long)(nb + MINSIZE)) { remainder_size = size - nb; remainder = chunk_at_offset(victim, nb); av->top = remainder; set_head(victim, nb | PREV_INUSE); set_head(remainder, remainder_size | PREV_INUSE); check_malloced_chunk(victim, nb); retval = chunk2mem(victim); goto DONE; } /* If no space in top, relay to handle system-dependent cases */ sysmem = __malloc_alloc(nb, av); retval = sysmem; DONE: __MALLOC_UNLOCK; return retval;