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.3"

• no_std

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

• Enable memory map backed main memory

  [dependencies]
  rarena-allocator = { version = "0.3", 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.