futex

Documentation

Overview

Package futex provides an implementation of the futex interface as found in the Linux kernel. It allows one to easily transform Wait() calls into waits on a channel, which is useful in a Go-based kernel, for example.

Index

• type Key
• type KeyKind
• type Manager
  • func NewManager() *Manager
  • func (m *Manager) Fork() *Manager
  • func (m *Manager) LockPI(w *Waiter, t Target, addr hostarch.Addr, tid uint32, private, try bool) (bool, error)
  • func (m *Manager) Requeue(t Target, addr, naddr hostarch.Addr, private bool, nwake int, nreq int) (int, error)
  • func (m *Manager) RequeueCmp(t Target, addr, naddr hostarch.Addr, private bool, val uint32, nwake int, ...) (int, error)
  • func (m *Manager) UnlockPI(t Target, addr hostarch.Addr, tid uint32, private bool) error
  • func (m *Manager) WaitComplete(w *Waiter, t Target)
  • func (m *Manager) WaitPrepare(w *Waiter, t Target, addr hostarch.Addr, private bool, val uint32, ...) error
  • func (m *Manager) Wake(t Target, addr hostarch.Addr, private bool, bitmask uint32, n int) (int, error)
  • func (m *Manager) WakeOp(t Target, addr1, addr2 hostarch.Addr, private bool, nwake1 int, nwake2 int, ...) (int, error)
• type Target
• type Waiter
  • func NewWaiter() *Waiter

Types

type Key

type Key struct {
	// Kind is the type of the Key.
	Kind KeyKind

	// Mappable is the memory-mapped object that is represented by the Key.
	// Mappable is always nil if Kind is not KindSharedMappable, and may be nil
	// even if it is.
	Mappable memmap.Mappable

	// MappingIdentity is the MappingIdentity associated with Mappable.
	// MappingIdentity is always nil is Mappable is nil, and may be nil even if
	// it isn't.
	MappingIdentity memmap.MappingIdentity

	// If Kind is KindPrivate or KindSharedPrivate, Offset is the represented
	// memory address. Otherwise, Offset is the represented offset into
	// Mappable.
	Offset uint64
}

Key represents something that a futex waiter may wait on.

type KeyKind

type KeyKind int

KeyKind indicates the type of a Key.

const (
	// KindPrivate indicates a private futex (a futex syscall with the
	// FUTEX_PRIVATE_FLAG set).
	KindPrivate KeyKind = iota

	// KindSharedPrivate indicates a shared futex on a private memory mapping.
	// Although KindPrivate and KindSharedPrivate futexes both use memory
	// addresses to identify futexes, they do not interoperate (in Linux, the
	// two are distinguished by the FUT_OFF_MMSHARED flag, which is used in key
	// comparison).
	KindSharedPrivate

	// KindSharedMappable indicates a shared futex on a memory mapping other
	// than a private anonymous memory mapping.
	KindSharedMappable
)

type Manager

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

Manager holds futex state for a single virtual address space.

+stateify savable

func NewManager

func NewManager() *Manager

NewManager returns an initialized futex manager.

func (*Manager) Fork

func (m *Manager) Fork() *Manager

Fork returns a new Manager. Shared futex clients using the returned Manager may interoperate with those using m.

func (*Manager) LockPI

func (m *Manager) LockPI(w *Waiter, t Target, addr hostarch.Addr, tid uint32, private, try bool) (bool, error)

LockPI attempts to lock the futex following the Priority-inheritance futex rules. The lock is acquired only when 'addr' points to 0. The TID of the calling task is set to 'addr' to indicate the futex is owned. It returns true if the futex was successfully acquired.

FUTEX_OWNER_DIED is only set by the Linux when robust lists are in use (see exit_robust_list()). Given we don't support robust lists, although handled below, it's never set.

func (*Manager) Requeue

func (m *Manager) Requeue(t Target, addr, naddr hostarch.Addr, private bool, nwake int, nreq int) (int, error)

Requeue wakes up to nwake waiters on the given addr, and unconditionally requeues up to nreq waiters on naddr.

func (*Manager) RequeueCmp

func (m *Manager) RequeueCmp(t Target, addr, naddr hostarch.Addr, private bool, val uint32, nwake int, nreq int) (int, error)

RequeueCmp atomically checks that the addr contains val (via the Target), wakes up to nwake waiters on addr and then unconditionally requeues nreq waiters on naddr.

func (*Manager) UnlockPI

func (m *Manager) UnlockPI(t Target, addr hostarch.Addr, tid uint32, private bool) error

UnlockPI unlocks the futex following the Priority-inheritance futex rules. The address provided must contain the caller's TID. If there are waiters, TID of the next waiter (FIFO) is set to the given address, and the waiter woken up. If there are no waiters, 0 is set to the address.

func (*Manager) WaitComplete

func (m *Manager) WaitComplete(w *Waiter, t Target)

WaitComplete must be called when a Waiter previously added by WaitPrepare is no longer eligible to be woken.

func (*Manager) WaitPrepare

func (m *Manager) WaitPrepare(w *Waiter, t Target, addr hostarch.Addr, private bool, val uint32, bitmask uint32) error

WaitPrepare atomically checks that addr contains val (via the Checker), then enqueues w to be woken by a send to w.C. If WaitPrepare returns nil, the Waiter must be subsequently removed by calling WaitComplete, whether or not a wakeup is received on w.C.

func (*Manager) Wake

func (m *Manager) Wake(t Target, addr hostarch.Addr, private bool, bitmask uint32, n int) (int, error)

Wake wakes up to n waiters matching the bitmask on the given addr. The number of waiters woken is returned.

func (*Manager) WakeOp

func (m *Manager) WakeOp(t Target, addr1, addr2 hostarch.Addr, private bool, nwake1 int, nwake2 int, op uint32) (int, error)

WakeOp atomically applies op to the memory address addr2, wakes up to nwake1 waiters unconditionally from addr1, and, based on the original value at addr2 and a comparison encoded in op, wakes up to nwake2 waiters from addr2. It returns the total number of waiters woken.

type Target

type Target interface {
	context.Context

	// SwapUint32 gives access to hostarch.IO.SwapUint32.
	SwapUint32(addr hostarch.Addr, new uint32) (uint32, error)

	// CompareAndSwap gives access to hostarch.IO.CompareAndSwapUint32.
	CompareAndSwapUint32(addr hostarch.Addr, old, new uint32) (uint32, error)

	// LoadUint32 gives access to hostarch.IO.LoadUint32.
	LoadUint32(addr hostarch.Addr) (uint32, error)

	// GetSharedKey returns a Key with kind KindSharedPrivate or
	// KindSharedMappable corresponding to the memory mapped at address addr.
	//
	// If GetSharedKey returns a Key with a non-nil MappingIdentity, a
	// reference is held on the MappingIdentity, which must be dropped by the
	// caller when the Key is no longer in use.
	GetSharedKey(addr hostarch.Addr) (Key, error)
}

Target abstracts memory accesses and keys.

type Waiter

type Waiter struct {

	// C is sent to when the Waiter is woken.
	C chan struct{}
	// contains filtered or unexported fields
}

Waiter is the struct which gets enqueued into buckets for wake up routines and requeue routines to scan and notify. Once a Waiter has been enqueued by WaitPrepare(), callers may listen on C for wake up events.

func NewWaiter

func NewWaiter() *Waiter

NewWaiter returns a new unqueued Waiter.