1/*-
2 * Copyright (c) 2013, 2015 Antti Kantee.  All rights reserved.
3 * Copyright (c) 1983, 1993
4 *	The Regents of the University of California.  All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 *    notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in the
13 *    documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of the University nor the names of its contributors
15 *    may be used to endorse or promote products derived from this software
16 *    without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * SUCH DAMAGE.
29 */
30
31/*
32 * malloc.c (Caltech) 2/21/82
33 * Chris Kingsley, kingsley@cit-20.
34 *
35 * This is a very fast storage allocator.  It allocates blocks of a small
36 * number of different sizes, and keeps free lists of each size.  Blocks that
37 * don't exactly fit are passed up to the next larger size.  In this
38 * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
39 * This is designed for use in a virtual memory environment.
40 *
41 * Modified for bmk by Antti Kantee over 30 years later.
42 */
43
44#include <bmk-core/core.h>
45#include <bmk-core/null.h>
46#include <bmk-core/string.h>
47#include <bmk-core/memalloc.h>
48#include <bmk-core/platform.h>
49#include <bmk-core/pgalloc.h>
50#include <bmk-core/printf.h>
51#include <bmk-core/queue.h>
52
53#include <bmk-pcpu/pcpu.h>
54
55/*
56 * Header goes right before the allocated space and holds
57 * information about the allocation.  Notably, we support
58 * max 4gig alignment.  If you need more, use some other
59 * allocator than malloc.
60 */
61struct memalloc_hdr {
62	uint32_t	mh_alignpad;	/* padding for alignment */
63	uint16_t	mh_magic;	/* magic number */
64	uint8_t		mh_index;	/* bucket # */
65	uint8_t		mh_who;		/* who allocated */
66};
67bmk_ctassert(sizeof(struct memalloc_hdr) == 8);
68
69struct memalloc_freeblk {
70	LIST_ENTRY(memalloc_freeblk) entries;
71};
72LIST_HEAD(freebucket, memalloc_freeblk);
73
74#define	MAGIC		0xef		/* magic # on accounting info */
75#define UNMAGIC		0x1221		/* magic # != MAGIC */
76#define UNMAGIC2	0x2442		/* magic # != MAGIC/UNMAGIC */
77
78#define MINSHIFT 5
79#define	LOCALBUCKETS (BMK_PCPU_PAGE_SHIFT - MINSHIFT)
80#define MINALIGN 16
81static struct freebucket freebuckets[LOCALBUCKETS];
82
83/*
84 * nmalloc[i] is the difference between the number of mallocs and frees
85 * for a given block size.
86 */
87static unsigned nmalloc[LOCALBUCKETS];
88
89/* not multicore */
90#define malloc_lock()
91#define malloc_unlock()
92
93static void *
94morecore(int bucket)
95{
96	void *rv;
97	uint8_t *p;
98	unsigned long sz;		/* size of desired block */
99	unsigned long nblks;		/* how many blocks we get */
100
101	sz = 1<<(bucket+MINSHIFT);
102	nblks = BMK_PCPU_PAGE_SIZE / sz;
103	bmk_assert(nblks > 1);
104
105	if ((p = rv = bmk_pgalloc_one()) == NULL)
106		return NULL;
107
108	/*
109	 * Add new memory allocated to that on
110	 * free list for this hash bucket.  Return one block.
111	 */
112	while (--nblks) {
113		struct memalloc_freeblk *frb;
114
115		p += sz;
116		frb = (void *)p;
117		LIST_INSERT_HEAD(&freebuckets[bucket], frb, entries);
118	}
119	return rv;
120}
121
122void
123bmk_memalloc_init(void)
124{
125	unsigned i;
126
127	bmk_assert(BMK_PCPU_PAGE_SIZE > 0);
128	for (i = 0; i < LOCALBUCKETS; i++) {
129		LIST_INIT(&freebuckets[i]);
130	}
131}
132
133static void *
134bucketalloc(unsigned bucket)
135{
136	struct memalloc_freeblk *frb;
137
138	malloc_lock();
139
140	/*
141	 * If nothing in hash bucket right now,
142	 * request more memory from the system.
143	 */
144	if ((frb = LIST_FIRST(&freebuckets[bucket])) == NULL) {
145		if ((frb = morecore(bucket)) == NULL) {
146			malloc_unlock();
147			return NULL;
148		}
149	} else {
150		LIST_REMOVE(frb, entries);
151	}
152
153	nmalloc[bucket]++;
154	malloc_unlock();
155
156	return frb;
157}
158
159void *
160bmk_memalloc(unsigned long nbytes, unsigned long align, enum bmk_memwho who)
161{
162	struct memalloc_hdr *hdr;
163	void *rv;
164	unsigned long allocbytes;
165	unsigned bucket;
166	unsigned long alignpad;
167
168	if (align & (align-1))
169		return NULL;
170	if (align < MINALIGN)
171		align = MINALIGN;
172	bmk_assert(align <= (1UL<<31));
173
174	/* need at least this many bytes plus header to satisfy alignment */
175	allocbytes = nbytes + ((sizeof(*hdr) + (align-1)) & ~(align-1));
176
177	/*
178	 * Convert amount of memory requested into closest block size
179	 * stored in hash buckets which satisfies request.
180	 * Account for space used per block for accounting.
181	 */
182	if (allocbytes < 1<<MINSHIFT) {
183		bucket = 0;
184	} else {
185		bucket = 8*sizeof(allocbytes)
186		    - __builtin_clzl(allocbytes>>MINSHIFT);
187		if ((allocbytes & (allocbytes-1)) == 0)
188			bucket--;
189	}
190
191	/* handle with page allocator? */
192	if (bucket >= LOCALBUCKETS) {
193		hdr = bmk_pgalloc(bucket+MINSHIFT - BMK_PCPU_PAGE_SHIFT);
194	} else {
195		hdr = bucketalloc(bucket);
196	}
197	if (hdr == NULL)
198		return NULL;
199
200	/* align op before returned memory */
201	rv = (void *)(((unsigned long)(hdr+1) + align - 1) & ~(align - 1));
202	alignpad = (unsigned long)rv - (unsigned long)hdr;
203
204#ifdef MEMALLOC_TESTING
205	bmk_memset(hdr, MAGIC, alignpad);
206#endif
207
208	hdr = ((struct memalloc_hdr *)rv)-1;
209	hdr->mh_magic = MAGIC;
210	hdr->mh_index = bucket;
211	hdr->mh_alignpad = alignpad;
212	hdr->mh_who = who;
213
214  	return rv;
215}
216
217void *
218bmk_xmalloc_bmk(unsigned long howmuch)
219{
220	void *rv;
221
222	rv = bmk_memalloc(howmuch, 0, BMK_MEMWHO_WIREDBMK);
223	if (rv == NULL)
224		bmk_platform_halt("xmalloc failed");
225	return rv;
226}
227
228void *
229bmk_memcalloc(unsigned long n, unsigned long size, enum bmk_memwho who)
230{
231	void *v;
232	unsigned long tot = n * size;
233
234	if (size != 0 && tot / size != n)
235		return NULL;
236
237	if ((v = bmk_memalloc(tot, MINALIGN, who)) != NULL) {
238		bmk_memset(v, 0, tot);
239	}
240	return v;
241}
242
243void
244bmk_memfree(void *cp, enum bmk_memwho who)
245{
246	struct memalloc_hdr *hdr;
247	struct memalloc_freeblk *frb;
248	unsigned long alignpad;
249	unsigned int index;
250	void *origp;
251
252  	if (cp == NULL)
253  		return;
254	hdr = ((struct memalloc_hdr *)cp)-1;
255	if (hdr->mh_magic != MAGIC) {
256#ifdef MEMALLOC_TESTING
257		bmk_assert(0);
258#else
259		bmk_printf("bmk_memfree: invalid pointer %p\n", cp);
260		return;
261#endif
262	}
263	if (hdr->mh_who != who) {
264		bmk_printf("bmk_memfree: mismatch %d vs. %d for %p",
265		    hdr->mh_who, who, cp);
266		bmk_platform_halt("bmk_memalloc error");
267	}
268
269	index = hdr->mh_index;
270	alignpad = hdr->mh_alignpad;
271
272	origp = (unsigned char *)cp - alignpad;
273
274#ifdef MEMALLOC_TESTING
275	{
276		unsigned long i;
277
278		for (i = 0;
279		    (unsigned char *)origp + i < (unsigned char *)hdr;
280		    i++) {
281			bmk_assert(*((unsigned char *)origp + i) == MAGIC);
282
283		}
284	}
285#endif
286
287	if (index >= LOCALBUCKETS) {
288		bmk_pgfree(origp, (index+MINSHIFT) - BMK_PCPU_PAGE_SHIFT);
289	} else {
290		malloc_lock();
291		frb = origp;
292		LIST_INSERT_HEAD(&freebuckets[index], frb, entries);
293		nmalloc[index]--;
294		malloc_unlock();
295	}
296}
297
298/*
299 * Don't do any of "storage compaction" nonsense, "just" the three modes:
300 *   + cp == NULL ==> malloc
301 *   + nbytes == 0 ==> free
302 *   + else ==> realloc
303 *
304 * Also, assume that realloc() is always called from POSIX compat code,
305 * because nobody sane would use realloc()
306 */
307void *
308bmk_memrealloc_user(void *cp, unsigned long nbytes)
309{
310	struct memalloc_hdr *hdr;
311  	unsigned long size;
312	unsigned long alignpad;
313	void *np;
314
315	if (cp == NULL)
316		return bmk_memalloc(nbytes, MINALIGN, BMK_MEMWHO_USER);
317
318	if (nbytes == 0) {
319		bmk_memfree(cp, BMK_MEMWHO_USER);
320		return NULL;
321	}
322
323	hdr = ((struct memalloc_hdr *)cp)-1;
324	size = hdr->mh_index;
325	alignpad = hdr->mh_alignpad;
326
327	/* don't bother "compacting".  don't like it?  don't use realloc! */
328	if (((1<<(size+MINSHIFT)) - alignpad) >= nbytes)
329		return cp;
330
331	/* we're gonna need a bigger bucket */
332	np = bmk_memalloc(nbytes, 8, BMK_MEMWHO_USER);
333	if (np == NULL)
334		return NULL;
335
336	bmk_memcpy(np, cp, (1<<(size+MINSHIFT)) - alignpad);
337	bmk_memfree(cp, BMK_MEMWHO_USER);
338	return np;
339}
340
341/*
342 * mstats - print out statistics about malloc
343 *
344 * Prints two lines of numbers, one showing the length of the free list
345 * for each size category, the second showing the number of mallocs -
346 * frees for each size category.
347 */
348void
349bmk_memalloc_printstats(void)
350{
351	struct memalloc_freeblk *frb;
352	unsigned long totfree = 0, totused = 0;
353	unsigned int i, j;
354
355	bmk_printf("Memory allocation statistics\n");
356	bmk_printf("size:\t");
357	for (i = 0; i < LOCALBUCKETS; i++) {
358		bmk_printf("%8d", 1<<(i+MINSHIFT));
359	}
360	bmk_printf("\nfree:\t");
361	for (i = 0; i < LOCALBUCKETS; i++) {
362		j = 0;
363		LIST_FOREACH(frb, &freebuckets[i], entries) {
364			j++;
365		}
366		bmk_printf("%8d", j);
367		totfree += j * (1 << (i + MINSHIFT));
368  	}
369	bmk_printf("\nused:\t");
370	for (i = 0; i < LOCALBUCKETS; i++) {
371		bmk_printf("%8d", nmalloc[i]);
372		totused += nmalloc[i] * (1 << (i + MINSHIFT));
373  	}
374	bmk_printf("\n\tTotal in use: %lukB, total free in buckets: %lukB\n",
375	    totused/1024, totfree/1024);
376}
377
378
379/*
380 * The rest of this file contains unit tests.
381 */
382
383#ifdef MEMALLOC_TESTING
384
385#define TEST_SMALL_MINALLOC 0
386#define TEST_SMALL_MAXALLOC (128)
387
388#define TEST_LARGE_MINALLOC 0
389#define TEST_LARGE_MAXALLOC (64*1024)
390
391#define TEST_MINALIGN 1
392#define TEST_MAXALIGN 16
393
394#define NALLOC 1024
395#define NRING 16
396
397static unsigned randstate;
398
399static unsigned
400myrand(void)
401{
402
403	return (randstate = randstate * 1103515245 + 12345) % (0x80000000L);
404}
405
406static void *
407testalloc(unsigned long min, unsigned long max)
408{
409	void *v, *nv;
410	unsigned int size1, size2, align;
411
412	/* doesn't give an even bucket distribution, but ... */
413	size1 = myrand() % ((max-min)+1) + min;
414	align = myrand() % ((TEST_MAXALIGN-TEST_MINALIGN)+1) + TEST_MINALIGN;
415
416	v = bmk_memalloc(size1, 1<<align, BMK_MEMWHO_USER);
417	if (!v)
418		return NULL;
419	bmk_assert(((uintptr_t)v & (align-1)) == 0);
420	bmk_memset(v, UNMAGIC, size1);
421
422	size2 = myrand() % ((max-min)+1) + min;
423	nv = bmk_memrealloc_user(v, size2);
424	if (nv) {
425		bmk_memset(nv, UNMAGIC2, size2);
426		return nv;
427	}
428
429	return size2 ? v : NULL;
430}
431
432/* XXX: no prototype */
433void bmk_memalloc_test(void);
434void
435bmk_memalloc_test(void)
436{
437	unsigned long min = TEST_LARGE_MINALLOC;
438	unsigned long max = TEST_LARGE_MAXALLOC;
439	void **rings; /* yay! */
440	void **ring_alloc, **ring_free; /* yay! */
441	int i, n;
442
443	randstate = (unsigned)bmk_platform_cpu_clock_epochoffset();
444
445	rings = bmk_memalloc(NALLOC * NRING * sizeof(void *),
446	    0, BMK_MEMWHO_USER);
447	/* so we can free() immediately without stress */
448	bmk_memset(rings, 0, NALLOC * NRING * sizeof(void *));
449
450	for (n = 0;; n = (n+1) % NRING) {
451		if (n == 0) {
452			bmk_memalloc_printstats();
453			if (max == TEST_SMALL_MAXALLOC) {
454				min = TEST_LARGE_MINALLOC;
455				max = TEST_LARGE_MAXALLOC;
456			} else {
457				min = TEST_SMALL_MINALLOC;
458				max = TEST_SMALL_MAXALLOC;
459			}
460		}
461
462		ring_alloc = &rings[n * NALLOC];
463		ring_free = &rings[((n + NRING/2) % NRING) * NALLOC];
464		for (i = 0; i < NALLOC; i++) {
465			ring_alloc[i] = testalloc(min, max);
466			bmk_memfree(ring_free[i], BMK_MEMWHO_USER);
467		}
468	}
469}
470#endif /* MEMALLOC_TESTING */
471