memory-allocator.zc

实现树形结构

//[of]:description
//[c]Simple memory allocator
//[c]
//[c]Currently a simple wrapper to the libc malloc.
//[c]A very basic leak detector is implemented.
//[cf]
//[of]:imports
//[c]
import "libc/malloc"
import "base/types"
import "base/memory"
//[cf]
//[of]:globals
//[c]
//[c]Statistics
//[c]
public def total block : size
public def left block : size
public def left bytes : size
public def max bytes : size
//[cf]
//[c]
//[of]:module initialization
//[of]:initialize allocator
//[c]
public func initialize allocator

	first block = nil
	total block = 0
	left block = 0
	left bytes = 0
	max bytes = 0

end
//[cf]
//[of]:release allocator
//[c]
public func release allocator

	def block = first block
	while not nil (block)

		def next = next (block)
		free (block - head size)
		block = next
	end

end
//[cf]
//[cf]
//[of]:allocating
//[of]:allocate memory (size)
//[c]Allocates memory
//[c]
public equ allocate memory (size: size) =
	raw allocate memory (size)
//[cf]
//[of]:free memory (base)
//[c]Frees a memory block
//[c]
//[c]Deleting a null pointer does nothing but is valid
//[c]
public equ free memory (base: mem) = 
	raw free memory (base)
//[cf]
//[c]
//[c]For statistics, basic leak detections:
//[of]:stat allocate memory (size)
//[c]Allocates memory
//[c]
private func stat allocate memory (size: size)

	def next block = first block
	first block = malloc ((size + head size):malloc size):bytes + head size
	next (first block) = next block
	prev (first block) = nil
	size (first block) = size
	
	if not nil (next block)
		prev (next block) = first block
	end
	
	// statistics
	total block += 1
	left block += 1
	left bytes += size
	if left bytes > max bytes
		max bytes = left bytes
	end
	
	return first block
end
//[cf]
//[of]:stat free memory (base)
//[c]Frees a memory block
//[c]
//[c]Deleting a null pointer does nothing but is valid
//[c]
private func stat free memory (base: mem)

	if is nil (base)
		return
	end

	def p = prev (base:bytes)
	def n = next (base:bytes)
	
	if not nil (p)
		next (p) = n
	end
	
	if not nil (n)
		prev (n) = p
	end
	
	if first block == base 
		first block = n
	end
	
	// statistics
	left bytes -= size (base:bytes)
	left block -= 1

	// now free memory
	free (base:bytes - head size)

end
//[cf]
//[c]
//[c]For memory debugging:
//[of]:debug allocate memory (size)
//[c]Allocates memory
//[c]
equ extra = 32
equ uninit = 0xE4:byte
equ wall = 0xE6:byte
//[c]
private func debug allocate memory (size: size)

	def next block = first block
	first block = malloc ((size + head size + extra):malloc size):bytes + head size
	next (first block) = next block
	prev (first block) = nil
	size (first block) = size
	
	if not nil (next block)
		prev (next block) = first block
	end

	// fill allocated memory with unitialized markers
	// plus extra bytes
	def p = first block
	def limit = p+size
	while p < limit
		p++[] = uninit
	end
	limit = p+extra
	while p < limit
		p++[] = wall
	end
	
	// statistics
	total block += 1
	left block += 1
	left bytes += size
	if left bytes > max bytes
		max bytes = left bytes
	end
	
	return first block
end
//[cf]
//[of]:debug free memory (base)
//[c]Frees a memory block
//[c]
//[c]Deleting a null pointer does nothing but is valid
//[c]
private func debug free memory (base: mem)

	if is nil (base)
		return
	end

	def p = prev (base:bytes)
	def n = next (base:bytes)
	def s = size (base:bytes)
	
	if not nil (p)
		next (p) = n
	end
	
	if not nil (n)
		prev (n) = p
	end
	
	if first block == base 
		first block = n
	end

	// check this block	
	if s > 0x0fffffff
		trap
	end
	def pp = base:bytes + s
	def limit = pp+extra
	while pp < limit
		if pp++[] <> wall
			trap
		end
	end
	check memory
	
	// statistics
	left bytes -= size (base:bytes)
	left block -= 1

	// now free memory
	def r = base:bytes
	def i = size (base:bytes)
	while i > 0
		r++ [] = 0xE5:byte
		i --
	end
	free (base:bytes - head size)

end
//[c]
public func check memory
	def base = first block
	while not nil (base)
		def s = size (base:bytes)
		def p = base:bytes + s
		def limit = p + extra
		while p < limit
			if p++[] <> wall
				trap
			end
		end
		base = next (base)
	end
end
//[cf]
//[c]
//[c]The libc allocation functions:
//[of]:raw allocate memory (size)
//[c]Allocates memory
//[c]
private equ raw allocate memory (size: size) =
	malloc (size:malloc size):bytes
//[cf]
//[of]:raw free memory (base)
//[c]Frees a memory block
//[c]
private equ raw free memory (base: mem) = 
	free (base:bytes)
//[cf]
//[cf]
//[c]
//[of]:private
//[of]:types
//[c]
typedef bytes = []byte
//[cf]
//[of]:globals
//[c]
def first block: bytes
//[cf]
//[of]:macros & constants
//[c]
private struct mem head
	next: bytes
	prev: bytes
	size: size
end

equ head size = sizeof (local mem head)
equ next(base:bytes) = next ((base-head size): mem head)
equ prev(base:bytes) = prev ((base-head size): mem head)
equ size(base:bytes) = size ((base-head size): mem head)
//[cf]
//[cf]