Crate rarena_allocator

rarena-allocator

Lock-free ARENA allocator which can be used in both memory and on-disk.

Introduction

rarena-allocator is a lock-free concurrent-safe ARENA implementation, the underlying memory can from either an allocation or memory map, which means that the allocator can be restored.

There are 3 kinds of main memory:

1. AlignedVec
2. file backed memory map
3. anon memory map

There are 3 kinds of freelist:

1. None

   Disable freelist, once main memory is consumed out, then this ARENA cannot allocate anymore.

2. Optimistic

   A lock-free linked list which ordered by segment size (descending), when allocating, pop the head segment.

   e.g.

   freelist: 100 -> 96 -> 50.

   The head segment size is 100, we want 20, then the head will be removed from the linked list, give out 20, the remaining 80 will be inserted back to the freelist if it is larger than Options::minimum_segment_size().

   After this allocation, the freelist will be 96 -> 80 -> 50.

3. Pessimistic

   A lock-free linked list which ordered by segment size (ascending), when allocating, find the most suitable segment.

   e.g.

   freelist: 42 -> 84 -> 100.

   If we want 50, then the second segment will be removed from the linked list, give out 50, the remaining 34 will be inserted back to the freelist if it is larger than Options::minimum_segment_size().

   After this allocation, the freelist will be 34 -> 42 -> 100.

The allocation policy used in the implementation is that, first try to allocate from main memory, main memory is increase-only, so it is blazing fast if main memory has enough space, at the same time, ARENA will collect dropped segments to construct a freelist (lock-free linked list). When the main memory does not have space, the ARENA will try to allocate from the freelist.

This crate contains many unsafe code, although the main functionalities of this crate are well tested by miri, loom and sanitizer, please use it at your own risk.

Memory Layout

• Pure memory layout, only Vec and anon memory map backed main memory support this layout, this layout cannot be recovered.

  --------------------------------------
  |           1 byte          | ...... |
  --------------------------------------
  | reserved as null pointer  |  data  |
  --------------------------------------

• Unify memory layout, all 3 backed memroy will use the same memory layout. Controlled by Options::with_unify(true)

  --------------------------------------------------------------------------------------------------------------
  |           1 byte          |    1 byte     |   2 bytes    |      2 bytes     | 2 bytes |  32 bytes | ...... |
  --------------------------------------------------------------------------------------------------------------
  | reserved as null pointer  | freelist kind |  magic text  | external version | version |   header  |  data  |
  --------------------------------------------------------------------------------------------------------------

Installation

[dependencies]
rarena-allocator = "0.5"

• no_std

  [dependencies]
  rarena-allocator = { version = "0.5", default-features = false, features = ["alloc"] }

• Enable memory map backed main memory

  [dependencies]
  rarena-allocator = { version = "0.5", features = ["memmap"] }

License

rarena-allocator is under the terms of both the MIT license and the Apache License (Version 2.0).

See LICENSE-APACHE, LICENSE-MIT for details.

Copyright (c) 2024 Al Liu.

Re-exports

pub use either;

Modules

checksum

Traits and structs for checksuming.

sync

Lock-free allocator allocator can be used in concurrent environments.

unsync

allocator allocator for single-threaded environments.

Structs

BytesMut

A owned buffer that allocated by the ARENA

BytesRefMut

A buffer that allocated by the ARENA

IncompleteBuffer

Returned when the buffer does not contains engouth bytes for decoding.

InsufficientBuffer

Returned when the encoded buffer is too small to hold the bytes format of the types.

Meta

The metadata of the structs allocated from ARENA.

Options

Options for creating an ARENA

Owned

An owned to a value T in the ARENA.

RefMut

A mutable reference to a value T in the ARENA.

UnknownFreelist

Unknown freelist error.

Enums

ArenaPosition

Enumeration of possible methods to seek within an Allocator.

DecodeVarintError

Decoding varint error.

Error

An error indicating that the arena is full

Freelist

The freelist configuration for the ARENA.

Traits

Allocator

A trait for easily interacting with the sync and unsync allocator allocators.

Buffer

The memory chunk allocated from the allocator.

Functions

align_offset

Calculates the aligned offset for a given type T starting from current_offset.