hkgate

Enterprise-grade C library providing an in-flight de-duplication gate keyed only by SHA-256(body) using process-shared memory (POSIX shm_open + mmap).

Scope

hkgate is an execution guard, not an idempotency layer. It suppresses concurrent duplicates of the same body hash. It does not store responses, track operation outcomes, or distinguish in-flight from completed work — HK_DROP means "another caller owns this hash right now or recently," not "here is the previous result." For full HTTP idempotency-key semantics (replaying the original response; distinguishing IN_PROGRESS / COMPLETED / FAILED / UNKNOWN_REQUIRES_RECOVERY; recovering from provider-timeout uncertainty) you need an outcome store layered on top of this gate.

The gate hashes the bytes you give it, not the meaning. Two semantically equivalent JSON bodies that differ in field order or whitespace produce different SHA-256s and will not deduplicate. Callers that need semantic equivalence must canonicalize before hashing.

Semantics (exact after hash finalization)

Guaranteed

• After SHA-256 finalization, hk_gate_try_acquire() is atomic across all processes:
  • If no live entry exists (slot is free, tombed, or recovered as stale), exactly one caller gets HK_ALLOW and an in-flight entry is installed.
  • While an in-flight entry exists and is not stale, all callers for the same hash get HK_DROP_INFLIGHT.
  • After hk_gate_release(), the entry transitions to a completed state; subsequent acquires of the same hash within TTL get HK_DROP_COMPLETED. Past TTL, the slot becomes reusable and the next acquire gets HK_ALLOW.
  • When the shard is saturated (every slot occupied with live, in-flight or unexpired-completed entries — and notably, with no tombstones), the call returns HK_OK with decision HK_DROP_OVERLOAD. Integrators MUST fail-closed on this decision (return HTTP 503, refuse the order), since allowing it through would defeat the gate. HK_DROP_OVERLOAD is reported as a drop, not an error, precisely so callers that "fail-closed on any non-ALLOW" are correct by default. Saturation recovery happens via periodic hk_gate_sweep (which tombs expired entries and compacts), not via in-line work on the request path.
• hk_gate_release() is idempotent: it transitions an in-flight entry to completed, and is a no-op on already-completed or absent entries.
• An entry is treated as stale and recovered (allowing the new acquire) if either:
  • its age exceeds ttl_seconds, or
  • its holder process is no longer alive (kill(pid, 0) == ESRCH) — recovery happens immediately, before TTL. Stale recoveries are counted (stale_recovered_count); dead-PID recoveries within TTL are also counted separately (pid_dead_recovered_count).

Not possible (by design)

• It is not possible to deterministically drop duplicates before reading and hashing the full body, because the key is content-derived and no client-provided early key exists.
• Therefore, multiple identical requests may hash concurrently in an unavoidable overlap window before the first finishes hashing.

Architecture

• Shared memory segment layout:
  • header (magic/version/config + atomic counters)
  • array of shard locks (pthread_mutex_t, PTHREAD_PROCESS_SHARED, robust if available)
  • fixed-capacity hash table entries
• Hash table:
  • deterministic fixed-capacity open addressing per shard segment (linear probing)
  • no pointers stored in shared memory (only plain structs)
• Sharding:
  • shard = mix64(bytes_to_u64(hash[0..7]) ^ shard_salt) % shard_count — full-hash mix plus per-segment random salt prevents adversarial concentration
  • probe start within shard uses mix64(bytes_to_u64(hash[24..31])) — disjoint bytes from shard pick, so prefix collisions don't compound
  • each shard owns a contiguous region of capacity_entries / shard_count
  • shard mutexes, counters, and entries are all 64-byte aligned (_Alignas(64) + _Static_assert) and individually padded to cache lines (no false sharing)
  • HK_CACHELINE defaults to 64 bytes but auto-detects to 128 on POWER and Apple-silicon via explicit arch macros (__powerpc64__ / __aarch64__ && __APPLE__); the on-disk header records the build-time value, so a different-toolchain attacher with a different cacheline gets a clean HK_ERR_MISMATCH rather than indexing into wrong slots

Sizing guidance

Shared memory must accommodate:

sizeof(header)              ≈ 1.4 KiB (cache-line padded counters)
+ shard_count * 64 bytes    (each mutex padded to a cache line)
+ capacity_entries * 64     (each entry is exactly one cache line)

Example: shard_count=256, capacity_entries=262144 (1024 entries/shard):

• mutexes: 256 × 64 bytes = 16 KiB
• entries: 262144 × 64 bytes = 16 MiB
• plus header/alignment

In practice, allocate >= 20 MiB for this example.

Per-shard load skew (balls-and-bins) means the most-loaded shard has expected load cap + √(2 cap log S) — about 10% over nominal at "full" global load. Size for target load factor < 0.5 to stay clear of saturation under skew. (At α=0.7 the per-shard saturation probability is ~4×10⁻³ per acquire-wave; at α=0.5 it drops below 10⁻¹².) HK_DROP_OVERLOAD is local to the saturated shard; the gate keeps serving every other shard normally.

Exchange-scale sizing

The right number is (distinct idempotent ops per request) × peak RPM × ttl_replay, divided by the target load factor.

A naïve "1M req/min × 5min" ignores fan-out: a single exchange request often dispatches several internal idempotent operations (order-place, position-update, risk-check, match, settle), each with its own body hash. With 5× fan-out, the working set is 5×.

Workload	Live entries	At α=0.7	SHM size
1M rpm × 5min, no fan-out	5M	7.2M	~480 MiB
1M rpm × 5min, 5× fan-out	25M	36M	~2.4 GiB
100k rpm × 5min, 3× fan-out	1.5M	2.2M	~150 MiB

capacity_entries must be a multiple of shard_count; aim for ~1024 entries per shard. Each entry is 64 bytes; each shard mutex is one cache line.

Defaults in examples/ (65k–262k entries) are demo-scale only. Sizing wrong = the gate enters chronic HK_DROP_OVERLOAD and refuses real orders. Size for your peak with headroom.

Operational notes

• TTL source: CLOCK_BOOTTIME (Linux) or CLOCK_MONOTONIC fallback. NTP step-back / date -s will NOT corrupt TTL semantics; the system clock may be adjusted freely. If the caller passes a non-zero now_sec, hkgate uses it verbatim — make sure all callers in the same SHM segment use the same clock domain (either all 0/auto, or all clock_gettime(CLOCK_BOOTTIME)-derived). Mixing domains will misjudge entry age.
• TTL meaning: the config has three knobs: ttl_seconds (legacy fallback), ttl_inflight_seconds (lease lifetime for OCC entries — how long a holder may hold without touch), and ttl_replay_seconds (replay window for DONE entries — how long after release the same hash returns HK_DROP_COMPLETED). Pass 0 for either of the split fields to fall back to ttl_seconds. The replay window restarts at release time.
• Acquisition token (lost-lease protection): hk_gate_try_acquire returns an opaque token on HK_ALLOW. release/touch validate it; a stale token (slot was reclaimed and reused by someone else) is treated as "not your lease" and the call no-ops. Without this, a slow caller could TTL-expire, lose its slot to another acquirer, then call release and silently steal the new lease. The token is XOR'd with a per-segment 64-bit token_obfusc random so the slot index does not leak if an integrator echoes the token in a header — without obfuscation, an attacker could map (hash → shard) by collecting echoed tokens.
• Crash safety (lock): uses robust mutexes where supported (PTHREAD_MUTEX_ROBUST). If a process dies while holding a shard lock, the next locker recovers (EOWNERDEAD + pthread_mutex_consistent), increments error_count, and continues.
  • If robust mutexes are not available, build falls back to non-robust; deadlock freedom after owner death is then not guaranteed.
• Crash safety (entry): in-flight entries record the holder PID. If the holder dies before release, retries see the dead PID and recover the slot immediately (no TTL wait). PID recycling within the TTL window is theoretically possible; treat TTL as the upper bound, not the typical recovery time.
• Stale recovery on acquire: on a matching in-flight entry, if age > ttl or the holder PID is dead, the entry is tombed and the new acquire is allowed; stale_recovered_count increments. On a matching completed entry past TTL, the entry is tombed and the new acquire is allowed (silent — completed expiry is the normal lifecycle, not an error condition).
• Long-running operations: if an op may exceed ttl_seconds, callers must periodically call hk_gate_touch to refresh the lease. Without it, sweep skips the live holder (live-PID guard) but the acquire path will still recover the slot on age alone, allowing a duplicate. Touch is the primary mechanism; the live-PID guard in sweep is a safety net.
• Sweep behavior: hk_gate_sweep runs in two passes. Pass 1 tombs expired OCC entries with dead holder PIDs and expired DONE entries. Pass 2 compacts the shard if any tombstones exist — snapshots all live entries, marks every slot FREE, then re-inserts via linear probing. This collapses tombstones to FREE and bounds the steady-state probe length. Compactions are counted (shards_compacted_count). The compact path uses the per-handle sweep_snap scratch buffer guarded by sweep_mtx so concurrent sweeps from multiple threads on the same hk_gate_t serialize on the buffer (one shard compacted at a time per process).
• Sweep cadence: the library does not run sweep on its own by default, but exposes an opt-in helper: hk_gate_sweeper_start(g, cadence_sec) spawns one detached thread that calls hk_gate_sweep on the cadence (default min(ttl_replay/4, 30s)). Run from EXACTLY ONE worker per host (e.g., nginx worker 0, sidecar). Alternatively, the integrator can wire their own background timer or systemd timer calling hk_gate_sweep(g, 0, max_to_sweep, &swept). HK_DROP_OVERLOAD recovery time is bounded by the sweep interval — once a shard saturates, it stays in OVERLOAD until the next sweep tombs expired entries on that shard. Size cadence_sec ≤ desired-SLA-recovery-time; for an exchange that's typically 5–10s.
• Audit hook: call hk_gate_set_audit(g, fn, user) to register a per-decision callback. The callback fires AFTER the shard mutex is released and receives the decision, hash, and acquisition token — wire it to your structured-log / Kafka pipeline for compliance.
• Liveness checks: an entry is "alive" if (1) kill(pid, 0) returns success, (2) /proc/<pid>/stat is readable AND its starttime matches the stored tuple AND its state is not Z/X (zombie). If /proc is inaccessible (hidepid, seccomp), liveness falls back to TTL — never aggressive recovery (avoids duplicate execution under restricted procfs).
• PID recycling: the gate stores a (pid, /proc/<pid>/stat starttime) tuple per in-flight entry, so a recycled PID is detected as "the original holder is dead" rather than mistaken for a live owner.
• Container caveats: /dev/shm must NOT be bind-mounted across PID namespaces — stored PIDs are namespace-local, and the gate has no namespace tag. Document or audit your container topology accordingly.
• Linux-only kernel features used: O_CLOEXEC on shm_open, MAP_POPULATE (prefault the SHM region, removes first-lock major fault), MADV_HUGEPAGE (best-effort transparent huge pages), CLOCK_BOOTTIME (TTL clock).
• Fork model: the SHM mapping is MAP_SHARED, so children inherit the gate handle and can use it directly. There is no MADV_DONTFORK — that flag would have caused SIGSEGV in PHP-FPM/nginx-style fork models. After fork(), the child may continue using the same hk_gate_t * (a per-process PID cache is refreshed lazily on first access). A child that inherits a parent-started background sweeper does not own that thread; closing the inherited handle in the child does not join the parent's sweeper, and the parent remains responsible for hk_gate_sweeper_stop().
• SHM compatibility: the on-disk layout version is HK_VERSION = 4. Earlier-version segments are rejected with HK_ERR_MISMATCH. Use hk_gate_destroy(name) (a thin wrapper around shm_unlink) to remove a stale segment, then reopen with create_if_missing=1. The shared library SONAME (libhkgate.so.4) signals the C ABI break to the dynamic linker.
• Init race: magic is written last with release ordering (_Atomic uint64_t). Concurrent attachers spin on an acquire-load of magic (capped at ~1s) before reading other header fields, so a creator and an attacher hitting the same fresh segment cannot read uninitialized mutexes. If two processes race the O_EXCL creation, the loser falls back to attaching to the winner's segment instead of returning an error. The shm_attach_existing path also re-validates off_mutexes / off_entries against the actual mapped size, so a corrupted or maliciously edited header cannot induce SIGBUS by pointing the entry array past the mapping.
• Entry-write race safety: entry_set writes state LAST via __atomic_store_n(..., __ATOMIC_RELEASE). The matching readers use __atomic_load_n(..., __ATOMIC_ACQUIRE), so on weakly-ordered architectures (ARM, POWER) a recoverer reading state is guaranteed to see all the field writes that preceded it (or the old state with no partial writes visible). The shard mutex is the primary synchronization, but the explicit acquire/release makes the ordering robust against future optimistic-read paths.
• Cross-host scope: the gate is single-host only. SHM is local to one kernel — running hkgate on two machines behind a load balancer does NOT prevent duplicates between them. For HA, use consistent-hash LB so the same hash always lands on the same host, OR layer a distributed coordinator on top.
• Reboot wipes the gate: tmpfs-backed SHM does not survive reboot. After reboot, every pre-reboot pending request would be re-allowed if it retries. Pair hkgate with an outcome store (DB/Kafka offset) for idempotency that must survive host reboot. The library cannot enforce this — operators must wire it explicitly, and a fresh-segment HK_LOG_WARN should trigger a deploy-blocking alert if no outcome store is configured.
• Power-of-two shard count recommended: the modulo bias from mix64() % shard_count for non-power-of-two shard counts is mathematically negligible (~1 in 5e16), but power-of-two also enables a faster bitmask reduction in future versions. No correctness impact.

Zero-downtime upgrade

Same-HK_VERSION patches: SONAME (libhkgate.so.4) is shared; old and new code attach to the same segment without coordination.

HK_VERSION bumps (layout-changing): old and new code cannot share a segment. Recommended procedure:

1. Provision a parallel segment under a new shm_name (e.g. /hk_gate_v5).
2. Roll new workers in, pointing at the new segment, while old workers continue on /hk_gate_v4.
3. Drain old worker traffic via load balancer.
4. Once drained, reap old workers and hk_gate_destroy("/hk_gate_v4").

In-place upgrade (drain → destroy → reopen) is acceptable only if the gap (duration without a populated gate) is shorter than the relevant retry window for your clients.

Security model

• SHM read access leaks the salt. shard_salt and token_obfusc live in plaintext inside the SHM segment. Any process that can shm_open the segment (typically: anyone in the same uid + supplementary group) reads them. Salt-secrecy is the basis for adversarial-key-resistance on the shard-pick and in-shard probe; once leaked, an attacker can grind hash inputs to concentrate one shard.
  • Mitigation 1 — uid isolation: dedicate a hkgate uid; only the gateway processes (nginx workers, PHP-FPM workers, sidecar) run under it. Other tenants cannot shm_open the segment.
  • Mitigation 2 — file mode: shm_open is opened with mode 0600. Verify your umask doesn't widen it. On Linux SHM is backed by /dev/shm/<name>; chmod 0600 /dev/shm/hk_gate_* post-creation is belt-and-braces.
  • Mitigation 3 — MAC: AppArmor/SELinux profile that denies read on /dev/shm/hk_gate_* for non-hkgate uids closes the gap on multi-tenant hosts.
  • Salt rotation: at every layout-version bump, the new segment gets a fresh salt. To rotate without a layout bump, use a renamed segment (/hk_gate_v4_<rotation_id>), not in-place unlink — during in-place rotation, two workers can briefly hold leases on different segments and both ALLOW the same hash. The clean procedure: provision the new name, roll workers onto it, drain the old name's traffic, then hk_gate_unlink_segment the old one. Use hk_gate_get_info(g, &info).salt_fingerprint to verify across deploy what salt rotation generation is live.

Build

Dependencies:

• OpenSSL development headers/libs (libssl, libcrypto)
• pthread

make
make test

Optional sanitizer builds:

make asan
# ThreadSanitizer generally conflicts with robust process-shared mutexes; provided for best-effort only.
make tsan

Benchmarks

Two benches: examples/bench saturates with random keys (cost-of-saturation), examples/bench_realistic reuses a 1024-key working set (production fast path).

./examples/bench_realistic — production-shaped workload (cache-resident entries, sustained acquire/release):

16 procs
~10.25M ops/s

./examples/bench — random keys, table saturates then measures HK_DROP_OVERLOAD cost:

Procs	ops/s
4	~309k
16	~432k
64	~442k

The random-keys bench deliberately saturates the table — every shard hits 100% load and every subsequent acquire walks the full probe length and returns HK_DROP_OVERLOAD. It measures the cost of saturation, not steady-state throughput. The realistic bench maps to production shapes: ~100ns per acquire+release pair on the fast path.

Hardware: standard cloud VM (your numbers will differ; the shape should hold).

Run make bench to reproduce — it prints the README baselines next to the current measurements so regressions are obvious. Single-shot, so expect ±5–10% run-to-run jitter.

Examples

• examples/demo_multiproc.c – simple multi-process acquire behavior
• examples/bench.c – random-key fill bench (measures end-to-end gate cost including HK_ERR_FULL walks)
• examples/bench_realistic.c – realistic acquire/release bench over a small key space (measures fast-path throughput)

API

See include/hkgate.h.

Minimal flow:

1. Stream request body into SHA-256 context via hk_sha256_init/update/final. The hk_sha256_ctx_t MUST be value-initialized before the first hk_sha256_init (use hk_sha256_ctx_t ctx = HK_SHA256_CTX_INIT;, = {0}, or calloc); to reuse a ctx, call hk_sha256_cleanup first. Call hk_sha256_cleanup even after final.
2. Call hk_gate_try_acquire(g, &h, now_sec, &d, &token) with the finalized hash. Pass 0 for now_sec (recommended) to use the internal CLOCK_BOOTTIME-derived clock. token is set to a non-zero opaque value on HK_ALLOW, 0 on drops.
3. Branch on the decision:
   • HK_ALLOW — process the request; when complete, call hk_gate_release(g, &h, now_sec, token) with the token from acquire. For long-running work that may exceed ttl_inflight_seconds, call hk_gate_touch(g, &h, now_sec, token) periodically.
   • HK_DROP_INFLIGHT — another caller is currently processing this; wait, return 202 Accepted, return 409 Conflict with Retry-After, or poll for completion (your contract).
   • HK_DROP_COMPLETED — the same hash was processed within the TTL replay window. hkgate does not store the original response; if you need replay semantics, layer an outcome store on top.
   • HK_DROP_OVERLOAD — the gate is saturated. Fail closed (return 503 / refuse the order). Don't fall back to ALLOW or you've defeated the gate.

Optional:

• hk_gate_set_audit(g, fn, user) — per-decision callback for compliance audit logging. Atomic swap of {fn, user}; treat as init-time configuration (each call leaks the old slot, so don't use in steady-state config-reload paths).
• hk_gate_set_logger(g, fn, user) — error/warn diagnostics. Wire BEFORE traffic so OVERLOAD/force-release/etc. emit through your structured-log pipeline.
• hk_gate_get_counters(g, &c) — aggregate metrics (allow/drop counts, recovery counts, error subtypes, probe-length histogram, compaction count).
• hk_gate_get_info(g, &info) — read-only segment metadata: shard topology, robust-mutex flag, cacheline size, salt fingerprint (for rotation auditing), fresh-segment flag (treat as deploy-blocking signal indicating reboot/unlink wiped state).
• hk_gate_fresh_segment(g) — convenience accessor; if 1, alert and verify your outcome store before accepting traffic.
• hk_gate_sweeper_start(g, cadence_sec) / hk_gate_sweeper_stop(g) — opt-in background sweeper thread (one per host).
• hk_gate_force_release(g, &h) — admin break-glass to tomb a stuck lease without torching the segment. Logs at WARN.
• hk_gate_unlink_segment(name) — shm_unlink wrapper for layout-version upgrades. (hk_gate_destroy is a deprecated alias — the old name implied a handle destructor, which it never was. Define HK_WARN_DEPRECATED to enable the deprecation warning.)