shithub: mc

ref: c0192155d8e843ab3355a564ed97537d0ede00a6
dir: /libstd/alloc.myr/

use "die.use"
use "sys.use"
use "types.use"
use "extremum.use"

pkg std =
	generic alloc	: (		-> @a*)
	generic free	: (v:@a*	-> void)

	generic slalloc	: (len : size	-> @a[:])
	generic slfree	: (sl : @a[:]	-> void)
	generic slgrow	: (sl : @a[:], len : size	-> @a[:])

	const bytealloc	: (sz:size	-> byte*)
	const bytefree	: (m:byte*, sz:size	-> void)
;;

/* null pointers */
const Zbyte	= 0 castto(byte*)
const Zslab	= 0 castto(slab*)
const Zchunk	= 0 castto(chunk*)

const Slabsz 	= 1048576	/* 1 meg slabs */
const Cachemax	= 16	/* maximum number of slabs in the cache */
const Bucketmax	= 32768	/* Slabsz / 8; a balance. */
const Align	= 16	/* minimum allocation alignment */

var buckets	: bucket[32] /* excessive */
var initdone	: int

type bucket = struct
	sz	: size	/* aligned size */
	nper	: size	/* max number of elements per slab */
	slabs	: slab*	/* partially filled or free slabs */
	cache	: slab* /* cache of empty slabs, to prevent thrashing */
	ncache	: size  /* size of cache */
;;

type slab = struct
	head	: byte*	/* head of virtual addresses, so we don't leak address space */
	next	: slab*	/* the next slab on the chain */
	freehd	: chunk*	/* the nodes we're allocating */
	nfree	: size	/* the number of free nodes */
;;

type chunk = struct	/* NB: must be smaller than sizeof(slab) */
	next	: chunk*	/* the next chunk in the free list */
;;

generic alloc = {-> @a*
	-> bytealloc(sizeof(@a)) castto(@a*)
}

generic free = {v:@a* -> void
	bytefree(v castto(byte*), sizeof(@a))
}

generic slalloc = {len
	var p

	p = bytealloc(len*sizeof(@a)) castto(@a*)
	-> p[0:len]
}

generic slfree	 = {sl
	-> bytefree(sl castto(byte*), sl.len * sizeof(@a))
}

generic slgrow = {sl, len
	var i
	var n
	var new

	new = slalloc(len)
	n = min(len, sl.len)
	for i = 0; i < n; i++
		new[i] = sl[i]
	;;
	-> new
}

const bytealloc = {sz
	var i
	var bkt

	if !initdone
		for i = 0; i < buckets.len && (Align << i) <= Bucketmax; i++
			bktinit(&buckets[i], Align << i)
		;;
		initdone = 1
	;;

	if (sz <= Bucketmax)
		bkt = &buckets[bktnum(sz)]
		-> bktalloc(bkt)
	else
		-> mmap(Zbyte, sz, Mprotrw, Mpriv | Manon, -1, 0)
	;;
}

const bytefree = {m, sz
	var bkt

	if (sz < Bucketmax)
		bkt = &buckets[bktnum(sz)]
		bktfree(bkt, m)
	else
		munmap(m, sz)
	;;
}

const bktinit = {b : bucket*, sz
	b.sz = align(sz, Align)
	b.nper = (Slabsz - sizeof(slab))/b.sz
	b.slabs = Zslab
	b.cache = Zslab
	b.ncache = 0
}

const mkslab = {bkt : bucket*
	var i
	var p
	var s
	var b
	var bnext
	var off /* offset of chunk head */

	if bkt.ncache > 0
		s = bkt.cache
		bkt.cache = s.next
		bkt.ncache--
	;;
	/* tricky: we need power of two alignment, so we allocate double the
	   needed size, chop off the unaligned ends, and waste the address
	   space. Since the OS is "smart enough", this shouldn't actually
	   cost us memory, and 64 bits of address space means that we're not
	   going to have issues with running out of address space for a
	   while. On a 32 bit system this would be a bad idea. */
	p = mmap(Zbyte, Slabsz*2, Mprotrw, Mpriv | Manon, -1, 0)
	if p == Mapbad
		die("Unable to mmap")
	;;

	s = align(p castto(intptr), Slabsz) castto(slab*)
	s.head = p
	s.nfree = bkt.nper
	/* skip past the slab header */
	off = align(sizeof(slab), Align)
	bnext = nextchunk(s castto(chunk*), off)
	s.freehd = bnext
	for i = 0; i < bkt.nper; i++
		b = bnext
		bnext = nextchunk(b, bkt.sz)
		b.next = bnext
	;;
	b.next = Zchunk
	-> s
}

const bktalloc = {bkt
	var s
	var b

	/* find a slab */
	s = bkt.slabs
	if s == Zslab
		s = mkslab(bkt)
		if s == Zslab
			die("No memory left")
		;;
		bkt.slabs = s
	;;

	/* grab the first chunk on the slab */
	b = s.freehd
	s.freehd = b.next
	s.nfree--
	if !s.nfree
		bkt.slabs = s.next
		s.next = Zslab
	;;

	-> b castto(byte*)
}

const bktfree = {bkt, m
	var s
	var b

	s = mtrunc(m, Slabsz) castto(slab*)
	b = m castto(chunk*)
	if s.nfree == 0
		s.next = bkt.slabs
		bkt.slabs = s
	elif s.nfree == bkt.nper
		if bkt.ncache < Cachemax
			s.next = bkt.cache
			bkt.cache = s
		else
			/* we mapped 2*Slabsz so we could align it,
			 so we need to unmap the same */
			munmap(s.head, Slabsz*2)
		;;
	;;
	s.nfree++
	b.next = s.freehd
	s.freehd = b
}

const bktnum = {sz
	var i
	var bktsz

	bktsz = Align
	for i = 0; bktsz <= Bucketmax; i++
		if bktsz >= sz
			-> i
		;;
		bktsz *= 2
	;;
	die("Size does not match any buckets")
}

/* chunks are variable sizes, so we can't just take a slice */
const nextchunk = {b, sz
	-> ((b castto(intptr)) + sz) castto(chunk*)
}

const align = {v, align
	-> (v + align - 1) & ~(align - 1)
}

const mtrunc = {m, align
	-> ((m castto(intptr)) & ~(align - 1)) castto(byte*)
}