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)
 */

#define _GNU_SOURCE 1

#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 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* 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;
}

void* 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);
}

void* 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.1
Committed:	Sat Nov 28 05:57:08 2015 UTC (8 years, 6 months ago) by root
Content type:	text/plain
Branch:	MAIN
Log Message:	* empty log message *
#	Content
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	#define _GNU_SOURCE 1
11
12	#include <unistd.h>
13	#include <sys/mman.h>
14	#include <errno.h>
15
16	#include <sys/types.h>
17	#include <stddef.h>
18	#include <stdlib.h>
19	#include <string.h>
20
21	#include <limits.h>
22	//#include <sys/shm.h> /* for PAGE_SIZE */
23
24	#ifndef PAGE_SIZE
25	#define PAGE_SIZE sysconf (_SC_PAGESIZE)
26	#endif
27
28	#ifndef MREMAP_MAYMOVE
29	#define MREMAP_MAYMOVE 1
30	#endif
31
32	/* -- HELPER CODE --------------------------------------------------------- */
33
34	#ifndef MAP_FAILED
35	#define MAP_FAILED ((void*)-1)
36	#endif
37
38	#ifndef NULL
39	#define NULL ((void*)0)
40	#endif
41
42	typedef struct {
43	void* next;
44	size_t size;
45	} __alloc_t;
46
47	#define BLOCK_START(b) (((void*)(b))-sizeof(__alloc_t))
48	#define BLOCK_RET(b) (((void*)(b))+sizeof(__alloc_t))
49
50	#define MEM_BLOCK_SIZE PAGE_SIZE
51	#define PAGE_ALIGN(s) (((s)+MEM_BLOCK_SIZE-1)&(unsigned long)(~(MEM_BLOCK_SIZE-1)))
52
53	/* a simple mmap :) */
54	#if defined(__i386__)
55	#define REGPARM(x) __attribute__((regparm(x)))
56	#else
57	#define REGPARM(x)
58	#endif
59
60	static void REGPARM(1) *do_mmap(size_t size) {
61	return mmap(0, size, PROT_READ\|PROT_WRITE, MAP_ANONYMOUS\|MAP_PRIVATE, -1, (size_t)0);
62	}
63
64	/* -- SMALL MEM ----------------------------------------------------------- */
65
66	static __alloc_t* __small_mem[8];
67
68	#define __SMALL_NR(i) (MEM_BLOCK_SIZE/(i))
69
70	#define __MIN_SMALL_SIZE __SMALL_NR(256) /* 16 / 32 */
71	#define __MAX_SMALL_SIZE __SMALL_NR(2) /* 2048 / 4096 */
72
73	#define GET_SIZE(s) (__MIN_SMALL_SIZE<<get_index((s)))
74
75	#define FIRST_SMALL(p) (((unsigned long)(p))&(~(MEM_BLOCK_SIZE-1)))
76
77	static inline int __ind_shift() { return (MEM_BLOCK_SIZE==4096)?4:5; }
78
79	static size_t REGPARM(1) get_index(size_t _size) {
80	register size_t idx=0;
81	// if (_size) { /* we already check this in the callers */
82	register size_t size=((_size-1)&(MEM_BLOCK_SIZE-1))>>__ind_shift();
83	while(size) { size>>=1; ++idx; }
84	// }
85	return idx;
86	}
87
88	/* small mem */
89	static void __small_free(void*_ptr,size_t _size) REGPARM(2);
90
91	static void REGPARM(2) __small_free(void*_ptr,size_t _size) {
92	__alloc_t* ptr=BLOCK_START(_ptr);
93	size_t size=_size;
94	size_t idx=get_index(size);
95
96	#ifdef WANT_FREE_OVERWRITE
97	memset(ptr,0x55,size); /* allways zero out small mem */
98	#else
99	#if 0
100	memset(ptr,0,size); /* allways zero out small mem */
101	#endif
102	#endif
103
104	ptr->next=__small_mem[idx];
105	__small_mem[idx]=ptr;
106	}
107
108	static void* REGPARM(1) __small_malloc(size_t _size) {
109	__alloc_t *ptr;
110	size_t size=_size;
111	size_t idx;
112
113	idx=get_index(size);
114	ptr=__small_mem[idx];
115
116	if (ptr==0) { /* no free blocks ? */
117	register int i,nr;
118	ptr=do_mmap(MEM_BLOCK_SIZE);
119	if (ptr==MAP_FAILED) return MAP_FAILED;
120
121	__small_mem[idx]=ptr;
122
123	nr=__SMALL_NR(size)-1;
124	for (i=0;i<nr;i++) {
125	ptr->next=(((void*)ptr)+size);
126	ptr=ptr->next;
127	}
128	ptr->next=0;
129
130	ptr=__small_mem[idx];
131	}
132
133	/* get a free block */
134	__small_mem[idx]=ptr->next;
135	ptr->next=0;
136
137	return ptr;
138	}
139
140	/* -- PUBLIC FUNCTIONS ---------------------------------------------------- */
141
142	void free(void *ptr) {
143	register size_t size;
144	if (ptr) {
145	size=((__alloc_t*)BLOCK_START(ptr))->size;
146	if (size) {
147	if (size<=__MAX_SMALL_SIZE)
148	__small_free(ptr,size);
149	else
150	munmap(BLOCK_START(ptr),size);
151	}
152	}
153	}
154
155	void* malloc(size_t size) {
156	__alloc_t* ptr;
157	size_t need;
158	if (!size) goto err_out;
159	size+=sizeof(__alloc_t);
160	if (size<sizeof(__alloc_t)) goto err_out;
161	if (size<=__MAX_SMALL_SIZE) {
162	need=GET_SIZE(size);
163	ptr=__small_malloc(need);
164	}
165	else {
166	need=PAGE_ALIGN(size);
167	if (!need) ptr=MAP_FAILED; else ptr=do_mmap(need);
168	}
169	if (ptr==MAP_FAILED) goto err_out;
170	ptr->size=need;
171	return BLOCK_RET(ptr);
172	err_out:
173	//(*__errno_location())=ENOMEM;
174	return 0;
175	}
176
177	void* calloc(size_t nmemb, size_t _size) {
178	register size_t size=_size*nmemb;
179	if (nmemb && size/nmemb!=_size) {
180	//(*__errno_location())=ENOMEM;
181	return 0;
182	}
183	#ifdef WANT_FREE_OVERWRITE
184	if (size<__MAX_SMALL_SIZE) {
185	void* x=malloc(size);
186	memset(x,0,size);
187	return x;
188	} else
189	#endif
190	return malloc(size);
191	}
192
193	void* realloc(void* ptr, size_t _size) {
194	register size_t size=_size;
195	if (ptr) {
196	if (size) {
197	__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	if (tmp->size!=size) {
202	if ((tmp->size<=__MAX_SMALL_SIZE)) {
203	void *new=malloc(_size);
204	if (new) {
205	register __alloc_t* foo=BLOCK_START(new);
206	size=foo->size;
207	if (size>tmp->size) size=tmp->size;
208	if (size) memcpy(new,ptr,size-sizeof(__alloc_t));
209	free(ptr);
210	}
211	ptr=new;
212	}
213	else {
214	register __alloc_t* foo;
215	size=PAGE_ALIGN(size);
216	foo=mremap(tmp,tmp->size,size,MREMAP_MAYMOVE);
217	if (foo==MAP_FAILED) {
218	retzero:
219	//(*__errno_location())=ENOMEM;
220	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