microscheme/malloc.c

/*
 * malloc/free by O.Dreesen
 *
 * first TRY:
 *   lists w/magics
 * and now the second TRY
 *   let the kernel map all the stuff (if there is something to do)
 */

#include <unistd.h>
#include <sys/mman.h>
#include <errno.h>

#include <sys/types.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

#include <limits.h>
//#include <sys/shm.h>  /* for PAGE_SIZE */

#ifndef PAGE_SIZE
 #define PAGE_SIZE sysconf (_SC_PAGESIZE)
#endif

#ifndef MREMAP_MAYMOVE
 #define MREMAP_MAYMOVE 1
#endif

/* -- HELPER CODE --------------------------------------------------------- */

#ifndef MAP_FAILED
#define MAP_FAILED ((void*)-1)
#endif

#ifndef NULL
#define NULL ((void*)0)
#endif

typedef struct {
  void*  next;
  size_t size;
} alloc_t;

#define BLOCK_START(b)  (((void*)(b))-sizeof(alloc_t))
#define BLOCK_RET(b)    (((void*)(b))+sizeof(alloc_t))

#define MEM_BLOCK_SIZE  PAGE_SIZE
#define PAGE_ALIGN(s)   (((s)+MEM_BLOCK_SIZE-1)&(unsigned long)(~(MEM_BLOCK_SIZE-1)))

/* a simple mmap :) */
#if defined(i386)
#define REGPARM(x) attribute((regparm(x)))
#else
#define REGPARM(x)
#endif

static void REGPARM(1) *do_mmap(size_t size) {
  return mmap(0, size, PROT_READ|PROT_WRITE, MAP_ANONYMOUS|MAP_PRIVATE, -1, (size_t)0);
}

/* -- SMALL MEM ----------------------------------------------------------- */

static alloc_t* small_mem[8];

#define SMALL_NR(i)             (MEM_BLOCK_SIZE/(i))

#define MIN_SMALL_SIZE  SMALL_NR(256)           /*   16 /   32 */
#define MAX_SMALL_SIZE  SMALL_NR(2)             /* 2048 / 4096 */

#define GET_SIZE(s)             (MIN_SMALL_SIZE<<get_index((s)))

#define FIRST_SMALL(p)          (((unsigned long)(p))&(~(MEM_BLOCK_SIZE-1)))

static inline int ind_shift() { return (MEM_BLOCK_SIZE==4096)?4:5; }

static size_t REGPARM(1) get_index(size_t _size) {
  register size_t idx=0;
//  if (_size) {        /* we already check this in the callers */
    register size_t size=((_size-1)&(MEM_BLOCK_SIZE-1))>>ind_shift();
    while(size) { size>>=1; ++idx; }
//  }
  return idx;
}

/* small mem */
static void small_free(void*_ptr,size_t _size) REGPARM(2);

static void REGPARM(2) small_free(void*_ptr,size_t _size) {
  alloc_t* ptr=BLOCK_START(_ptr);
  size_t size=_size;
  size_t idx=get_index(size);

#ifdef WANT_FREE_OVERWRITE
  memset(ptr,0x55,size);        /* allways zero out small mem */
#else
#if 0
  memset(ptr,0,size);   /* allways zero out small mem */
#endif
#endif

  ptr->next=small_mem[idx];
  small_mem[idx]=ptr;
}

static void* REGPARM(1) small_malloc(size_t _size) {
  alloc_t *ptr;
  size_t size=_size;
  size_t idx;

  idx=get_index(size);
  ptr=small_mem[idx];

  if (ptr==0)  {        /* no free blocks ? */
    register int i,nr;
    ptr=do_mmap(MEM_BLOCK_SIZE);
    if (ptr==MAP_FAILED) return MAP_FAILED;

    small_mem[idx]=ptr;

    nr=SMALL_NR(size)-1;
    for (i=0;i<nr;i++) {
      ptr->next=(((void*)ptr)+size);
      ptr=ptr->next;
    }
    ptr->next=0;

    ptr=small_mem[idx];
  }

  /* get a free block */
  small_mem[idx]=ptr->next;
  ptr->next=0;

  return ptr;
}

/* -- PUBLIC FUNCTIONS ---------------------------------------------------- */

void tiny_free(void *ptr) {
  register size_t size;
  if (ptr) {
    size=((alloc_t*)BLOCK_START(ptr))->size;
    if (size) {
      if (size<=MAX_SMALL_SIZE)
        small_free(ptr,size);
      else
        munmap(BLOCK_START(ptr),size);
    }
  }
}

void* tiny_malloc(size_t size) {
  alloc_t* ptr;
  size_t need;
  if (!size) goto err_out;
  size+=sizeof(alloc_t);
  if (size<sizeof(alloc_t)) goto err_out;
  if (size<=MAX_SMALL_SIZE) {
    need=GET_SIZE(size);
    ptr=small_malloc(need);
  }
  else {
    need=PAGE_ALIGN(size);
    if (!need) ptr=MAP_FAILED; else ptr=do_mmap(need);
  }
  if (ptr==MAP_FAILED) goto err_out;
  ptr->size=need;
  return BLOCK_RET(ptr);
err_out:
  //(*errno_location())=ENOMEM;
  return 0;
}

#if 0
void* tiny_calloc(size_t nmemb, size_t _size) {
  register size_t size=_size*nmemb;
  if (nmemb && size/nmemb!=_size) {
    //(*errno_location())=ENOMEM;
    return 0;
  }
#ifdef WANT_FREE_OVERWRITE
  if (size<MAX_SMALL_SIZE) {
    void* x=malloc(size);
    memset(x,0,size);
    return x;
  } else
#endif
  return malloc(size);
}
#endif

void* tiny_realloc(void* ptr, size_t _size) {
  register size_t size=_size;
  if (ptr) {
    if (size) {
      alloc_t* tmp=BLOCK_START(ptr);
      size+=sizeof(alloc_t);
      if (size<sizeof(alloc_t)) goto retzero;
      size=(size<=MAX_SMALL_SIZE)?GET_SIZE(size):PAGE_ALIGN(size);
      if (tmp->size!=size) {
        if ((tmp->size<=MAX_SMALL_SIZE)) {
          void *new=malloc(_size);
          if (new) {
            register alloc_t* foo=BLOCK_START(new);
            size=foo->size;
            if (size>tmp->size) size=tmp->size;
            if (size) memcpy(new,ptr,size-sizeof(alloc_t));
            free(ptr);
          }
          ptr=new;
        }
        else {
          register alloc_t* foo;
          size=PAGE_ALIGN(size);
          foo=mremap(tmp,tmp->size,size,MREMAP_MAYMOVE);
          if (foo==MAP_FAILED) {
retzero:
            //(*errno_location())=ENOMEM;
            ptr=0;
          }
          else {
            foo->size=size;
            ptr=BLOCK_RET(foo);
          }
        }
      }
    }
    else { /* size==0 */
      free(ptr);
      ptr = NULL;
    }
  }
  else { /* ptr==0 */
    if (size) {
      ptr=malloc(size);
    }
  }
  return ptr;
}

Revision:	1.2
Committed:	Wed Dec 2 07:43:46 2015 UTC (8 years, 6 months ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.1:	+50 -50 lines
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	/*
2			* malloc/free by O.Dreesen
3			*
4			* first TRY:
5			* lists w/magics
6			* and now the second TRY
7			* let the kernel map all the stuff (if there is something to do)
8			*/
9
10			#include <unistd.h>
11			#include <sys/mman.h>
12			#include <errno.h>
13
14			#include <sys/types.h>
15			#include <stddef.h>
16			#include <stdlib.h>
17			#include <string.h>
18
19			#include <limits.h>
20			//#include <sys/shm.h> /* for PAGE_SIZE */
21
22			#ifndef PAGE_SIZE
23			#define PAGE_SIZE sysconf (_SC_PAGESIZE)
24			#endif
25
26			#ifndef MREMAP_MAYMOVE
27			#define MREMAP_MAYMOVE 1
28			#endif
29
30			/* -- HELPER CODE --------------------------------------------------------- */
31
32			#ifndef MAP_FAILED
33			#define MAP_FAILED ((void*)-1)
34			#endif
35
36			#ifndef NULL
37			#define NULL ((void*)0)
38			#endif
39
40			typedef struct {
41			void* next;
42			size_t size;
43	root	1.2	} alloc_t;
44	root	1.1
45	root	1.2	#define BLOCK_START(b) (((void*)(b))-sizeof(alloc_t))
46			#define BLOCK_RET(b) (((void*)(b))+sizeof(alloc_t))
47	root	1.1
48			#define MEM_BLOCK_SIZE PAGE_SIZE
49			#define PAGE_ALIGN(s) (((s)+MEM_BLOCK_SIZE-1)&(unsigned long)(~(MEM_BLOCK_SIZE-1)))
50
51			/* a simple mmap :) */
52	root	1.2	#if defined(i386)
53			#define REGPARM(x) attribute((regparm(x)))
54	root	1.1	#else
55			#define REGPARM(x)
56			#endif
57
58			static void REGPARM(1) *do_mmap(size_t size) {
59			return mmap(0, size, PROT_READ\|PROT_WRITE, MAP_ANONYMOUS\|MAP_PRIVATE, -1, (size_t)0);
60			}
61
62			/* -- SMALL MEM ----------------------------------------------------------- */
63
64	root	1.2	static alloc_t* small_mem[8];
65	root	1.1
66	root	1.2	#define SMALL_NR(i) (MEM_BLOCK_SIZE/(i))
67	root	1.1
68	root	1.2	#define MIN_SMALL_SIZE SMALL_NR(256) /* 16 / 32 */
69			#define MAX_SMALL_SIZE SMALL_NR(2) /* 2048 / 4096 */
70	root	1.1
71	root	1.2	#define GET_SIZE(s) (MIN_SMALL_SIZE<<get_index((s)))
72	root	1.1
73			#define FIRST_SMALL(p) (((unsigned long)(p))&(~(MEM_BLOCK_SIZE-1)))
74
75	root	1.2	static inline int ind_shift() { return (MEM_BLOCK_SIZE==4096)?4:5; }
76	root	1.1
77			static size_t REGPARM(1) get_index(size_t _size) {
78			register size_t idx=0;
79			// if (_size) { /* we already check this in the callers */
80	root	1.2	register size_t size=((_size-1)&(MEM_BLOCK_SIZE-1))>>ind_shift();
81	root	1.1	while(size) { size>>=1; ++idx; }
82			// }
83			return idx;
84			}
85
86			/* small mem */
87	root	1.2	static void small_free(void*_ptr,size_t _size) REGPARM(2);
88	root	1.1
89	root	1.2	static void REGPARM(2) small_free(void*_ptr,size_t _size) {
90			alloc_t* ptr=BLOCK_START(_ptr);
91	root	1.1	size_t size=_size;
92			size_t idx=get_index(size);
93
94			#ifdef WANT_FREE_OVERWRITE
95			memset(ptr,0x55,size); /* allways zero out small mem */
96			#else
97			#if 0
98			memset(ptr,0,size); /* allways zero out small mem */
99			#endif
100			#endif
101
102	root	1.2	ptr->next=small_mem[idx];
103			small_mem[idx]=ptr;
104	root	1.1	}
105
106	root	1.2	static void* REGPARM(1) small_malloc(size_t _size) {
107			alloc_t *ptr;
108	root	1.1	size_t size=_size;
109			size_t idx;
110
111			idx=get_index(size);
112	root	1.2	ptr=small_mem[idx];
113	root	1.1
114			if (ptr==0) { /* no free blocks ? */
115			register int i,nr;
116			ptr=do_mmap(MEM_BLOCK_SIZE);
117			if (ptr==MAP_FAILED) return MAP_FAILED;
118
119	root	1.2	small_mem[idx]=ptr;
120	root	1.1
121	root	1.2	nr=SMALL_NR(size)-1;
122	root	1.1	for (i=0;i<nr;i++) {
123			ptr->next=(((void*)ptr)+size);
124			ptr=ptr->next;
125			}
126			ptr->next=0;
127
128	root	1.2	ptr=small_mem[idx];
129	root	1.1	}
130
131			/* get a free block */
132	root	1.2	small_mem[idx]=ptr->next;
133	root	1.1	ptr->next=0;
134
135			return ptr;
136			}
137
138			/* -- PUBLIC FUNCTIONS ---------------------------------------------------- */
139
140	root	1.2	void tiny_free(void *ptr) {
141	root	1.1	register size_t size;
142			if (ptr) {
143	root	1.2	size=((alloc_t*)BLOCK_START(ptr))->size;
144	root	1.1	if (size) {
145	root	1.2	if (size<=MAX_SMALL_SIZE)
146			small_free(ptr,size);
147	root	1.1	else
148			munmap(BLOCK_START(ptr),size);
149			}
150			}
151			}
152
153	root	1.2	void* tiny_malloc(size_t size) {
154			alloc_t* ptr;
155	root	1.1	size_t need;
156			if (!size) goto err_out;
157	root	1.2	size+=sizeof(alloc_t);
158			if (size<sizeof(alloc_t)) goto err_out;
159			if (size<=MAX_SMALL_SIZE) {
160	root	1.1	need=GET_SIZE(size);
161	root	1.2	ptr=small_malloc(need);
162	root	1.1	}
163			else {
164			need=PAGE_ALIGN(size);
165			if (!need) ptr=MAP_FAILED; else ptr=do_mmap(need);
166			}
167			if (ptr==MAP_FAILED) goto err_out;
168			ptr->size=need;
169			return BLOCK_RET(ptr);
170			err_out:
171	root	1.2	//(*errno_location())=ENOMEM;
172	root	1.1	return 0;
173			}
174
175	root	1.2	#if 0
176			void* tiny_calloc(size_t nmemb, size_t _size) {
177	root	1.1	register size_t size=_size*nmemb;
178			if (nmemb && size/nmemb!=_size) {
179	root	1.2	//(*errno_location())=ENOMEM;
180	root	1.1	return 0;
181			}
182			#ifdef WANT_FREE_OVERWRITE
183	root	1.2	if (size<MAX_SMALL_SIZE) {
184	root	1.1	void* x=malloc(size);
185			memset(x,0,size);
186			return x;
187			} else
188			#endif
189			return malloc(size);
190			}
191	root	1.2	#endif
192	root	1.1
193	root	1.2	void* tiny_realloc(void* ptr, size_t _size) {
194	root	1.1	register size_t size=_size;
195			if (ptr) {
196			if (size) {
197	root	1.2	alloc_t* tmp=BLOCK_START(ptr);
198			size+=sizeof(alloc_t);
199			if (size<sizeof(alloc_t)) goto retzero;
200			size=(size<=MAX_SMALL_SIZE)?GET_SIZE(size):PAGE_ALIGN(size);
201	root	1.1	if (tmp->size!=size) {
202	root	1.2	if ((tmp->size<=MAX_SMALL_SIZE)) {
203	root	1.1	void *new=malloc(_size);
204			if (new) {
205	root	1.2	register alloc_t* foo=BLOCK_START(new);
206	root	1.1	size=foo->size;
207			if (size>tmp->size) size=tmp->size;
208	root	1.2	if (size) memcpy(new,ptr,size-sizeof(alloc_t));
209	root	1.1	free(ptr);
210			}
211			ptr=new;
212			}
213			else {
214	root	1.2	register alloc_t* foo;
215	root	1.1	size=PAGE_ALIGN(size);
216			foo=mremap(tmp,tmp->size,size,MREMAP_MAYMOVE);
217			if (foo==MAP_FAILED) {
218			retzero:
219	root	1.2	//(*errno_location())=ENOMEM;
220	root	1.1	ptr=0;
221			}
222			else {
223			foo->size=size;
224			ptr=BLOCK_RET(foo);
225			}
226			}
227			}
228			}
229			else { /* size==0 */
230			free(ptr);
231			ptr = NULL;
232			}
233			}
234			else { /* ptr==0 */
235			if (size) {
236			ptr=malloc(size);
237			}
238			}
239			return ptr;
240			}
241