rhdl_ubft/kv/

hash_table.rs

//! Transactional cuckoo table, nine true synchronous RAM banks of 64 entries.
//! Transactions are serialized; responses hold until consumed. Reset discards all
//! in-flight work and scrubs every RAM address before accepting another request.
//!
//! The central invariant is that no request can observe an unfinished eviction.
//! A successful insertion keeps its writes; an exhausted insertion restores
//! every overwritten entry before publishing failure. Holding the response
//! also holds off the next request, which makes the transaction boundary clear.
//!
//! State encoding: 0 scrub, 1 idle/admit, 2 launch RAM addresses, 3 inspect RAM
//! results, 4 undo one journal entry. New requests launch their RAM addresses
//! on admission. Evicted victims still use state 2 to launch their new address.
//! Reset clears the table; it does not restore a persistent pre-reset snapshot.
//!
//! Transfers occur on rising edges with valid and ready asserted. Producers
//! retain valid and payload until transfer. Simultaneous lookup/update requests
//! alternate admission preference; a stalled response blocks further admission.
//! Reset suppresses request and response handshakes.
use super::tabulation::hashes;
use rhdl::prelude::*;
use rhdl_fpga::core::{
    dff::DFF,
    ram::synchronous::{RamStyle, SyncBRAM},
};

#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
/// One lookup; hold its fields until `valid && lookup_request_ready`.
pub struct LookupReq {
    /// A lookup is offered; hold key/source until its request handshake.
    pub valid: bool,
    /// Full 64-bit key; zero is a valid key.
    pub key: b64,
    /// Opaque caller bit echoed in the response; it grants no access rights.
    pub source: bool,
}
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
/// A held result. A miss always returns value zero; consult `hit` to distinguish
/// that miss from a stored zero value.
pub struct LookupResp {
    /// Response pending; retained until lookup_response_ready.
    pub valid: bool,
    /// Original request key.
    pub key: b64,
    /// Stored value on hit, otherwise zero.
    pub value: b16,
    /// Original request source bit, echoed without interpretation.
    pub source: bool,
    /// A valid entry matched the full key.
    pub hit: bool,
}
/// op=0 upsert, op=1 delete. This is a semantic API, not HLS enum packing.
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
pub struct UpdateReq {
    /// An update is offered; hold all fields until its request handshake.
    pub valid: bool,
    /// Zero upserts; one deletes all matching candidates.
    pub op: b1,
    /// Full 64-bit key to update.
    pub key: b64,
    /// Replacement value for upsert; ignored for deletion but echoed.
    pub value: b16,
    /// Opaque caller bit echoed unchanged; not authorization.
    pub source: bool,
}
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
/// Upsert success means the entry is installed. Delete success means an entry
/// existed. Failed upsert means all eviction writes have already been undone.
pub struct UpdateResp {
    /// Response pending; retained until update_response_ready.
    pub valid: bool,
    /// Original requested operation.
    pub op: b1,
    /// Original request key, never a displaced victim key.
    pub key: b64,
    /// Original request value, including for deletion and failed insertion.
    pub value: b16,
    /// Original request source bit.
    pub source: bool,
    /// Upsert installed, or deletion found an entry; false otherwise.
    pub success: bool,
}
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
/// Requests and response-consumer readiness for the serialized table.
pub struct HashTableIn {
    /// Lookup request channel.
    pub lookup: LookupReq,
    /// Upsert/delete request channel.
    pub update: UpdateReq,
    /// Consumer accepts a valid lookup response this edge.
    pub lookup_response_ready: bool,
    /// Consumer accepts a valid update response this edge.
    pub update_response_ready: bool,
}
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
/// Admission readiness, held responses, and reset/diagnostic status.
pub struct HashTableOut {
    /// Admits a valid lookup this edge; depends on arbitration and response drain.
    pub lookup_request_ready: bool,
    /// Admits a valid update this edge; depends on arbitration and response drain.
    pub update_request_ready: bool,
    /// Held lookup result.
    pub lookup: LookupResp,
    /// Held update result.
    pub update: UpdateResp,
    /// Wrapping diagnostic counter, not a transaction identifier.
    pub insert_failures: b16,
    /// The reset scrub has completed; requests may now be admitted.
    pub initialized: bool,
}
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
/// One physical RAM entry; key and value are meaningful only while valid.
pub struct Entry {
    /// Occupancy bit; false marks a free location.
    pub valid: bool,
    /// Resident full-width key.
    pub key: b64,
    /// Resident application value.
    pub value: b16,
}
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
/// The old contents of one physical location, recorded before overwriting it.
/// Repeated locations remain separate records because rollback is ordered.
pub struct Undo {
    /// Physical bank index, constrained to 0 through 8.
    pub bank: b4,
    /// Six-bit address within the bank.
    pub addr: b6,
    /// Complete contents before this overwrite, including validity.
    pub entry: Entry,
}
#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
/// Transaction controller state, including the twelve-entry undo journal.
pub struct Registers {
    state: b3,
    scrub: b6,
    initialized: bool,
    prefer_update: bool,
    is_update: bool,
    // Original caller request remains unchanged throughout an eviction chain.
    request: UpdateReq,
    // Entry seeking a home: initially the request, then each displaced victim.
    pending: Entry,
    lookup: LookupResp,
    update: UpdateResp,
    failures: b16,
    journal: [Undo; 12],
    // Number of journal records written, or still to restore during rollback.
    count: b4,
    victim_index: b4,
    victim_bit: bool,
}
#[derive(Clone, Debug, Synchronous, SynchronousDQ)]
/// Nine 64-entry synchronous RAM banks with key64/value16 and bounded insertion.
/// Reset scrubs all contents. Failed insertion rolls back before reporting failure.
pub struct HashTable {
    regs: DFF<Registers>,
    banks: [SyncBRAM<Entry, 6>; 9],
}
impl Default for HashTable {
    fn default() -> Self {
        Self {
            regs: DFF::new(Registers::default()),
            banks: std::array::from_fn(|_| SyncBRAM::default().with_style(RamStyle::Block)),
        }
    }
}
impl SynchronousIO for HashTable {
    type I = HashTableIn;
    type O = HashTableOut;
    type Kernel = hash_table_kernel;
}

/// Advance admission, synchronous RAM access, or one rollback step.
/// Decisions read the registered snapshot; writes describe the next edge.
#[kernel]
pub fn hash_table_kernel(
    cr: ClockReset,
    i: HashTableIn,
    q: HashTableQ,
) -> (HashTableOut, HashTableD) {
    // q is the registered state for this cycle; d/r describe the next edge.
    // Read q for decisions so one transition cannot cascade through two states.
    let mut d = HashTableD::dont_care();
    let mut r = q.regs;
    // Consuming the old response frees its slot on this edge. Admission may
    // share that edge, but a stalled response still owns the transaction.
    let idle = q.regs.state == b3(1)
        && (!q.regs.lookup.valid || i.lookup_response_ready)
        && (!q.regs.update.valid || i.update_response_ready)
        && !cr.reset.any();
    // With both callers waiting, the previous winner yields to the other.
    // With only one caller, no preference bit can unnecessarily block it.
    let accept_update = idle && (!i.lookup.valid || q.regs.prefer_update);
    let accept_lookup = idle && (!i.update.valid || !q.regs.prefer_update);
    // Select the key before hashing, so admission reuses the same nine hash
    // networks as eviction. No writes occur in the admission state.
    let mut read_key = q.regs.pending.key;
    if accept_update && i.update.valid {
        read_key = i.update.key;
    } else if accept_lookup && i.lookup.valid {
        read_key = i.lookup.key;
    }
    let addresses = hashes(read_key);
    for bank in 0..9 {
        d.banks[bank].read_addr = addresses[bank];
        d.banks[bank].write.addr = addresses[bank];
        d.banks[bank].write.value = q.regs.pending;
        d.banks[bank].write.enable = false;
    }
    let mut o = HashTableOut {
        lookup_request_ready: accept_lookup,
        update_request_ready: accept_update,
        lookup: q.regs.lookup,
        update: q.regs.update,
        insert_failures: q.regs.failures,
        initialized: q.regs.initialized && !cr.reset.any(),
    };
    if i.lookup_response_ready {
        r.lookup.valid = false;
    }
    if i.update_response_ready {
        r.update.valid = false;
    }
    if !cr.reset.any() {
        if q.regs.state == b3(0) {
            // Clear all banks in parallel, one address per cycle. No BRAM reset
            // inference is assumed, including when reset interrupts eviction.
            for bank in 0..9 {
                d.banks[bank].write.addr = q.regs.scrub;
                d.banks[bank].write.value = Entry {
                    valid: false,
                    key: b64(0),
                    value: b16(0),
                };
                d.banks[bank].write.enable = true;
            }
            r.scrub = q.regs.scrub + b6(1);
            if q.regs.scrub == b6(63) {
                r.state = b3(1);
                r.initialized = true;
            }
        } else if q.regs.state == b3(1) {
            if accept_update && i.update.valid {
                r.request = i.update;
                r.pending = Entry {
                    valid: true,
                    key: i.update.key,
                    value: i.update.value,
                };
                r.is_update = true;
                r.count = b4(0);
                r.victim_index = b4(0);
                r.prefer_update = false;
                // Read the accepted key immediately. The preceding operation's
                // RAM write has already committed before this admission edge.
                r.state = b3(3);
            } else if accept_lookup && i.lookup.valid {
                r.request = UpdateReq {
                    valid: true,
                    op: b1(0),
                    key: i.lookup.key,
                    value: b16(0),
                    source: i.lookup.source,
                };
                r.pending = Entry {
                    valid: true,
                    key: i.lookup.key,
                    value: b16(0),
                };
                r.is_update = false;
                r.prefer_update = true;
                r.state = b3(3);
            }
        } else if q.regs.state == b3(2) {
            // Address launch; RAM result is consumed the following cycle.
            r.state = b3(3);
        } else if q.regs.state == b3(3) {
            let mut hit = false;
            let mut hit_bank = b4(0);
            let mut value = b16(0);
            let mut free = false;
            let mut free_bank = b4(0);
            for bank in 0..9 {
                if q.banks[bank].valid && q.banks[bank].key == q.regs.pending.key {
                    hit = true;
                    hit_bank = b4(bank as u128);
                    value = q.banks[bank].value;
                }
                if !q.banks[bank].valid {
                    free = true;
                    free_bank = b4(bank as u128);
                }
            }
            if !q.regs.is_update {
                r.lookup = LookupResp {
                    valid: true,
                    key: q.regs.request.key,
                    value,
                    source: q.regs.request.source,
                    hit,
                };
                r.state = b3(1);
            } else if q.regs.request.op == b1(1) {
                for bank in 0..9 {
                    if q.banks[bank].valid && q.banks[bank].key == q.regs.pending.key {
                        d.banks[bank].write.enable = true;
                        d.banks[bank].write.value.valid = false;
                    }
                }
                r.update = UpdateResp {
                    valid: true,
                    op: q.regs.request.op,
                    key: q.regs.request.key,
                    value: q.regs.request.value,
                    source: q.regs.request.source,
                    success: hit,
                };
                r.state = b3(1);
            } else if hit || free {
                // Search every candidate for an existing key before choosing a
                // free slot. Otherwise an upsert could create a second copy.
                let chosen = if hit { hit_bank } else { free_bank };
                for bank in 0..9 {
                    if chosen == b4(bank as u128) {
                        d.banks[bank].write.enable = true;
                    }
                }
                r.update = UpdateResp {
                    valid: true,
                    op: q.regs.request.op,
                    key: q.regs.request.key,
                    value: q.regs.request.value,
                    source: q.regs.request.source,
                    success: true,
                };
                r.state = b3(1);
            } else {
                // All candidates are occupied. Save the victim before writing
                // pending in its place, then seek a home for that victim.
                // The twelfth displacement still needs a journal record even
                // though the next state immediately begins rolling it back.
                let mut victim = b4(0);
                for bank in 0..9 {
                    if q.regs.victim_index == b4(bank as u128) {
                        victim = addresses[bank].resize::<4>() & b4(7);
                    }
                }
                if q.regs.victim_bit {
                    victim = victim + b4(1);
                }
                let mut undo = Undo {
                    bank: victim,
                    addr: b6(0),
                    entry: q.regs.pending,
                };
                for bank in 0..9 {
                    if victim == b4(bank as u128) {
                        undo.addr = addresses[bank];
                        undo.entry = q.banks[bank];
                        d.banks[bank].write.enable = true;
                        r.pending = q.banks[bank];
                    }
                }
                for slot in 0..12 {
                    if q.regs.count == b4(slot as u128) {
                        r.journal[slot] = undo;
                    }
                }
                r.count = q.regs.count + b4(1);
                r.victim_bit = !q.regs.victim_bit;
                r.victim_index = if q.regs.victim_index == b4(8) {
                    b4(0)
                } else {
                    q.regs.victim_index + b4(1)
                };
                r.state = if q.regs.count == b4(11) { b3(4) } else { b3(2) };
            }
        } else if q.regs.state == b3(4) {
            // Reverse order is essential when a failed path revisits an address.
            let last = q.regs.count - b4(1);
            for slot in 0..12 {
                if last == b4(slot as u128) {
                    for bank in 0..9 {
                        if q.regs.journal[slot].bank == b4(bank as u128) {
                            d.banks[bank].write.addr = q.regs.journal[slot].addr;
                            d.banks[bank].write.value = q.regs.journal[slot].entry;
                            d.banks[bank].write.enable = true;
                        }
                    }
                }
            }
            r.count = last;
            if last == b4(0) {
                r.failures = q.regs.failures + b16(1);
                r.update = UpdateResp {
                    valid: true,
                    op: q.regs.request.op,
                    key: q.regs.request.key,
                    value: q.regs.request.value,
                    source: q.regs.request.source,
                    success: false,
                };
                r.state = b3(1);
            }
        }
    } else {
        o.lookup.valid = false;
        o.update.valid = false;
    }
    d.regs = r;
    (o, d)
}

#[cfg(test)]
#[path = "tests/hash_table.rs"]
mod tests;