Crate slotmap_careful

slotmap-careful: Wrapper for slotmap generational arena to prevent key reuse.

The slotmap generational arena implementation is efficient and easy to use. Unfortunately, it has a behavior where if a single index slot is reused about 2^31 times, its version field will wrap around, and the same key will be returned twice. This can lead to security problems in programs that rely on each for a slotmap being permanently unique.

This crate implement a wrapper around slotmap::SlotMap to prevent key reuse. It works by noticing when any slot with a very high version counter is about to become empty, and instead marking such slots as permanently unusable.

Note that this new behavior can result in memory usage that grows slowly over time, even if the actual capacity of the slotmap remains low.

Modules

key_data 🔒

Hacks to extract the version and index from a slotmap key, using serde.

secondary

Contains the secondary map implementation.

Macros

define_implementation 🔒

Helper: Define a wrapper for a single SlotMap type.

new_key_type

A helper macro to create new key types. If you use a new key type for each slot map you create you can entirely prevent using the wrong key on the wrong slot map.

Structs

DefaultKey

The default slot map key type.

DenseSlotMap

A variation of slotmap::DenseSlotMap that can never give the same key for multiple objects.

DenseSlotMapValidationToken 🔒

Helper: a token constructed if the slotmap behavior matches our expectations.

HopSlotMap

A variation of slotmap::HopSlotMap that can never give the same key for multiple objects.

HopSlotMapValidationToken 🔒

Helper: a token constructed if the slotmap behavior matches our expectations.

KeyData

The actual data stored in a Key.

SecondaryMap

Secondary map, associate data with previously stored elements in a slot map.

SlotMap

A variation of slotmap::SlotMap that can never give the same key for multiple objects.

SlotMapValidationToken 🔒

Helper: a token constructed if the slotmap behavior matches our expectations.

SparseSecondaryMap

Sparse secondary map, associate data with previously stored elements in a slot map.

Enums

Entry 🔒

A single entry in one of our careful slotmaps.

Constants

SATURATE_AT_VERSION 🔒

The maximal version that we allow a key to reach.

Traits

Key

Key used to access stored values in a slot map.

Functions

key_okay 🔒

Return true if this key is apparently valid.

key_slot 🔒

Helper: return the slot of a key, assuming that the representation is as we expect.

key_version_is_maximal 🔒

Return true if the version number for this key should not be allowed to grow any larger.

validate_dense_slot_map_behavior 🔒

Spot-check whether SlotMap has changed its key encoding behavior; panic if so.

validate_hop_slot_map_behavior 🔒

Spot-check whether SlotMap has changed its key encoding behavior; panic if so.

validate_slot_map_behavior 🔒

Spot-check whether SlotMap has changed its key encoding behavior; panic if so.