metadata

package
v0.0.0-...-df451fa Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 21, 2024 License: MIT Imports: 12 Imported by: 1

Documentation

Index

Constants

View Source 
const (
	SmallBufferSize        = 256
	SecondLevelIndex uint8 = 5
	MemoryClassShift       = 7
	MaxMemoryClasses       = 65 - MemoryClassShift
)

Variables

This section is empty.

Functions

This section is empty.

Types

type AllocationRequest 

type AllocationRequest struct {
	// BlockAllocationHandle is a numeric handle used to identify individual allocations within the metadata
	BlockAllocationHandle BlockAllocationHandle
	// Size the total size of the allocation, maybe larger than what was originally requested
	Size int
	// Item is a Suballocation object indicating basic information about the allocation
	Item Suballocation
	// CustomData
	CustomData    uint32
	AlgorithmData uint64
	Type          AllocationRequestType
}

AllocationRequest is a type returned from BlockMetadata.CreateAllocationRequest which indicates where and how the metadata intends to allocate new memory. This allocation can be applied to the actual memory system consuming memutils, and then committed to the metadata with BlockMetadata.Alloc

type AllocationRequestType 

type AllocationRequestType uint32

AllocationRequestType is an enum that indicates the type of allocation that is being made. It is returned in AllocationRequest from CreateAllocationRequest 

const (
	// AllocationRequestTLSF indicates that the allocation request was sourced from metadata.TLSFBlockMetadata
	AllocationRequestTLSF AllocationRequestType = iota
	// AllocationRequestUpperAddress indicates that the allocation request was sourced from metadata.LinearBlockMetadata
	// and that it is an allocation for the upper side of a double stack
	AllocationRequestUpperAddress
	// AllocationRequestEndOf1st indicates that the allocation request was sourced from metadata.LinearBlockMetadata
	// and that it is an allocation to be added to the end of the first memory vector
	AllocationRequestEndOf1st
	// AllocationRequestEndOf2nd indicates that the allocation request was sourced from metadata.LinearBlockMetadata
	// and that it is an allocation to be added to the end of the second memory vector
	AllocationRequestEndOf2nd
)

func (AllocationRequestType) String 

func (t AllocationRequestType) String() string

type AllocationStrategy 

type AllocationStrategy uint32

AllocationStrategy exposes several options for choosing the location of a new memory allocation. You can choose several and memutils will select one of them based on its own preferences. If none is chosen, a balanced strategy will be used. 

const (
	// AllocationStrategyMinMemory selects the allocation strategy that chooses the smallest-possible
	// free range for the allocation to minimize memory usage and fragmentation, possibly at the expense of
	// allocation time
	AllocationStrategyMinMemory AllocationStrategy = 1 << iota
	// AllocationStrategyMinTime selects the allocation strategy that chooses the first suitable free
	// range for the allocation- not necessarily in terms of the smallest offset, but the one that is easiest
	// and fastest to find to minimize allocation time, possibly at the expense of allocation quality.
	AllocationStrategyMinTime
	// AllocationStrategyMinOffset selects the allocation strategy that chooses the lowest offset in
	// available space. This is not the most efficient strategy, but achieves highly packed data. Used internally
	// by defragmentation, not recommended in typical usage.
	AllocationStrategyMinOffset
)

type BlockAllocationHandle 

type BlockAllocationHandle uint64
const (
	NoAllocation BlockAllocationHandle = math.MaxUint64
)

type BlockMetadata 

type BlockMetadata interface {
	// Init must be called before the BlockMetadata is used. It gives the implementation an opportunity
	// to ensure that metadata structures are prepared for allocations, as well as allows the consumer
	// to inform the implementation of the size in bytes of the block of memory it will be managing,
	// via the size parameter.
	Init(size int)
	// Size retrieves the size in bytes that the block was initialized with
	Size() int
	// SupportsRandomAccess returns a boolean indicating whether the implementation allows allocations
	// to be made in arbitrary sections of the managed block, or whether the implementation demands
	// that allocation offsets be deterministic. As an example, the two-level segregated fit implementation
	// allows random access, while the linear (stack and ring buffer) implementation does not.
	// This method must return true for the block to be used with the memutils.defrag package.
	SupportsRandomAccess() bool

	// Validate performs internal consistency checks on the metadata. These checks may be expensive, depending
	// on the implementation. When the implementation is functioning correctly, it should not be possible
	// for this method to return an error, but this may assist in diagnosing issues with the implementation.
	Validate() error
	// AllocationCount returns the number of suballocations currently live in the implementation. This number
	// should generally be the number of successful allocations minus the number of successful frees.
	AllocationCount() int
	// FreeRegionsCount returns the number of unique regions of free memory in the block. The specific meaning
	// of this value is implementation-specific, but adjacent regions of free memory should usually be counted
	// as a single region (or, in fact, merged into a single region).
	FreeRegionsCount() int
	// SumFreeSize returns the number of free bytes of memory in the block.
	SumFreeSize() int
	// MayHaveFreeBlock should return a heuristic indicating whether the block could possibly support a new
	// allocation of the provided type and size. allocType is a value that has meaning within the memory
	// system consuming BlockMetadata. The implementation may or may not care, and could potentially pass
	// the value back to some callback or interface provided by the consumer. The size parameter is the size
	// in bytes of the hypothetical allocation.
	//
	// This method is used by memutils.defrag to very rapidly determine whether it can ignore blocks when
	// trying to reposition allocations. As a result, the most important requirement for the implementation
	// is that this method be fast and not produce false negatives. False positives are ok, but ideal performance
	// requires that this method balance runtime with the likelihood of false positives.
	//
	// It is completely acceptable for consumers to use this method for the same purpose as memutils.defrag
	// (determine whether a block can be ignored while attempting to rapidly make allocations of a particular
	// size).
	MayHaveFreeBlock(allocType uint32, size int) bool

	// IsEmpty will return true if this block has no live suballocations
	IsEmpty() bool

	// VisitAllRegions will call the provided callback once for each allocation and free region in
	// the block.  Depending on implementation, this can be extremely slow and should generally not
	// be done except for diagnostic purposes.
	VisitAllRegions(handleBlock func(handle BlockAllocationHandle, offset int, size int, userData any, free bool) error) error
	// AllocationListBegin will retrieve the handle very first allocation in the block, if any. If none exist, the
	// BlockAllocationHandle value NoAllocation will be returned.
	//
	// The implementation must return an error if SupportsRandomAccess() returns false.
	AllocationListBegin() (BlockAllocationHandle, error)
	// FindNextAllocation accepts a BlockAllocationHandle that maps to a live allocation within the block
	// and returns the handle for the next live allocation within the block, if any. If none exist, the
	// BlockAllocationHandle value NoAllocation will be returned.
	//
	// The implementation must return an error if SupportsRandomAccess() returns false. It must also
	// return an error if the provided allocHandle does not map to a live allocation within this block.
	FindNextAllocation(allocHandle BlockAllocationHandle) (BlockAllocationHandle, error)

	// AllocationOffset accepts a BlockAllocationHandle that maps to a live region of memory
	// (allocated or free) within the block and returns the offset in bytes within the block for that
	// region of memory.
	//
	// The implementation must return an error if the provided handle does not map to a live region of
	// memory within this block.
	AllocationOffset(allocHandle BlockAllocationHandle) (int, error)
	// AllocationUserData accepts a BlockAllocationHandle that maps to a live allocation within the block
	// and returns the userdata value provided by the consumer for that allocation.
	//
	// The implementation must return an error if the provided handle does not map to a live allocation
	// within this block.
	AllocationUserData(allocHandle BlockAllocationHandle) (any, error)
	// SetAllocationUserData accepts a BlockAllocationHandle that maps to a live allocation within the
	// block and a userData value. The allocation's userData is changed to the provided userData.
	//
	// The implementation must return an error if the provided handle does not map to a live allocation
	// within this block.
	SetAllocationUserData(allocHandle BlockAllocationHandle, userData any) error

	// AddDetailedStatistics sums this block's allocation statistics into the statistics currently present
	// in the provided memutils.DetailedStatistics object.
	AddDetailedStatistics(stats *memutils.DetailedStatistics)
	// AddStatistics sums this block's allocation statistics into the statistics currently present in the
	// provided memutils.Statistics object.
	AddStatistics(stats *memutils.Statistics)

	// Clear instantly frees all allocations and
	Clear()
	// BlockJsonData populates a json object with information about this block
	BlockJsonData(json jwriter.ObjectState)

	// CheckCorruption accepts a pointer to the underlying memory that this block manages. It will return
	// nil if anti-corruption memory markers are present for every suballocation in the block. This method
	// is fairly expensive and so should only be run as part of some sort of diagnostic regime.
	//
	// Bear in mind that anti-corruption memory markers are only written when memutils is built with
	// the build flag `debug_mem_utils`. This method will not return an error when that flag is not present,
	// but it is expensive regardless of build flags and so should only be run when mem_utils.DebugMargin
	// is not 0.
	//
	// Additionally, it is the responsibility of consumers to write the debug markers themselves after
	// allocation, by calling memutils.WriteMagicValue with the same pointer sent to CheckCorruption.
	// If the consumer has failed to write the anti-corruption markers, then this method will return an
	// error.
	CheckCorruption(blockData unsafe.Pointer) error

	// CreateAllocationRequest retrieves an AllocationRequest object indicating where and how the implementation
	// would prefer to allocate the requested memory. That object can be passed to Alloc to commit the
	// allocation.
	//
	// allocSize - the size in bytes of the requested allocation
	// allocAlignment - the minimum alignment of the requested allocation. The implementation may increase
	// the alignment above this value, but may not reduce it below this value
	// upperAddress - In implementations that split the memory block into two tranches (such as
	// LinearBlockMetadata and its double stack mode), this parameter indicates that the allocation should
	// be made in the upper tranch if true. When there is only a single tranch of memory in the implementation,
	// the implementation should return an error when this argument is true.
	// allocType - Memory-system-dependent allocation type value. The consumer may care about this.
	// Implementations usually have a consumer-provided "granularity handler" which may care about this.
	// strategy - Whether to prioritize memory usage, memory offset, or allocation speed when choosing
	// a place for the requested allocation.
	// maxOffset - This parameter should usually be math.MaxInt. The requested allocation must fail
	// if the allocation cannot be placed at an offset before the provided maxOffset. This is primarily
	// used by memutils.defrag to make relocating an allocation within a block more performant.
	CreateAllocationRequest(
		allocSize int, allocAlignment uint,
		upperAddress bool,
		allocType uint32,
		strategy AllocationStrategy,
		maxOffset int,
	) (bool, AllocationRequest, error)
	// Alloc commits an AllocationRequest object, creating the suballocation within the block based
	// on the data described in the AllocationRequest. The implementation must return an error if the
	// allocation is no longer valid- i.e. the requested free region no longer exists, is not free,
	// offset has changed, is no longer large enough to support the request, etc.
	Alloc(request AllocationRequest, allocType uint32, userData any) error

	// Free frees a suballocation within the block, causing it to become a free region once again.
	//
	// The implementation must return an error if the provided handle does not map to a live allocation
	// within this block.
	Free(allocHandle BlockAllocationHandle) error
}

BlockMetadata represents a single large allocation of memory within some system. It manages suballocations within the block, allowing allocations to be requested and freed, as well as enumerated and queried.

type BlockMetadataBase 

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

BlockMetadataBase is a simple struct that provides a few shared utilities for BlockMetadata implementations in the memutils module.

func NewBlockMetadata 

func NewBlockMetadata(allocationGranularity int, granularityHandler GranularityCheck) BlockMetadataBase

NewBlockMetadata creates a new BlockMetadataBase from a granularity value and handler. These are memory-system-specific and should have been provided by the consumer. See GranularityCheck for more information. If your memory system does not have granularity requirements, then allocationGranularity should be 1.

func (*BlockMetadataBase) Init 

func (m *BlockMetadataBase) Init(size int)

Init prepares this structure for allocations and sizes the block in bytes based on the parameter size.

func (*BlockMetadataBase) Size 

func (m *BlockMetadataBase) Size() int

Size returns the size of the block in bytes

func (*BlockMetadataBase) WriteBlockJson 

func (m *BlockMetadataBase) WriteBlockJson(json jwriter.ObjectState, unusedBytes, allocationCount, unusedRangeCount int)

WriteBlockJson populates a json object with information about this block

type GranularityCheck 

type GranularityCheck interface {
	// AllocRegions stores a region of memory and assigns it a memory-system-specific allocation type
	AllocRegions(allocType uint32, offset, size int)
	// FreeRegions removes a region of memory
	FreeRegions(offset, size int)
	// Clear removes all regions of memory
	Clear()
	// CheckConflictAndAlignUp is provided information about a potential allocation and attempts to find a non-
	// conflicting place for that allocation. If the offset is being placed in a location where it will conflict
	// with an existing allocation, the allocation will attempt to be nudged forward into a new slot.  An
	// updated allocation offset will be returned, along with a boolean indicating whether a non-conflicting
	// location could be found.
	//
	// allocOffset - Offset within the block of the requested allocation
	// allocSize - Size of the requested allocation
	// regionOffset - Offset within the block of the free region being allocated to
	// regionSize - Size of the free region being allocated to
	// allocType - The memory-system-specific allocation type of the requested allocation
	CheckConflictAndAlignUp(allocOffset, allocSize, regionOffset, regionSize int, allocType uint32) (int, bool)
	// RoundUpAllocRequest will return an updated alignment and size of a requested allocation, if necessary.
	// Some allocation types in some memory systems can't share or can't easily share slots with other allocations,
	// and so it is better for these allocations to expand to fill their slots in order to prevent the creation
	// of free regions that cannot be used by anyone.
	RoundUpAllocRequest(allocType uint32, allocSize int, allocAlignment uint) (int, uint)
	// AllocationsConflict will return a boolean indicating whether two memory-system-specific allocation
	// types can share the same slot.
	AllocationsConflict(firstAllocType uint32, secondAllocType uint32) bool

	// StartValidation will begin an internal consistency check on the granularity data. These checks may
	// be expensive, depending on the implementation. When an implementation is functioning correctly, it
	// should not be possible for this process to return an error, but this may assist in diagnosing issues
	// with the implementation.
	//
	// StartValidation will return a ctx object that will be passed to Validate and FinishValidation.
	StartValidation() any
	// Validate will validate a single allocation. An error will be returned if there are issues with the
	// provided region.
	//
	// ctx - The object that was returned from StartValidation
	// offset - The offset within the block of a specific allocation
	// size - The size of the allocation
	Validate(ctx any, offset, size int) error
	// FinishValidation will complete internal consistency checks and return an error if there was an issue.
	// Validate must have been called for each allocation before calling this method.
	//
	// ctx - The object that was returned from StartValidation.
	FinishValidation(ctx any) error
}

GranularityCheck represents an important concept in some memory systems. In certain memory systems (video memory being an important one), certain types of allocations cannot be too close to each other. Memory is separated into "slots" of particular size, and slots must effectively be assigned an allocation type. As a result, it is incumbent upon a memory management system to track the type assigned to each "slot" and not allow conflicting suballocations to be created.

GranularityCheck is responsible for this. For systems that do not have the concept of memory granularity, it is sufficient to create a dummy implementation that always returns success and does not store any information. Otherwise, the granularity rules of the system will need to be represented in the implementation in order to allow memutils to make good allocation decisions.

type LinearBlockMetadata 

type LinearBlockMetadata struct {
	BlockMetadataBase
	// contains filtered or unexported fields
}

func NewLinearBlockMetadata 

func NewLinearBlockMetadata(bufferImageGranularity int, granularityHandler GranularityCheck) *LinearBlockMetadata

func (*LinearBlockMetadata) AddDetailedStatistics 

func (m *LinearBlockMetadata) AddDetailedStatistics(stats *memutils.DetailedStatistics)

func (*LinearBlockMetadata) AddStatistics 

func (m *LinearBlockMetadata) AddStatistics(stats *memutils.Statistics)

func (*LinearBlockMetadata) Alloc 

func (m *LinearBlockMetadata) Alloc(req AllocationRequest, allocType uint32, userData any) error

func (*LinearBlockMetadata) AllocationCount 

func (m *LinearBlockMetadata) AllocationCount() int

func (*LinearBlockMetadata) AllocationListBegin 

func (m *LinearBlockMetadata) AllocationListBegin() (BlockAllocationHandle, error)

func (*LinearBlockMetadata) AllocationOffset 

func (m *LinearBlockMetadata) AllocationOffset(allocHandle BlockAllocationHandle) (int, error)

func (*LinearBlockMetadata) AllocationUserData 

func (m *LinearBlockMetadata) AllocationUserData(allocHandle BlockAllocationHandle) (any, error)

func (*LinearBlockMetadata) BlockJsonData 

func (m *LinearBlockMetadata) BlockJsonData(json jwriter.ObjectState)

func (*LinearBlockMetadata) CheckCorruption 

func (m *LinearBlockMetadata) CheckCorruption(blockData unsafe.Pointer) error

func (*LinearBlockMetadata) Clear 

func (m *LinearBlockMetadata) Clear()

func (*LinearBlockMetadata) CreateAllocationRequest 

func (m *LinearBlockMetadata) CreateAllocationRequest(
	allocSize int, allocAlignment uint,
	upperAddress bool,
	allocType uint32,
	strategy AllocationStrategy,
	maxOffset int,
) (bool, AllocationRequest, error)

func (*LinearBlockMetadata) FindNextAllocation 

func (m *LinearBlockMetadata) FindNextAllocation(allocHandle BlockAllocationHandle) (BlockAllocationHandle, error)

func (*LinearBlockMetadata) Free 

func (m *LinearBlockMetadata) Free(allocHandle BlockAllocationHandle) error

func (*LinearBlockMetadata) FreeRegionsCount 

func (m *LinearBlockMetadata) FreeRegionsCount() int

func (*LinearBlockMetadata) Init 

func (m *LinearBlockMetadata) Init(size int)

func (*LinearBlockMetadata) IsEmpty 

func (m *LinearBlockMetadata) IsEmpty() bool

func (*LinearBlockMetadata) MayHaveFreeBlock 

func (m *LinearBlockMetadata) MayHaveFreeBlock(allocType uint32, size int) bool

func (*LinearBlockMetadata) SetAllocationUserData 

func (m *LinearBlockMetadata) SetAllocationUserData(allocHandle BlockAllocationHandle, userData any) error

func (*LinearBlockMetadata) SumFreeSize 

func (m *LinearBlockMetadata) SumFreeSize() int

func (*LinearBlockMetadata) SupportsRandomAccess 

func (m *LinearBlockMetadata) SupportsRandomAccess() bool

func (*LinearBlockMetadata) Validate 

func (m *LinearBlockMetadata) Validate() error

func (*LinearBlockMetadata) VisitAllRegions 

func (m *LinearBlockMetadata) VisitAllRegions(handleBlock func(handle BlockAllocationHandle, offset int, size int, userData any, free bool) error) error

type SecondVectorMode 

type SecondVectorMode uint32
const (
	SecondVectorModeEmpty SecondVectorMode = iota
	SecondVectorModeRingBuffer
	SecondVectorModeDoubleStack
)

func (SecondVectorMode) String 

func (m SecondVectorMode) String() string

type Suballocation 

type Suballocation struct {
	Offset   int
	Size     int
	UserData any
	Type     uint32
}

type TLSFBlockMetadata 

type TLSFBlockMetadata struct {
	BlockMetadataBase
	// contains filtered or unexported fields
}

func NewTLSFBlockMetadata 

func NewTLSFBlockMetadata(bufferImageGranularity int, granularityHandler GranularityCheck) *TLSFBlockMetadata

func (*TLSFBlockMetadata) AddDetailedStatistics 

func (m *TLSFBlockMetadata) AddDetailedStatistics(stats *memutils.DetailedStatistics)

func (*TLSFBlockMetadata) AddStatistics 

func (m *TLSFBlockMetadata) AddStatistics(stats *memutils.Statistics)

func (*TLSFBlockMetadata) Alloc 

func (m *TLSFBlockMetadata) Alloc(req AllocationRequest, suballocType uint32, userData any) error

func (*TLSFBlockMetadata) AllocationCount 

func (m *TLSFBlockMetadata) AllocationCount() int

func (*TLSFBlockMetadata) AllocationListBegin 

func (m *TLSFBlockMetadata) AllocationListBegin() (BlockAllocationHandle, error)

func (*TLSFBlockMetadata) AllocationOffset 

func (m *TLSFBlockMetadata) AllocationOffset(allocHandle BlockAllocationHandle) (int, error)

func (*TLSFBlockMetadata) AllocationUserData 

func (m *TLSFBlockMetadata) AllocationUserData(allocHandle BlockAllocationHandle) (any, error)

func (*TLSFBlockMetadata) BlockJsonData 

func (m *TLSFBlockMetadata) BlockJsonData(json jwriter.ObjectState)

func (*TLSFBlockMetadata) CheckCorruption 

func (m *TLSFBlockMetadata) CheckCorruption(blockData unsafe.Pointer) error

func (*TLSFBlockMetadata) Clear 

func (m *TLSFBlockMetadata) Clear()

func (*TLSFBlockMetadata) CreateAllocationRequest 

func (m *TLSFBlockMetadata) CreateAllocationRequest(
	allocSize int, allocAlignment uint,
	upperAddress bool,
	allocType uint32,
	strategy AllocationStrategy,
	maxOffset int,
) (bool, AllocationRequest, error)

func (*TLSFBlockMetadata) FindNextAllocation 

func (m *TLSFBlockMetadata) FindNextAllocation(alloc BlockAllocationHandle) (BlockAllocationHandle, error)

func (*TLSFBlockMetadata) Free 

func (m *TLSFBlockMetadata) Free(allocHandle BlockAllocationHandle) error

func (*TLSFBlockMetadata) FreeRegionsCount 

func (m *TLSFBlockMetadata) FreeRegionsCount() int

func (*TLSFBlockMetadata) Init 

func (m *TLSFBlockMetadata) Init(size int)

func (*TLSFBlockMetadata) IsEmpty 

func (m *TLSFBlockMetadata) IsEmpty() bool

func (*TLSFBlockMetadata) MayHaveFreeBlock 

func (m *TLSFBlockMetadata) MayHaveFreeBlock(allocType uint32, size int) bool

func (*TLSFBlockMetadata) SetAllocationUserData 

func (m *TLSFBlockMetadata) SetAllocationUserData(allocHandle BlockAllocationHandle, userData any) error

func (*TLSFBlockMetadata) SumFreeSize 

func (m *TLSFBlockMetadata) SumFreeSize() int

func (*TLSFBlockMetadata) SupportsRandomAccess 

func (m *TLSFBlockMetadata) SupportsRandomAccess() bool

func (*TLSFBlockMetadata) Validate 

func (m *TLSFBlockMetadata) Validate() error

func (*TLSFBlockMetadata) VisitAllRegions 

func (m *TLSFBlockMetadata) VisitAllRegions(handleBlock func(handle BlockAllocationHandle, offset int, size int, userData any, free bool) error) error

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.