numballoc

README

Number allocators

Thread (and sometimes multi-process) safe number allocators.

Concurrent Bitmap

Lock-free concurrent allocator that stores state (free/used numbers) as a bitmap. Each number is a position in the bitmap: 0 means free, 1 means allocated. In conjunction with SharedMemory, it can be used as a safe way to allocate numbers across multiple processes.

Allocations are O(N) in the worst case, but the algorithm uses hints as an attempt to avoid full scans in most cases and provide a better amortized cost (probabilistic complexity analysis pending!), as long as allocations and deallocations are reasonably balanced.

package main

import (
	"fmt"

	"github.com/fabiokung/numballoc"
)

func main() {
	// shared memory can be safely used by multiple processes
	var size uint32 = 256 // bytes, can allocate 256 * 8 numbers
	mem, err := numballoc.LoadShared("my-memory-region", size)
	if err != nil {
		panic(err)
	}
	defer mem.Close()

	allocator := numballoc.ConcurrentBitmap(mem, 0)
	number, err := allocator.Allocate()
	if err != nil {
		panic(err)
	}
	fmt.Printf("%d\n", number)
	// number is guaranteed to be unique across all processes sharing the
	// same memory region
}

Concurrent Queue (LinkedList)

TBD: based on fabiokung/cqueue

Documentation

Index

• Variables
• func DestroyShared(name string) error
• type Allocator
  • func ConcurrentBitmap(mem Memory, max uint64) Allocator
• type Memory
• type SharedMemory
  • func LoadShared(name string, size uint32) (SharedMemory, error)

Variables

var ErrNoFreeNumber = errors.New("could not allocate a free number")

Functions

func DestroyShared

func DestroyShared(name string) error

DestroyShared cleans up a shared memory region

Types

type Allocator

type Allocator interface {
	// max number that can be allocated
	Max() uint64
	Allocate() (uint64, error)
	Free(uint64) error
}

func ConcurrentBitmap

func ConcurrentBitmap(mem Memory, max uint64) Allocator

ConcurrentBitmap is a lock-free allocator that stores allocations (free/used numbers) as a bitmap. Each number is a position in the bitmap: 0 means free, 1 means allocated.

mem.Size() is in bytes and each bit is a number, thus max will be min(mem.Size() * 8, max), or mem.Size() * 8 when 0 is provided.

type Memory

type Memory interface {
	Blocks() []uint32
	Size() uint32 // in bytes
}

type SharedMemory

type SharedMemory interface {
	Memory

	// Close frees up all references (so they can be GC'ed) and unmaps the
	// shared memory region
	Close() error
}

func LoadShared

func LoadShared(name string, size uint32) (SharedMemory, error)

LoadShared maps a shared memory region. Size must be consistent with all others mapping the same region (i.e.: the same name).

Loading a shared memory region using the wrong size can lead to segmentation faults (SIGSEGV), or truncated data.