/* mem.c -- light-weighted memory allocator Copyright (c) 2007, Heng Li This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #include #include #include /* #include "mem.h" */ /* The whole thing is: ("@" for the KR_HEADER of the block, "-" for free memory, and "+" for allocated memory. One char for one unit.) * * This region is core 1. This region is core 2. * * @-------@++++++@++++++++++++@------------ @----------@++++++++++++@+++++++@------------ * | | | | * p=p->ptr->ptr->ptr->ptr p->ptr p->ptr->ptr p->ptr->ptr->ptr */ #ifndef kr_size(x) #define kr_size(x) ((((KR_HEADER*)(x))-1)->size * sizeof(KR_HEADER)) #endif typedef struct _KR_HEADER_ { struct _KR_HEADER_ *ptr; /* next free block */ size_t size; /* size of current free block */ } KR_HEADER; static KR_HEADER base; static KR_HEADER *loop_head = 0; /* the last and also the first free block */ static size_t kr_total_allocated = 0, kr_n_core = 0; void kr_error(const char *s) { fprintf(stderr, "FATAL MEMORY PROBLEM: %s\n", s); exit(1); } static KR_HEADER *morecore(size_t nu) { extern float kr_stat(); extern void kr_free(void*); size_t rnu; KR_HEADER *up; rnu = (nu + 0xffff) & (~(size_t)(0xffff)); up = (KR_HEADER*)malloc(rnu * sizeof(KR_HEADER)); if (!up) { /* fail to allocate memory */ kr_stat(); fprintf(stderr, "*morecore* %u bytes requested but not available.\n", rnu * sizeof(KR_HEADER)); exit(1); } kr_total_allocated += rnu * sizeof(KR_HEADER); ++kr_n_core; up->size = rnu; /* the size of the current block, and in this case the block is the same as the new core */ kr_free(up + 1); /* initialize the new "core" */ return loop_head; } void kr_free(void *ap) { KR_HEADER *p, *q; if (!ap) return; p = (KR_HEADER*)ap - 1; /* p->size is the size of the current block */ /* Find the pointer that points to the block to be freed. The following loop can stop on two conditions: * * a) "p>q && pptr": @------@++++++++@+++++++@------- @---------------@+++++++@------- * (can also be in | | | -> | | * two cores) q p q->ptr q q->ptr * * @-------- @+++++++++@-------- @-------- @------------------ * | | | -> | | * q p q->ptr q q->ptr * * b) "q>=q->ptr && (p>q || pptr)": @-------@+++++ @--------@+++++++ @-------@+++++ @---------------- * | | | -> | | * q->ptr q p q->ptr q * * @+++++++@----- @++++++++@------- @------------- @++++++++@------- * | | | -> | | * p q->ptr q q->ptr q */ for (q = loop_head;; q = q->ptr) { if (q < q->ptr) { if (q < p && p < q->ptr) break; } else { if (p > q || p < q->ptr) break; } } if (p + p->size == q->ptr) { /* two adjacent blocks, merge p and q->ptr (the 2nd and 4th cases) */ p->size += q->ptr->size; /* this is the new q->ptr size */ p->ptr = q->ptr->ptr; /* this is the new q->ptr->ptr */ /* p is actually the new q->ptr. The actual change happens a few lines below. */ } else if (p + p->size > q->ptr && q->ptr >= p) { /* the end of the allocated block is in the next free block */ kr_error("*kr_free* The end of the allocated block enters a free block."); } else p->ptr = q->ptr; /* backup q->ptr */ if (q + q->size == p) { /* two adjacent blocks, merge q and p (the other two cases) */ q->size += p->size; q->ptr = p->ptr; } else if (q + q->size > p && p >= q) { /* the end of a free block in the allocated block */ kr_error("*kr_free* The end of a free block enters the allocated block."); } else q->ptr = p; /* in two cores, cannot be merged */ loop_head = q; } void *kr_realloc(void *ap, size_t n_bytes) { extern void *kr_malloc(size_t); KR_HEADER *p, *q; size_t n_units; if (!ap) return kr_malloc(n_bytes); n_units = 1 + (n_bytes + sizeof(KR_HEADER) - 1) / sizeof(KR_HEADER); p = (KR_HEADER*)ap - 1; if (p->size >= n_units) return ap; q = (KR_HEADER*)kr_malloc(n_bytes); memcpy(q, ap, (p->size - 1) * sizeof(KR_HEADER)); kr_free(ap); return q; } void *kr_malloc(size_t n_bytes) { KR_HEADER *p, *q; size_t j, n_units; int i; /* "n_units" means the number of units. The size of one unit equals to sizeof(KR_HEADER). * "1" is the KR_HEADER of a block, which is always required. */ n_units = 1 + (n_bytes + sizeof(KR_HEADER) - 1) / sizeof(KR_HEADER); #ifndef KR_NO_POW2 for (i = 31, j = (size_t)0x80000000L; i >= 0; --i, j >>= 1) if (n_units & j) { n_units = (size_t)1<<(i+1); break; } #endif if (!(q = loop_head)) { /* the first time when kr_malloc() is called, intialization */ base.ptr = loop_head = q = &base; base.size = 0; } for (p = q->ptr;; q = p, p = p->ptr) { /* search for a suitable block */ if (p->size >= n_units) { /* p->size if the size of current block. This line means the current block is large enough. */ if (p->size == n_units) q->ptr = p->ptr; /* no need to split the block */ else { /* split the block */ /* memory is allocated at the end of the block */ p->size -= n_units; /* reduce the size of the free block */ p += p->size; /* skip to the KR_HEADER of the allocated block */ p->size = n_units; /* set the size */ } loop_head = q; /* set the end of chain */ return p + 1; /* skip the KR_HEADER */ } if (p == loop_head) /* then ask for more "cores" */ if (!(p = morecore(n_units))) return 0; /* p==0 if fail to allocate, but morecore() will call exit(1) first */ } } float kr_stat() { unsigned n_blocks, n_units; size_t max_block = 0; KR_HEADER *p, *q; float frag; if (loop_head == 0) { fprintf(stderr, " No memory has been allocated so far."); return 0.0; } p = loop_head; n_blocks = n_units = 0; do { q = p->ptr; if (p->size > max_block) max_block = p->size; n_units += p->size; if (p + p->size > q && q > p) kr_error("*kr_stat* The end of a free block enters another free block."); p = q; ++n_blocks; } while (p != loop_head); --n_blocks; frag = 1.0/1024.0*n_units * sizeof(KR_HEADER)/kr_n_core; fprintf(stderr, " Total=%u, Free=%u, C=%u, B=%u, Max=%u, Frag=%.3fK\n", kr_total_allocated, n_units * sizeof(KR_HEADER), kr_n_core, n_blocks, max_block, frag); return frag; } #ifdef KR_TEST #include #include #include int main() { char **p; int i, j, k, n, m, N, do_alloc; n = 20000; N = 40000; m = 1024; srand48(time(0)); p = (char**)kr_malloc(sizeof(char*) * N); kr_stat(); for (i = 0; i < N; ++i) p[i] = 0; for (i = j = 0; i < N; ++i) { do_alloc = (drand48() < 1.0 - (double)j/n)? 1 : 0; if (j == 0) do_alloc = 1; else if (j == n) do_alloc = 0; if (do_alloc == 1) { if (drand48() > 0.5) { p[j++] = (char*)kr_malloc(sizeof(char) * (int)(m * drand48() + 1.5)); } else { k = (int)(drand48() * j); p[k] = (char*)kr_realloc(p[k], sizeof(char) * (int)(m * (1.0 + drand48()) + 0.5)); if (k == j) ++j; } } else if (do_alloc == 0) { k = (int)(drand48() * j); kr_free(p[k]); p[k] = 0; } if (i != 0 && i % 1000 == 0) kr_stat(); } fprintf(stderr, "%d\n", kr_size(p)); for (i = 0; i < N; ++i) kr_free(p[i]); kr_free(p); kr_stat(); return 0; } #endif /* KR_TEST */