001/*
002 * Copyright 2026 Revetware LLC.
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.revetsec.saml;
018
019import org.jspecify.annotations.NonNull;
020import org.jspecify.annotations.Nullable;
021
022import javax.annotation.concurrent.ThreadSafe;
023import java.time.Clock;
024import java.time.Duration;
025import java.time.Instant;
026import java.util.Comparator;
027import java.util.HashMap;
028import java.util.Map;
029import java.util.Objects;
030import java.util.PriorityQueue;
031import java.util.concurrent.TimeUnit;
032import java.util.concurrent.locks.ReentrantLock;
033
034/**
035 * Bounded, process-local SAML assertion replay cache. A restart loses its records; use a shared
036 * {@link SamlReplayCache} for more than one node. Live entries are never evicted. Expired records
037 * are removed only when a subsequent write observes a clock at least as late as every prior write.
038 * A clock rollback refuses new admissions until time catches up.
039 *
040 * @since 1.0.0
041 */
042@ThreadSafe
043public final class InMemorySamlReplayCache implements SamlReplayCache {
044    private static final int MAXIMUM_ENTRIES = 1_000_000;
045    private static final @NonNull Duration MAXIMUM_BUDGET = Duration.ofSeconds(30);
046
047    private final @NonNull ReentrantLock lock = new ReentrantLock();
048    private final @NonNull Map<@NonNull String, @NonNull ReplayEntry> entries = new HashMap<>();
049    private final @NonNull Map<@NonNull String, @NonNull Integer> connectionCounts = new HashMap<>();
050    private final @NonNull PriorityQueue<@NonNull ExpiryEntry> expiryIndex =
051            new PriorityQueue<>(Comparator.comparing(ExpiryEntry::expiresAt));
052    private final @NonNull Clock clock;
053    private final int maximumEntries;
054    private final int maximumPerConnection;
055    private final @Nullable Map<@NonNull String, @NonNull Integer> connectionLimits;
056    private @NonNull Instant lastObserved = Instant.MIN;
057
058    private record ReplayEntry(@NonNull String connectionId, @NonNull Instant expiresAt) { }
059    private record ExpiryEntry(@NonNull String key, @NonNull Instant expiresAt) { }
060
061    private InMemorySamlReplayCache(@NonNull Clock clock, int maximumEntries,
062            @Nullable Map<@NonNull String, @NonNull Integer> connectionLimits) {
063        this.clock = clock;
064        this.maximumEntries = maximumEntries;
065        this.maximumPerConnection = Math.max(1, maximumEntries / 4);
066        this.connectionLimits = connectionLimits;
067    }
068
069    /**
070     * Creates a volatile cache with an explicit entry limit.
071     *
072     * New namespaced admissions are limited to one quarter of the total
073     * capacity (at least one). Legacy three-argument admissions retain the
074     * full configured capacity. This shared-pool heuristic does not reserve capacity for mutually
075     * untrusted connections; use {@link #fromConnectionLimits(Clock, Map)} for fixed independent reservations.
076     *
077     * @param clock the time source used for admission and expiry
078     * @param maximumEntries maximum number of live replay records, from 1 to 1000000
079     * @return a new empty cache
080     * @since 1.0.0
081     */
082    public static @NonNull InMemorySamlReplayCache fromLimit(@NonNull Clock clock,
083            @NonNull Integer maximumEntries) {
084        Objects.requireNonNull(clock);
085        Objects.requireNonNull(maximumEntries);
086        if (maximumEntries < 1 || maximumEntries > MAXIMUM_ENTRIES)
087            throw new IllegalArgumentException("Invalid SAML replay cache capacity");
088        return new InMemorySamlReplayCache(clock, maximumEntries, null);
089    }
090
091    /**
092     * Creates fixed independent replay reservations for application-approved IdP connections. Each connection
093     * can use its entire configured quota even after all others fill theirs. Unknown connection IDs and the
094     * namespace-free admission overload cannot consume reserved capacity. Live replay marks are never evicted.
095     * <p>
096     * Configuration is snapshotted without reading the clock. There is no borrowing or live reconfiguration;
097     * replacing a populated cache requires an application transition preserving every still-live replay mark.
098     * This remains a volatile, single-process cache; restart loses replay protection.
099     *
100     * @param clock admission and expiry clock
101     * @param connectionLimits 1–1024 trusted connection IDs, each nonempty and at most 256 characters, with
102     *                         positive quotas totaling at most 1000000 live records
103     * @return an empty cache with immutable reservations
104     * @throws NullPointerException if the clock, map, a connection ID or quota is null
105     * @throws IllegalArgumentException if a configuration bound is exceeded
106     * @since 1.0.0
107     */
108    public static @NonNull InMemorySamlReplayCache fromConnectionLimits(@NonNull Clock clock,
109            @NonNull Map<@NonNull String, @NonNull Integer> connectionLimits) {
110        Objects.requireNonNull(clock);
111        Objects.requireNonNull(connectionLimits);
112        if (connectionLimits.isEmpty() || connectionLimits.size() > 1024)
113            throw new IllegalArgumentException("Invalid SAML replay connection reservations");
114        Map<String, Integer> snapshot = Map.copyOf(connectionLimits);
115        long total = 0;
116        for (Map.Entry<String, Integer> entry : snapshot.entrySet()) {
117            if (entry.getKey().isEmpty() || entry.getKey().length() > 256 || entry.getValue() < 1)
118                throw new IllegalArgumentException("Invalid SAML replay connection reservations");
119            total += entry.getValue();
120            if (total > MAXIMUM_ENTRIES)
121                throw new IllegalArgumentException("Invalid SAML replay connection reservations");
122        }
123        return new InMemorySamlReplayCache(clock, (int) total, snapshot);
124    }
125
126    /**
127     * Creates a volatile cache with 65536 slots and the system UTC clock.
128     *
129     * @return a new cache
130     * @since 1.0.0
131     */
132    public static @NonNull InMemorySamlReplayCache fromDefaults() {
133        return fromLimit(Clock.systemUTC(), 65_536);
134    }
135
136    @Override public @NonNull MarkResult markIfAbsent(@NonNull String key, @NonNull Instant expiresAt,
137            @NonNull Duration remaining) {
138        return mark("", key, expiresAt, remaining);
139    }
140
141    @Override public @NonNull MarkResult markIfAbsent(@NonNull String connectionId,
142            @NonNull String key, @NonNull Instant expiresAt, @NonNull Duration remaining) {
143        Objects.requireNonNull(connectionId);
144        if (connectionId.isEmpty()) throw new IllegalArgumentException("Empty SAML connection namespace");
145        return mark(connectionId, key, expiresAt, remaining);
146    }
147
148    private @NonNull MarkResult mark(@NonNull String connectionId, @NonNull String key,
149            @NonNull Instant expiresAt, @NonNull Duration remaining) {
150        Objects.requireNonNull(key);
151        Objects.requireNonNull(expiresAt);
152        Objects.requireNonNull(remaining);
153        if (key.isEmpty()) throw new IllegalArgumentException("Empty SAML replay key");
154        if (remaining.isZero() || remaining.isNegative() || Thread.currentThread().isInterrupted())
155            return MarkResult.UNAVAILABLE;
156        if (this.connectionLimits != null && !this.connectionLimits.containsKey(connectionId))
157            return MarkResult.CAPACITY_REFUSED;
158        Duration bounded = remaining.compareTo(MAXIMUM_BUDGET) > 0 ? MAXIMUM_BUDGET : remaining;
159        long deadline = System.nanoTime() + bounded.toNanos();
160        try {
161            long wait = deadline - System.nanoTime();
162            if (wait <= 0 || !lock.tryLock(wait, TimeUnit.NANOSECONDS)) return MarkResult.UNAVAILABLE;
163        } catch (InterruptedException exception) {
164            Thread.currentThread().interrupt();
165            return MarkResult.UNAVAILABLE;
166        }
167        try {
168            if (expired(deadline)) return MarkResult.UNAVAILABLE;
169            Instant now;
170            try { now = clock.instant(); }
171            catch (RuntimeException exception) { return MarkResult.UNAVAILABLE; }
172            if (now.isBefore(lastObserved)) return MarkResult.UNAVAILABLE;
173            lastObserved = now;
174            // A stale key cannot become fresh before the accepting caller's own expiry fence.
175            if (!now.isBefore(expiresAt)) return MarkResult.UNAVAILABLE;
176            ReplayEntry existing = entries.get(key);
177            if (existing != null && now.isBefore(existing.expiresAt())) return MarkResult.ALREADY_PRESENT;
178            reclaimExpired(now);
179            if (entries.size() >= maximumEntries) return MarkResult.CAPACITY_REFUSED;
180            int connectionLimit = this.connectionLimits == null ? this.maximumPerConnection
181                    : this.connectionLimits.getOrDefault(connectionId, 0);
182            if (!connectionId.isEmpty()
183                    && connectionCounts.getOrDefault(connectionId, 0) >= connectionLimit)
184                return MarkResult.CAPACITY_REFUSED;
185            if (expired(deadline)) return MarkResult.UNAVAILABLE;
186            entries.put(key, new ReplayEntry(connectionId, expiresAt));
187            expiryIndex.add(new ExpiryEntry(key, expiresAt));
188            if (!connectionId.isEmpty()) connectionCounts.merge(connectionId, 1, Integer::sum);
189            return expired(deadline) ? MarkResult.INDETERMINATE : MarkResult.MARKED;
190        } finally {
191            lock.unlock();
192        }
193    }
194
195    private void reclaimExpired(@NonNull Instant now) {
196        while (true) {
197            ExpiryEntry earliest = expiryIndex.peek();
198            if (earliest == null || now.isBefore(earliest.expiresAt())) return;
199            expiryIndex.remove();
200            ReplayEntry entry = entries.get(earliest.key());
201            if (entry == null || !entry.expiresAt().equals(earliest.expiresAt())) continue;
202            entries.remove(earliest.key());
203            if (!entry.connectionId().isEmpty()) {
204                int count = connectionCounts.getOrDefault(entry.connectionId(), 0) - 1;
205                if (count == 0) connectionCounts.remove(entry.connectionId());
206                else connectionCounts.put(entry.connectionId(), count);
207            }
208        }
209    }
210
211    static boolean expired(long deadline) {
212        return expiredAt(deadline, System.nanoTime(), Thread.currentThread().isInterrupted());
213    }
214
215    static boolean expiredAt(long deadline, long now, boolean interrupted) {
216        return interrupted || deadline - now <= 0;
217    }
218
219    /** Redacts replay keys. @since 1.0.0 */
220    @Override public @NonNull String toString() { return "InMemorySamlReplayCache{entries=<redacted>}"; }
221}