1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168 |
- #include "malloc.h"
- __UCLIBC_MUTEX_INIT(__malloc_lock, PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP);
- struct malloc_state __malloc_state;
- static int __malloc_largebin_index(unsigned int sz);
- #ifdef __UCLIBC_MALLOC_DEBUGGING__
- void __do_check_chunk(mchunkptr p)
- {
- mstate av = get_malloc_state();
- #ifdef __DOASSERTS__
-
- char* max_address = (char*)(av->top) + chunksize(av->top);
- char* min_address = max_address - av->sbrked_mem;
- unsigned long sz = chunksize(p);
- #endif
- if (!chunk_is_mmapped(p)) {
-
- if (p != av->top) {
- if (contiguous(av)) {
- assert(((char*)p) >= min_address);
- assert(((char*)p + sz) <= ((char*)(av->top)));
- }
- }
- else {
-
- assert((unsigned long)(sz) >= MINSIZE);
-
- assert(prev_inuse(p));
- }
- }
- else {
-
- if (contiguous(av) && av->top != initial_top(av)) {
- assert(((char*)p) < min_address || ((char*)p) > max_address);
- }
-
- assert(((p->prev_size + sz) & (av->pagesize-1)) == 0);
-
- assert(aligned_OK(chunk2mem(p)));
- }
- }
- void __do_check_free_chunk(mchunkptr p)
- {
- size_t sz = p->size & ~PREV_INUSE;
- #ifdef __DOASSERTS__
- mstate av = get_malloc_state();
- mchunkptr next = chunk_at_offset(p, sz);
- #endif
- __do_check_chunk(p);
-
- assert(!inuse(p));
- assert (!chunk_is_mmapped(p));
-
- if ((unsigned long)(sz) >= MINSIZE)
- {
- assert((sz & MALLOC_ALIGN_MASK) == 0);
- assert(aligned_OK(chunk2mem(p)));
-
- assert(next->prev_size == sz);
-
- assert(prev_inuse(p));
- assert (next == av->top || inuse(next));
-
- assert(p->fd->bk == p);
- assert(p->bk->fd == p);
- }
- else
- assert(sz == (sizeof(size_t)));
- }
- void __do_check_inuse_chunk(mchunkptr p)
- {
- mstate av = get_malloc_state();
- mchunkptr next;
- __do_check_chunk(p);
- if (chunk_is_mmapped(p))
- return;
-
- assert(inuse(p));
- next = next_chunk(p);
-
- if (!prev_inuse(p)) {
-
- mchunkptr prv = prev_chunk(p);
- assert(next_chunk(prv) == p);
- __do_check_free_chunk(prv);
- }
- if (next == av->top) {
- assert(prev_inuse(next));
- assert(chunksize(next) >= MINSIZE);
- }
- else if (!inuse(next))
- __do_check_free_chunk(next);
- }
- void __do_check_remalloced_chunk(mchunkptr p, size_t s)
- {
- #ifdef __DOASSERTS__
- size_t sz = p->size & ~PREV_INUSE;
- #endif
- __do_check_inuse_chunk(p);
-
- assert((sz & MALLOC_ALIGN_MASK) == 0);
- assert((unsigned long)(sz) >= MINSIZE);
-
- assert(aligned_OK(chunk2mem(p)));
-
- assert((long)(sz) - (long)(s) >= 0);
- assert((long)(sz) - (long)(s + MINSIZE) < 0);
- }
- void __do_check_malloced_chunk(mchunkptr p, size_t s)
- {
-
- __do_check_remalloced_chunk(p, s);
-
- assert(prev_inuse(p));
- }
- void __do_check_malloc_state(void)
- {
- mstate av = get_malloc_state();
- int i;
- mchunkptr p;
- mchunkptr q;
- mbinptr b;
- unsigned int binbit;
- int empty;
- unsigned int idx;
- size_t size;
- unsigned long total = 0;
- int max_fast_bin;
-
- assert(sizeof(size_t) <= sizeof(char*));
-
- assert((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-1)) == 0);
-
- if (av->top == 0 || av->top == initial_top(av))
- return;
-
- assert((av->pagesize & (av->pagesize-1)) == 0);
-
-
- assert(get_max_fast(av) <= request2size(MAX_FAST_SIZE));
- max_fast_bin = fastbin_index(av->max_fast);
- for (i = 0; i < NFASTBINS; ++i) {
- p = av->fastbins[i];
-
- if (i > max_fast_bin)
- assert(p == 0);
- while (p != 0) {
-
- __do_check_inuse_chunk(p);
- total += chunksize(p);
-
- assert(fastbin_index(chunksize(p)) == i);
- p = p->fd;
- }
- }
- if (total != 0)
- assert(have_fastchunks(av));
- else if (!have_fastchunks(av))
- assert(total == 0);
-
- for (i = 1; i < NBINS; ++i) {
- b = bin_at(av,i);
-
- if (i >= 2) {
- binbit = get_binmap(av,i);
- empty = last(b) == b;
- if (!binbit)
- assert(empty);
- else if (!empty)
- assert(binbit);
- }
- for (p = last(b); p != b; p = p->bk) {
-
- __do_check_free_chunk(p);
- size = chunksize(p);
- total += size;
- if (i >= 2) {
-
- idx = bin_index(size);
- assert(idx == i);
-
- if ((unsigned long) size >= (unsigned long)(FIRST_SORTED_BIN_SIZE)) {
- assert(p->bk == b ||
- (unsigned long)chunksize(p->bk) >=
- (unsigned long)chunksize(p));
- }
- }
-
- for (q = next_chunk(p);
- (q != av->top && inuse(q) &&
- (unsigned long)(chunksize(q)) >= MINSIZE);
- q = next_chunk(q))
- __do_check_inuse_chunk(q);
- }
- }
-
- __do_check_chunk(av->top);
-
- assert(total <= (unsigned long)(av->max_total_mem));
- assert(av->n_mmaps >= 0);
- assert(av->n_mmaps <= av->max_n_mmaps);
- assert((unsigned long)(av->sbrked_mem) <=
- (unsigned long)(av->max_sbrked_mem));
- assert((unsigned long)(av->mmapped_mem) <=
- (unsigned long)(av->max_mmapped_mem));
- assert((unsigned long)(av->max_total_mem) >=
- (unsigned long)(av->mmapped_mem) + (unsigned long)(av->sbrked_mem));
- }
- #endif
- static void* __malloc_alloc(size_t nb, mstate av)
- {
- mchunkptr old_top;
- size_t old_size;
- char* old_end;
- long size;
- char* fst_brk;
- long correction;
- char* snd_brk;
- size_t front_misalign;
- size_t end_misalign;
- char* aligned_brk;
- mchunkptr p;
- mchunkptr remainder;
- unsigned long remainder_size;
- unsigned long sum;
- size_t pagemask = av->pagesize - 1;
-
- if (have_fastchunks(av)) {
- assert(in_smallbin_range(nb));
- __malloc_consolidate(av);
- return malloc(nb - MALLOC_ALIGN_MASK);
- }
-
- if ((unsigned long)(nb) >= (unsigned long)(av->mmap_threshold) &&
- (av->n_mmaps < av->n_mmaps_max)) {
- char* mm;
-
- size = (nb + (sizeof(size_t)) + MALLOC_ALIGN_MASK + pagemask) & ~pagemask;
-
- if ((unsigned long)(size) > (unsigned long)(nb)) {
- mm = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE));
- if (mm != (char*)(MORECORE_FAILURE)) {
-
- front_misalign = (size_t)chunk2mem(mm) & MALLOC_ALIGN_MASK;
- if (front_misalign > 0) {
- correction = MALLOC_ALIGNMENT - front_misalign;
- p = (mchunkptr)(mm + correction);
- p->prev_size = correction;
- set_head(p, (size - correction) |IS_MMAPPED);
- }
- else {
- p = (mchunkptr)mm;
- p->prev_size = 0;
- set_head(p, size|IS_MMAPPED);
- }
-
- if (++av->n_mmaps > av->max_n_mmaps)
- av->max_n_mmaps = av->n_mmaps;
- sum = av->mmapped_mem += size;
- if (sum > (unsigned long)(av->max_mmapped_mem))
- av->max_mmapped_mem = sum;
- sum += av->sbrked_mem;
- if (sum > (unsigned long)(av->max_total_mem))
- av->max_total_mem = sum;
- check_chunk(p);
- return chunk2mem(p);
- }
- }
- }
-
- old_top = av->top;
- old_size = chunksize(old_top);
- old_end = (char*)(chunk_at_offset(old_top, old_size));
- fst_brk = snd_brk = (char*)(MORECORE_FAILURE);
-
- assert((old_top == initial_top(av) && old_size == 0) ||
- ((unsigned long) (old_size) >= MINSIZE &&
- prev_inuse(old_top)));
-
- assert((unsigned long)(old_size) < (unsigned long)(nb + MINSIZE));
-
- assert(!have_fastchunks(av));
-
- size = nb + av->top_pad + MINSIZE;
-
- if (contiguous(av))
- size -= old_size;
-
- size = (size + pagemask) & ~pagemask;
-
- if (size > 0)
- fst_brk = (char*)(MORECORE(size));
-
- if (fst_brk == (char*)(MORECORE_FAILURE)) {
-
- if (contiguous(av))
- size = (size + old_size + pagemask) & ~pagemask;
-
- if ((unsigned long)(size) < (unsigned long)(MMAP_AS_MORECORE_SIZE))
- size = MMAP_AS_MORECORE_SIZE;
-
- if ((unsigned long)(size) > (unsigned long)(nb)) {
- fst_brk = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE));
- if (fst_brk != (char*)(MORECORE_FAILURE)) {
-
- snd_brk = fst_brk + size;
-
- set_noncontiguous(av);
- }
- }
- }
- if (fst_brk != (char*)(MORECORE_FAILURE)) {
- av->sbrked_mem += size;
-
- if (fst_brk == old_end && snd_brk == (char*)(MORECORE_FAILURE)) {
- set_head(old_top, (size + old_size) | PREV_INUSE);
- }
-
- else {
- front_misalign = 0;
- end_misalign = 0;
- correction = 0;
- aligned_brk = fst_brk;
-
- if (contiguous(av) && old_size != 0 && fst_brk < old_end) {
- set_noncontiguous(av);
- }
-
- if (contiguous(av)) {
-
- if (old_size != 0)
- av->sbrked_mem += fst_brk - old_end;
-
- front_misalign = (size_t)chunk2mem(fst_brk) & MALLOC_ALIGN_MASK;
- if (front_misalign > 0) {
-
- correction = MALLOC_ALIGNMENT - front_misalign;
- aligned_brk += correction;
- }
-
- correction += old_size;
-
- end_misalign = (size_t)(fst_brk + size + correction);
- correction += ((end_misalign + pagemask) & ~pagemask) - end_misalign;
- assert(correction >= 0);
- snd_brk = (char*)(MORECORE(correction));
- if (snd_brk == (char*)(MORECORE_FAILURE)) {
-
- correction = 0;
- snd_brk = (char*)(MORECORE(0));
- }
- else if (snd_brk < fst_brk) {
-
- snd_brk = fst_brk + size;
- correction = 0;
- set_noncontiguous(av);
- }
- }
-
- else {
-
- assert(aligned_OK(chunk2mem(fst_brk)));
-
- if (snd_brk == (char*)(MORECORE_FAILURE)) {
- snd_brk = (char*)(MORECORE(0));
- av->sbrked_mem += snd_brk - fst_brk - size;
- }
- }
-
- if (snd_brk != (char*)(MORECORE_FAILURE)) {
- av->top = (mchunkptr)aligned_brk;
- set_head(av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
- av->sbrked_mem += correction;
-
- if (old_size != 0) {
-
- old_size = (old_size - 3*(sizeof(size_t))) & ~MALLOC_ALIGN_MASK;
- set_head(old_top, old_size | PREV_INUSE);
-
- chunk_at_offset(old_top, old_size )->size =
- (sizeof(size_t))|PREV_INUSE;
- chunk_at_offset(old_top, old_size + (sizeof(size_t)))->size =
- (sizeof(size_t))|PREV_INUSE;
-
- if (old_size >= MINSIZE) {
- size_t tt = av->trim_threshold;
- av->trim_threshold = (size_t)(-1);
- free(chunk2mem(old_top));
- av->trim_threshold = tt;
- }
- }
- }
- }
-
- sum = av->sbrked_mem;
- if (sum > (unsigned long)(av->max_sbrked_mem))
- av->max_sbrked_mem = sum;
- sum += av->mmapped_mem;
- if (sum > (unsigned long)(av->max_total_mem))
- av->max_total_mem = sum;
- check_malloc_state();
-
- p = av->top;
- size = chunksize(p);
-
- if ((unsigned long)(size) >= (unsigned long)(nb + MINSIZE)) {
- remainder_size = size - nb;
- remainder = chunk_at_offset(p, nb);
- av->top = remainder;
- set_head(p, nb | PREV_INUSE);
- set_head(remainder, remainder_size | PREV_INUSE);
- check_malloced_chunk(p, nb);
- return chunk2mem(p);
- }
- }
-
- __set_errno(ENOMEM);
- return 0;
- }
- static int __malloc_largebin_index(unsigned int sz)
- {
- unsigned int x = sz >> SMALLBIN_WIDTH;
- unsigned int m;
- if (x >= 0x10000) return NBINS-1;
-
- #if defined(__GNUC__) && defined(i386)
- __asm__("bsrl %1,%0\n\t"
- : "=r" (m)
- : "g" (x));
- #else
- {
-
- unsigned int n = ((x - 0x100) >> 16) & 8;
- x <<= n;
- m = ((x - 0x1000) >> 16) & 4;
- n += m;
- x <<= m;
- m = ((x - 0x4000) >> 16) & 2;
- n += m;
- x = (x << m) >> 14;
- m = 13 - n + (x & ~(x>>1));
- }
- #endif
-
- return NSMALLBINS + (m << 2) + ((sz >> (m + 6)) & 3);
- }
- void* malloc(size_t bytes)
- {
- mstate av;
- size_t nb;
- unsigned int idx;
- mbinptr bin;
- mfastbinptr* fb;
- mchunkptr victim;
- size_t size;
- int victim_index;
- mchunkptr remainder;
- unsigned long remainder_size;
- unsigned int block;
- unsigned int bit;
- unsigned int map;
- mchunkptr fwd;
- mchunkptr bck;
- void * sysmem;
- void * retval;
- #if !defined(__MALLOC_GLIBC_COMPAT__)
- if (!bytes) {
- __set_errno(ENOMEM);
- return NULL;
- }
- #endif
-
- checked_request2size(bytes, nb);
- __MALLOC_LOCK;
- av = get_malloc_state();
-
- if (!have_anychunks(av)) {
- if (av->max_fast == 0)
- __malloc_consolidate(av);
- goto use_top;
- }
-
- if ((unsigned long)(nb) <= (unsigned long)(av->max_fast)) {
- fb = &(av->fastbins[(fastbin_index(nb))]);
- if ( (victim = *fb) != 0) {
- *fb = victim->fd;
- check_remalloced_chunk(victim, nb);
- retval = chunk2mem(victim);
- goto DONE;
- }
- }
-
- if (in_smallbin_range(nb)) {
- idx = smallbin_index(nb);
- bin = bin_at(av,idx);
- if ( (victim = last(bin)) != bin) {
- bck = victim->bk;
- set_inuse_bit_at_offset(victim, nb);
- bin->bk = bck;
- bck->fd = bin;
- check_malloced_chunk(victim, nb);
- retval = chunk2mem(victim);
- goto DONE;
- }
- }
-
- else {
- idx = __malloc_largebin_index(nb);
- if (have_fastchunks(av))
- __malloc_consolidate(av);
- }
-
- while ( (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {
- bck = victim->bk;
- size = chunksize(victim);
-
- if (in_smallbin_range(nb) &&
- bck == unsorted_chunks(av) &&
- victim == av->last_remainder &&
- (unsigned long)(size) > (unsigned long)(nb + MINSIZE)) {
-
- remainder_size = size - nb;
- remainder = chunk_at_offset(victim, nb);
- unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
- av->last_remainder = 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;
- }
-
- unsorted_chunks(av)->bk = bck;
- bck->fd = unsorted_chunks(av);
-
- if (size == nb) {
- set_inuse_bit_at_offset(victim, size);
- check_malloced_chunk(victim, nb);
- retval = chunk2mem(victim);
- goto DONE;
- }
-
- if (in_smallbin_range(size)) {
- victim_index = smallbin_index(size);
- bck = bin_at(av, victim_index);
- fwd = bck->fd;
- }
- else {
- victim_index = __malloc_largebin_index(size);
- bck = bin_at(av, victim_index);
- fwd = bck->fd;
- if (fwd != bck) {
-
- 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)) {
-
- size |= PREV_INUSE;
- 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 (!in_smallbin_range(nb)) {
- 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);
-
- if (remainder_size < MINSIZE) {
- set_inuse_bit_at_offset(victim, size);
- check_malloced_chunk(victim, nb);
- retval = chunk2mem(victim);
- goto DONE;
- }
-
- 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;
- }
- }
- }
- }
-
- ++idx;
- bin = bin_at(av,idx);
- block = idx2block(idx);
- map = av->binmap[block];
- bit = idx2bit(idx);
- for (;;) {
-
- if (bit > map || bit == 0) {
- do {
- if (++block >= BINMAPSIZE)
- goto use_top;
- } while ( (map = av->binmap[block]) == 0);
- bin = bin_at(av, (block << BINMAPSHIFT));
- bit = 1;
- }
-
- while ((bit & map) == 0) {
- bin = next_bin(bin);
- bit <<= 1;
- assert(bit != 0);
- }
-
- victim = last(bin);
-
- if (victim == bin) {
- av->binmap[block] = map &= ~bit;
- bin = next_bin(bin);
- bit <<= 1;
- }
- else {
- size = chunksize(victim);
-
- assert((unsigned long)(size) >= (unsigned long)(nb));
- remainder_size = size - nb;
-
- bck = victim->bk;
- bin->bk = bck;
- bck->fd = bin;
-
- if (remainder_size < MINSIZE) {
- set_inuse_bit_at_offset(victim, size);
- check_malloced_chunk(victim, nb);
- retval = chunk2mem(victim);
- goto DONE;
- }
-
- else {
- remainder = chunk_at_offset(victim, nb);
- unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
- remainder->bk = remainder->fd = unsorted_chunks(av);
-
- 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:
-
- 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;
- }
-
- sysmem = __malloc_alloc(nb, av);
- retval = sysmem;
- DONE:
- __MALLOC_UNLOCK;
- return retval;
- }
|