allocator

Documentation

Index

• Constants
• Variables
• type AllocationStats
• type Free
• type FreeLists
  • func NewFreeLists() *FreeLists
• type FreeingBumpHeapAllocator
  • func NewFreeingBumpHeapAllocator(heapBase uint32) *FreeingBumpHeapAllocator
  • func (f *FreeingBumpHeapAllocator) Allocate(mem runtime.Memory, size uint32) (ptr uint32, err error)
  • func (f *FreeingBumpHeapAllocator) Deallocate(mem runtime.Memory, ptr uint32) (err error)
• type Header
• type Link
• type Nil
• type Occupied
• type Order
• type Ptr

Constants

const (
	Aligment = 8

	// each pointer is prefixed with 8 bytes, which indentifies the list
	// index to which it belongs
	HeaderSize = 8

	// The minimum possible allocation size is chosen to be 8 bytes
	// because in that case we would have easier time to provide the
	// guaranteed alignment of 8
	//
	// The maximum possible allocation size is set to 32Mib
	//
	// NumOrders represents the number of orders supported, this number
	// corresponds to the number of powers between the minimum an maximum
	// possible allocation (2^3 ... 2^25 both ends inclusive)
	NumOrders              uint32 = 23
	MinPossibleAllocations uint32 = 8
	// (1 << 25)
	MaxPossibleAllocations uint32 = 33554432

	PageSize     = 65536
	MaxWasmPages = (4 * 1024 * 1024 * 1024 / PageSize) - 1
)

const NilMarker = math.MaxUint32

NilMarker is a special magic value for a pointer in a link that denotes the end of the linked list.

Variables

var (
	ErrInvalidOrder                 = errors.New("invalid order")
	ErrRequestedAllocationTooLarge  = errors.New("requested allocation too large")
	ErrCannotReadHeader             = errors.New("cannot read header")
	ErrCannotWriteHeader            = errors.New("cannot write header")
	ErrInvalidHeaderPointerDetected = errors.New("invalid header pointer detected")
	ErrAllocatorOutOfSpace          = errors.New("allocator out of space")
	ErrCannotGrowLinearMemory       = errors.New("cannot grow linear memory")
	ErrInvalidPointerForDealocation = errors.New("invalid pointer for deallocation")
	ErrEmptyHeader                  = errors.New("allocation points to an empty header")
	ErrAllocatorPoisoned            = errors.New("allocator poisoned")
	ErrMemoryShrunk                 = errors.New("memory shrunk")
)

Types

type AllocationStats

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

AllocationStats gather stats during the lifetime of the allocator

type Free

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

Free contains a link to the next element to form a free linked list.

type FreeLists

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

FreeLists represents a collection of intrusive linked lists for each order.

func NewFreeLists

func NewFreeLists() *FreeLists

type FreeingBumpHeapAllocator

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

func NewFreeingBumpHeapAllocator

func NewFreeingBumpHeapAllocator(heapBase uint32) *FreeingBumpHeapAllocator

func (*FreeingBumpHeapAllocator) Allocate

func (f *FreeingBumpHeapAllocator) Allocate(mem runtime.Memory, size uint32) (ptr uint32, err error)

Allocate gets the requested number of bytes to allocate and returns a pointer. The maximum size which can be allocated is 32MiB. There is no minimum size, but whatever size is passed into this function is rounded to the next power of two. If the requested size is bellow 8 bytes it will be rounded up to 8 bytes.

The identity or the type of the passed memory object does not matter. However, the size of memory cannot shrink compared to the memory passed in previous invocations.

NOTE: Once the allocator has returned an error all subsequent requests will return an error.

- `mem` - a slice representing the linear memory on which this allocator operates. - size: size in bytes of the allocation request

func (*FreeingBumpHeapAllocator) Deallocate

func (f *FreeingBumpHeapAllocator) Deallocate(mem runtime.Memory, ptr uint32) (err error)

Deallocate deallocates the space which was allocated for a pointer

The identity or the type of the passed memory object does not matter. However, the size of memory cannot shrink compared to the memory passed in previous invocations.

NOTE: Once the allocator has returned an error all subsequent requests will return an error.

- `mem` - a slice representing the linear memory on which this allocator operates. - `ptr` - pointer to the allocated chunk

type Header

type Header interface {
	// contains filtered or unexported methods
}

Header of an allocation.

The header is encoded in memory as follows.

## Free header

```ignore 64 32 0

+--------------+-------------------+

| 0 | next element link | +--------------+-------------------+ ``` ## Occupied header ```ignore 64 32 0

+--------------+-------------------+

| 1 | order | +--------------+-------------------+ ```

type Link

type Link interface {
	// contains filtered or unexported methods
}

Link represents a link between headers in the free list.

type Nil

type Nil struct{}

Nil denotes that there is no next element.

type Occupied

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

Occupied represents an occupied header has an attached order to know in which free list we should put the allocation upon deallocation

type Order

type Order uint32

Order is the exponent for the power of two sized block adjusted to the minimum size.

This way, if `MIN_POSSIBLE_ALLOCATION == 8`, we would get:

power_of_two_size | order 8 | 0 16 | 1 32 | 2 64 | 3 ... 16777216 | 21 33554432 | 22

and so on.

type Ptr

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

Ptr element represents a pointer to the header.