tlsf

Documentation

Index

• Constants
• func Compare(a, b unsafe.Pointer, n uintptr) int
• func Copy(dst, src unsafe.Pointer, n uintptr)
• func Equals(a, b unsafe.Pointer, size uintptr) bool
• func Fastrand() uint32
• func Move(to, from unsafe.Pointer, n uintptr)
• func NewSysArena() *sysArena
• func PrintDebugInfo()
• func SizeOf(ptr uintptr) uintptr
• func Zero(ptr unsafe.Pointer, n uintptr)
• type Arena
• type BLOCK
• type Grow
  • func GrowBy(pages int32, arena Arena) Grow
  • func GrowByDouble(arena Arena) Grow
  • func GrowMin(arena Arena) Grow
• type GrowFactory
• type Heap
  • func Bootstrap(start, end uintptr, pages int32, grow Grow) *Heap
  • func NewHeap(pages int32) *Heap
  • func NewHeapWithConfig(pages int32, pageAlloc Arena, grow GrowFactory) *Heap
  • func (a *Heap) Alloc(size uintptr) uintptr
  • func (a *Heap) AllocZeroed(size uintptr) uintptr
  • func (a *Heap) Free(ptr uintptr)
  • func (a *Heap) Realloc(ptr uintptr, size uintptr) uintptr
  • func (a *Heap) ToSync() *Sync
• type SliceArena
  • func NewSliceArena() *SliceArena
  • func (a *SliceArena) Alloc(size uintptr) (uintptr, uintptr)
  • func (a *SliceArena) Free()
• type Stats
  • func (s *Stats) Fragmentation() float32
• type Sync
  • func (a *Sync) Alloc(size uintptr) uintptr
  • func (a *Sync) AllocZeroed(size uintptr) uintptr
  • func (a *Sync) Free(ptr uintptr)
  • func (a *Sync) Realloc(ptr uintptr, size uintptr) uintptr
  • func (a *Sync) Stats() Stats
• type SystemAllocator

Constants

const (
	PageSize = uintptr(64 * 1024)

	ALBits uint32  = 4 // 16 bytes to fit up to v128
	ALSize uintptr = 1 << uintptr(ALBits)
	ALMask         = ALSize - 1

	// Overhead of a memory manager block.
	BlockOverhead = unsafe.Sizeof(BLOCK{})
	// Block constants. A block must have a minimum size of three pointers so it can hold `prev`,
	// `prev` and `back` if free.
	BlockMinSize = ((3*_TLSFSizeofPointer + BlockOverhead + ALMask) & ^ALMask) - BlockOverhead
	// Maximum size of a memory manager block's payload.
	BlockMaxSize = (1 << 30) - BlockOverhead

	TagsMask = _TLSFFREE | _TLSFLEFTFREE
)

const (
	SLStart  = _TLSFSizeofPointer
	SLEnd    = SLStart + (uintptr(_TLSFFLBits) << _TLSFAlignU32)
	HLStart  = (SLEnd + ALMask) &^ ALMask
	HLEnd    = HLStart + uintptr(_TLSFFLBits)*uintptr(_TLSFSLSize)*_TLSFSizeofPointer
	RootSize = HLEnd + _TLSFSizeofPointer
)

Functions

func Compare

func Compare(a, b unsafe.Pointer, n uintptr) int

func Copy

func Copy(dst, src unsafe.Pointer, n uintptr)

func Equals

func Equals(a, b unsafe.Pointer, size uintptr) bool

func Fastrand

func Fastrand() uint32

func Move

func Move(to, from unsafe.Pointer, n uintptr)

Memmove copies n bytes from "from" to "to".

Memmove ensures that any pointer in "from" is written to "to" with an indivisible write, so that racy reads cannot observe a half-written pointer. This is necessary to prevent the garbage collector from observing invalid pointers, and differs from Memmove in unmanaged languages. However, Memmove is only required to do this if "from" and "to" may contain pointers, which can only be the case if "from", "to", and "n" are all be word-aligned.

Implementations are in memmove_*.s.

func NewSysArena

func NewSysArena() *sysArena

func PrintDebugInfo

func PrintDebugInfo()

func SizeOf

func SizeOf(ptr uintptr) uintptr

func Zero

func Zero(ptr unsafe.Pointer, n uintptr)

Types

type Arena

type Arena interface {
	Alloc(size uintptr) (uintptr, uintptr)

	Free()
}

Arena allocates memory from the underlying platform. It is used to add new memory to an Allocator.

type BLOCK

type BLOCK struct {
	MMInfo uintptr
}

╒════════════ Memory manager block layout (32-bit) ═════════════╕

  3                   2                   1
1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0  bits

├─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┤ │ MM info │ -4 ╞>ptr═══════════════════════════════════════════════════════════╡ │ ... │

type Grow

type Grow func(pagesBefore, pagesNeeded int32, minSize uintptr) (pagesAdded int32, start, end uintptr)

Grow provides the ability to Grow the heap and allocate a contiguous chunk of system memory to add to the allocator.

func GrowBy

func GrowBy(pages int32, arena Arena) Grow

func GrowByDouble

func GrowByDouble(arena Arena) Grow

func GrowMin

func GrowMin(arena Arena) Grow

type GrowFactory

type GrowFactory func(arena Arena) Grow

type Heap

type Heap struct {
	HeapStart uintptr
	HeapEnd   uintptr

	Grow Grow
	Slot uint8
	Stats
	// contains filtered or unexported fields
}

Heap === Heap (Two-Level Segregate Fit) memory allocator ===

Heap is a general purpose dynamic memory allocator specifically designed to meet real-time requirements:

Bounded Response Time - The worst-case execution time (WCET) of memory allocation
						and deallocation Has got to be known in advance and be
						independent of application data. Allocator Has a constant
						cost O(1).

				 Fast - Additionally to a bounded cost, the allocator Has to be
						efficient and fast enough. Allocator executes a maximum
						of 168 processor instructions in a x86 architecture.
						Depending on the compiler version and optimisation flags,
						it can be slightly lower or higher.

Efficient Memory Use - 	Traditionally, real-time systems run for long periods of
						time and some (embedded applications), have strong constraints
						of memory size. Fragmentation can have a significant impact on
						such systems. It can increase  dramatically, and degrade the
						system performance. A way to measure this efficiency is the
						memory fragmentation incurred by the allocator. Allocator has
						been tested in hundreds of different loads (real-time tasks,
						general purpose applications, etc.) obtaining an average
						fragmentation lower than 15 %. The maximum fragmentation
						measured is lower than 25%.

Memory can be added on demand and is a multiple of 64kb pages. Grow is used to allocate new memory to be added to the allocator. Each Grow must provide a contiguous chunk of memory. However, the allocator may be comprised of many contiguous chunks which are not contiguous of each other. There is not a mechanism for shrinking the memory. Supplied Grow function can effectively limit how big the allocator can get. If a zero pointer is returned it will cause an out-of-memory situation which is propagated as a nil pointer being returned from Alloc. It's up to the application to decide how to handle such scenarios.

see: http://www.gii.upv.es/tlsf/ see: https://github.com/AssemblyScript/assemblyscript

- `ffs(x)` is equivalent to `ctz(x)` with x != 0 - `fls(x)` is equivalent to `sizeof(x) * 8 - clz(x) - 1`

╒══════════════ Block size interpretation (32-bit) ═════════════╕

  3                   2                   1
1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0  bits

├─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┼─┴─┴─┴─╫─┴─┴─┴─┤ │ | FL │ SB = SL + AL │ ◄─ usize └───────────────────────────────────────────────┴───────╨───────┘ FL: first level, SL: second level, AL: alignment, SB: small block

func Bootstrap

func Bootstrap(start, end uintptr, pages int32, grow Grow) *Heap

Bootstrap bootstraps the Allocator with the initial block of contiguous memory that at least fits the minimum required to fit the bitmap.

func NewHeap

func NewHeap(pages int32) *Heap

func NewHeapWithConfig

func NewHeapWithConfig(pages int32, pageAlloc Arena, grow GrowFactory) *Heap

func (*Heap) Alloc

func (a *Heap) Alloc(size uintptr) uintptr

Alloc allocates a block of memory that fits the size provided

func (*Heap) AllocZeroed

func (a *Heap) AllocZeroed(size uintptr) uintptr

AllocZeroed allocates a block of memory that fits the size provided

func (*Heap) Free

func (a *Heap) Free(ptr uintptr)

Free release the allocation back into the free list.

func (*Heap) Realloc

func (a *Heap) Realloc(ptr uintptr, size uintptr) uintptr

Realloc determines the best way to resize an allocation.

func (*Heap) ToSync

func (a *Heap) ToSync() *Sync

type SliceArena

type SliceArena struct {
	// contains filtered or unexported fields
}

SliceArena allocates memory by creating Go byte slices

func NewSliceArena

func NewSliceArena() *SliceArena

func (*SliceArena) Alloc

func (a *SliceArena) Alloc(size uintptr) (uintptr, uintptr)

func (*SliceArena) Free

func (a *SliceArena) Free()

type Stats

type Stats struct {
	HeapSize        int64
	AllocSize       int64
	PeakAllocSize   int64
	FreeSize        int64
	Allocs          int32
	InitialPages    int32
	ConsecutiveLow  int32
	ConsecutiveHigh int32
	Pages           int32
	Grows           int32
	// contains filtered or unexported fields
}

Stats provides the metrics of an Allocator

func (*Stats) Fragmentation

func (s *Stats) Fragmentation() float32

type Sync

type Sync struct {
	Slot uint8
	sync.Mutex
	// contains filtered or unexported fields
}

func (*Sync) Alloc

func (a *Sync) Alloc(size uintptr) uintptr

Alloc allocates a block of memory that fits the size provided. The allocation IS cleared / zeroed out.

func (*Sync) AllocZeroed

func (a *Sync) AllocZeroed(size uintptr) uintptr

AllocZeroed allocates a block of memory that fits the size provided. The allocation is NOT cleared / zeroed out.

func (*Sync) Free

func (a *Sync) Free(ptr uintptr)

Free release the allocation back into the free list.

func (*Sync) Realloc

func (a *Sync) Realloc(ptr uintptr, size uintptr) uintptr

Realloc determines the best way to resize an allocation. Any extra size added is NOT cleared / zeroed out.

func (*Sync) Stats

func (a *Sync) Stats() Stats

type SystemAllocator

type SystemAllocator struct {
}