| 1 |
|
| #ifndef SA_HASH_H |
| 2 |
|
| #define SA_HASH_H |
| 3 |
|
| |
| 4 |
|
| /* sa_hash.h - a fixed-capacity map several processes share. Perl-free. |
| 5 |
|
| * |
| 6 |
|
| * Open addressing with linear probing, in one carved region. Readers take no |
| 7 |
|
| * lock at all; writers take one of a stripe of spinlocks, so two writers |
| 8 |
|
| * touching different keys almost never meet. |
| 9 |
|
| * |
| 10 |
|
| * ---- fixed capacity, and no growth ------------------------------------------ |
| 11 |
|
| * |
| 12 |
|
| * The table is sized once and never rehashes. That is not a simplification to |
| 13 |
|
| * be fixed later: growing a table several processes are reading means moving |
| 14 |
|
| * entries other processes are mid-probe on, and the only safe ways to do that |
| 15 |
|
| * are to stop the world or to keep both tables alive until every reader has |
| 16 |
|
| * left. Neither belongs in something whose whole point is that a read is a hash |
| 17 |
|
| * and a compare. |
| 18 |
|
| * |
| 19 |
|
| * So a full table REFUSES a new key. `used` and `capacity` are in the stats, |
| 20 |
|
| * and a caller that reaches the ceiling wanted a bigger table. |
| 21 |
|
| * |
| 22 |
|
| * ---- tombstones, and what deleting costs ----------------------------------- |
| 23 |
|
| * |
| 24 |
|
| * A deleted entry becomes a tombstone rather than empty, because an empty slot |
| 25 |
|
| * stops a probe and a probe that stops early cannot find a key that was placed |
| 26 |
|
| * past it. Tombstones are reused by the next insert that probes over them, but |
| 27 |
|
| * they are never swept: a workload that deletes constantly will fill the table |
| 28 |
|
| * with them and start refusing keys while `used` looks low. `tombstones` is in |
| 29 |
|
| * the stats so that is visible rather than mysterious. |
| 30 |
|
| * |
| 31 |
|
| * ---- reading without a lock ------------------------------------------------- |
| 32 |
|
| * |
| 33 |
|
| * A value is read while another process may be replacing it, so each slot |
| 34 |
|
| * carries a VERSION: odd while being written, even when settled, and a reader |
| 35 |
|
| * takes it before and after copying. Same discipline as the ring's two |
| 36 |
|
| * sequence words and for the same reason - and, as there, a release store is |
| 37 |
|
| * not enough on its own. It orders what came before it and says nothing about |
| 38 |
|
| * the writes that follow, so the barriers are explicit. Getting that wrong |
| 39 |
|
| * produces whole, plausible values that belong to neither the old entry nor the |
| 40 |
|
| * new one, which is the hardest kind of bug to see. |
| 41 |
|
| * |
| 42 |
|
| * A reader that keeps losing the race gives up after a bounded number of tries |
| 43 |
|
| * and counts a `busy`. It does NOT report the key as missing: absent and |
| 44 |
|
| * could-not-read are different answers, and conflating them is how a caller |
| 45 |
|
| * ends up believing a key was deleted when a writer was simply mid-update. |
| 46 |
|
| * |
| 47 |
|
| * ---- expiry is per key, lazy, and by a wall clock --------------------------- |
| 48 |
|
| * |
| 49 |
|
| * A slot carries a deadline: 0 for never, otherwise a millisecond on the same |
| 50 |
|
| * clock the cache uses (sa_now_ms). A WALL clock rather than a monotonic one, |
| 51 |
|
| * because the deadline is written by one process and read by another, and the |
| 52 |
|
| * only clock two processes certainly agree on is the machine's. A step in it |
| 53 |
|
| * moves every deadline together, which costs at worst one round of early or |
| 54 |
|
| * late expiry. |
| 55 |
|
| * |
| 56 |
|
| * LAZY, not swept. A read that lands on an expired entry treats it as absent |
| 57 |
|
| * and turns it into a tombstone in passing, so the space comes back without a |
| 58 |
|
| * background sweeper and without a lock on the read path for the common case. |
| 59 |
|
| * An expiry a caller never reads again sits until an insert probes over it, |
| 60 |
|
| * exactly as a delete does. `expired` counts the ones collected this way, so a |
| 61 |
|
| * table full of stale keys is visible rather than mysterious. |
| 62 |
|
| * |
| 63 |
|
| * A TOMBSTONE ON EXPIRY IS A WRITE, so the reader takes the stripe lock to do |
| 64 |
|
| * it - and only to do it. A live-but-current entry is still read with no lock |
| 65 |
|
| * at all; the lock is paid once, by whoever first notices a key has died. |
| 66 |
|
| * |
| 67 |
|
| * The point of all this is the case a plain map handles wrong: a denylist, a |
| 68 |
|
| * nonce store, a dedup window. Without a deadline every caller writes its own |
| 69 |
|
| * `> time` check and its own delete, and the failure is always the same one - |
| 70 |
|
| * forgetting the check, which turns every ban permanent. |
| 71 |
|
| * |
| 72 |
|
| * Needs sa_arena.h. |
| 73 |
|
| */ |
| 74 |
|
| |
| 75 |
|
| #include "sa/sa_arena.h" |
| 76 |
|
| #include "sa/sa_time.h" |
| 77 |
|
| |
| 78 |
|
| #define SA_HASH_MAGIC 0x5048534Du /* 'M','S','H','P' little-endian */ |
| 79 |
|
| |
| 80 |
|
| /* slot states. EMPTY stops a probe; DEAD does not. */ |
| 81 |
|
| #define SA_H_EMPTY 0u |
| 82 |
|
| #define SA_H_LIVE 1u |
| 83 |
|
| #define SA_H_DEAD 2u |
| 84 |
|
| |
| 85 |
|
| /* what a lookup answers */ |
| 86 |
|
| #define SA_H_HIT 0 |
| 87 |
|
| #define SA_H_MISS 1 |
| 88 |
|
| #define SA_H_BUSY 2 |
| 89 |
|
| |
| 90 |
|
| /* what a store answers */ |
| 91 |
|
| #define SA_H_OK 1 |
| 92 |
|
| #define SA_H_FULL 0 |
| 93 |
|
| #define SA_H_TOOBIG (-1) |
| 94 |
|
| #define SA_H_NOTNUM (-2) /* incr on an entry that is not a counter */ |
| 95 |
|
| #define SA_H_WBUSY (-3) /* the stripe stayed held: try again */ |
| 96 |
|
| |
| 97 |
|
| /* FULL MEANS STOP AND BUSY MEANS TRY AGAIN, and a writer refused for a held |
| 98 |
|
| * stripe is the second one. Until 0.14 it answered SA_H_FULL, so "the table |
| 99 |
|
| * has no room for this key" and "somebody else was mid-write on this stripe |
| 100 |
|
| * and I gave up" arrived as the same value. A caller cannot act on that: the |
| 101 |
|
| * first says the table is too small, the second says do it again. |
| 102 |
|
| * |
| 103 |
|
| * AND IT WAS COUNTED NOWHERE. `full` is incremented where the probe finds no |
| 104 |
|
| * slot, which this refusal never reached, so `stats` showed a clean map while |
| 105 |
|
| * writes went missing. The only evidence was a total that came up short, which |
| 106 |
|
| * is how both of these were found and neither was diagnosed from the stats: a |
| 107 |
|
| * FreeBSD smoker read 38 where it asked for 40, an Alpine one 999 of a |
| 108 |
|
| * thousand, in a table of 64 slots holding six keys. Nothing was full, and |
| 109 |
|
| * nothing said so. |
| 110 |
|
| * |
| 111 |
|
| * `incr` returns the new value or undef, so a refusal there is a count that |
| 112 |
|
| * did not happen. It is reported now - the return value, and `busy` - because |
| 113 |
|
| * a bounded wait can always be beaten by enough contenders, and a library that |
| 114 |
|
| * cannot promise "never refused" must promise "never silently". */ |
| 115 |
|
| |
| 116 |
|
| /* How many times a reader retries a slot whose writer is mid-update before it |
| 117 |
|
| * gives up and counts a busy. A writer holds a slot odd for one memcpy, so |
| 118 |
|
| * this is generous by orders of magnitude; the bound exists so a writer that |
| 119 |
|
| * died mid-update cannot wedge a reader for ever. */ |
| 120 |
|
| #define SA_HASH_SPIN 10000 |
| 121 |
|
| |
| 122 |
|
| typedef struct { |
| 123 |
|
| volatile uint32_t state; /* SA_H_* */ |
| 124 |
|
| volatile uint32_t version; /* odd = being written */ |
| 125 |
|
| volatile uint32_t klen; |
| 126 |
|
| volatile uint32_t vlen; |
| 127 |
|
| volatile uint64_t tag; /* the hash, so most probes skip the memcmp */ |
| 128 |
|
| volatile uint64_t expires; /* ms wall clock; 0 = never */ |
| 129 |
|
| char bytes[1]; /* key then value, slot_size in total */ |
| 130 |
|
| } sa_hash_slot; |
| 131 |
|
| |
| 132 |
|
| typedef struct { |
| 133 |
|
| volatile uint32_t magic; /* published LAST at init */ |
| 134 |
|
| uint32_t slot_size; |
| 135 |
|
| uint64_t nslots; |
| 136 |
|
| uint64_t slots_off; /* from the MAP's base */ |
| 137 |
|
| volatile uint64_t used; /* live entries */ |
| 138 |
|
| volatile uint64_t tombstones; |
| 139 |
|
| volatile uint64_t busy; /* gave up: a read mid-update, or a write |
| 140 |
|
| * whose stripe stayed held */ |
| 141 |
|
| volatile uint64_t full; /* stores refused for want of room */ |
| 142 |
|
| volatile uint64_t expired; /* entries collected because they lapsed */ |
| 143 |
|
| uint32_t serialise; /* values are Struct::Codec's encoding */ |
| 144 |
|
| uint32_t pad; |
| 145 |
|
| volatile unsigned char locks[SA_LOCK_STRIPES]; |
| 146 |
|
| } sa_hash_hdr; |
| 147 |
|
| |
| 148 |
|
| #ifndef SA_HASH_FWD |
| 149 |
|
| #define SA_HASH_FWD |
| 150 |
|
| typedef struct sa_hash sa_hash; |
| 151 |
|
| #endif |
| 152 |
|
| struct sa_hash { |
| 153 |
|
| sa_region *arena; |
| 154 |
|
| sa_hash_hdr *hdr; |
| 155 |
|
| char *slots; |
| 156 |
|
| uint32_t slot_size; |
| 157 |
|
| uint64_t nslots; |
| 158 |
|
| uint64_t pair_max; /* key + value that fits one slot */ |
| 159 |
|
| uint32_t serialise; /* copied out of the header at bind */ |
| 160 |
|
| }; |
| 161 |
|
| |
| 162 |
|
| #define SA_HSLOT_AT(m, i) \ |
| 163 |
|
| ((sa_hash_slot *)((m)->slots + (size_t)((i) % (m)->nslots) * (m)->slot_size)) |
| 164 |
|
| |
| 165 |
930 |
| static uint64_t sa_hash_capacity(uint32_t slot_size) { |
| 166 |
930 |
| uint64_t hdr = (uint64_t)sizeof(sa_hash_slot) - 1; |
| 167 |
930 |
▶ | return slot_size > hdr ? (uint64_t)slot_size - hdr : 0; |
Branch: 1 branch
| Branch | True | False | Total |
| return slot_size > hdr ? (uint64_t)slot_size - hdr : 0; |
930 |
0 |
930 |
|
| 168 |
|
| } |
| 169 |
|
| |
| 170 |
622 |
| static uint64_t sa_hash_bytes(uint64_t nslots, uint32_t slot_size) { |
| 171 |
622 |
| return sa_align_up((uint64_t)sizeof(sa_hash_hdr)) |
| 172 |
622 |
| + nslots * (uint64_t)slot_size; |
| 173 |
|
| } |
| 174 |
|
| |
| 175 |
|
| /* Attach to a map in a carved region, initialising it if nobody has yet. The |
| 176 |
|
| * init race takes the same answer as everywhere else: whoever finds magic unset |
| 177 |
|
| * writes the header and stores magic last, and the rest wait bounded. */ |
| 178 |
|
| /* `serialise` is 0, 1 or SA_SER_ANY; see sa_format.h. */ |
| 179 |
312 |
| static sa_hash *sa_hash_bind(sa_region *arena, sa_reg *e, |
| 180 |
|
| uint64_t nslots, uint32_t slot_size, |
| 181 |
|
| int serialise, int *err) |
| 182 |
|
| { |
| 183 |
|
| #if !SA_HAVE_ATOMICS |
| 184 |
|
| (void)arena; (void)e; (void)nslots; (void)slot_size; (void)serialise; |
| 185 |
|
| if (err) *err = SA_E_NOATOMICS; |
| 186 |
|
| return NULL; |
| 187 |
|
| #else |
| 188 |
|
| sa_hash *m; |
| 189 |
|
| sa_hash_hdr *h; |
| 190 |
|
| uint64_t hash; |
| 191 |
|
| |
| 192 |
312 |
▶ | if (err) *err = SA_E_OK; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_OK; |
312 |
0 |
312 |
|
| 193 |
312 |
▶ | if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } |
Branch: 3 branches
| Branch | True | False | Total |
| if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } |
312 |
0 |
312 |
| if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } |
0 |
312 |
312 |
| if (!arena || !e) { if (err) *err = SA_E_NOENT; return NULL; } |
0 |
0 |
0 |
|
| 194 |
|
| |
| 195 |
312 |
| h = (sa_hash_hdr *)sa_ptr_len(arena, e->off, sizeof(sa_hash_hdr)); |
| 196 |
312 |
▶ | if (!h) { if (err) *err = SA_E_NOENT; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!h) { if (err) *err = SA_E_NOENT; return NULL; } |
0 |
312 |
312 |
| if (!h) { if (err) *err = SA_E_NOENT; return NULL; } |
0 |
0 |
0 |
|
| 197 |
|
| |
| 198 |
312 |
▶ | if (sa_at_load32_acq(&h->magic) != SA_HASH_MAGIC) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load32_acq(&h->magic) != SA_HASH_MAGIC) { |
310 |
2 |
312 |
|
| 199 |
310 |
| hash = sa_at_fnv(e->name, strlen(e->name)); |
| 200 |
310 |
▶ | if (sa_at_lock(h->locks, hash)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_lock(h->locks, hash)) { |
310 |
0 |
310 |
|
| 201 |
310 |
▶ | if (sa_at_load32_acq(&h->magic) != SA_HASH_MAGIC) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load32_acq(&h->magic) != SA_HASH_MAGIC) { |
310 |
0 |
310 |
|
| 202 |
310 |
▶ | if (!nslots || !slot_size |
Branch: 2 branches
| Branch | True | False | Total |
| if (!nslots || !slot_size |
310 |
0 |
310 |
| if (!nslots || !slot_size |
310 |
0 |
310 |
|
| 203 |
310 |
▶ | || sa_hash_capacity(slot_size) == 0 |
Branch: 1 branch
| Branch | True | False | Total |
| || sa_hash_capacity(slot_size) == 0 |
310 |
0 |
310 |
|
| 204 |
310 |
▶ | || sa_hash_bytes(nslots, slot_size) > e->len) { |
Branch: 1 branch
| Branch | True | False | Total |
| || sa_hash_bytes(nslots, slot_size) > e->len) { |
0 |
310 |
310 |
|
| 205 |
0 |
| sa_at_unlock(h->locks, hash); |
| 206 |
0 |
▶ | if (err) *err = SA_E_FULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_FULL; |
0 |
0 |
0 |
|
| 207 |
0 |
| return NULL; |
| 208 |
|
| } |
| 209 |
310 |
| memset((void *)h, 0, (size_t)sizeof(sa_hash_hdr)); |
| 210 |
310 |
| h->slot_size = slot_size; |
| 211 |
310 |
| h->nslots = nslots; |
| 212 |
310 |
▶ | h->serialise = serialise > 0 ? 1u : 0u; |
Branch: 1 branch
| Branch | True | False | Total |
| h->serialise = serialise > 0 ? 1u : 0u; |
2 |
308 |
310 |
|
| 213 |
310 |
| h->slots_off = sa_align_up((uint64_t)sizeof(sa_hash_hdr)); |
| 214 |
310 |
| sa_at_store32_rel(&h->magic, SA_HASH_MAGIC); |
| 215 |
|
| } |
| 216 |
310 |
| sa_at_unlock(h->locks, hash); |
| 217 |
|
| } |
| 218 |
310 |
▶ | if (!sa_wait_magic32(&h->magic, SA_HASH_MAGIC)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!sa_wait_magic32(&h->magic, SA_HASH_MAGIC)) { |
0 |
310 |
310 |
|
| 219 |
0 |
▶ | if (err) *err = SA_E_MAGIC; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_MAGIC; |
0 |
0 |
0 |
|
| 220 |
0 |
| return NULL; |
| 221 |
|
| } |
| 222 |
|
| } |
| 223 |
|
| |
| 224 |
|
| /* THE GEOMETRY IN THE HEADER IS ALSO SOMEBODY ELSE'S NUMBER. |
| 225 |
|
| * |
| 226 |
|
| * The branch above only checks a size when this process is the one doing |
| 227 |
|
| * the INITIALISING. A process that finds the magic already set reads the |
| 228 |
|
| * shape out of the shared header and believed it, so a header claiming |
| 229 |
|
| * four billion slots put every later read past the end of the mapping. |
| 230 |
|
| * sa_reg_ok makes `len` trustworthy; this makes the shape trustworthy. */ |
| 231 |
|
| |
| 232 |
312 |
▶ | if ((nslots && h->nslots != nslots) |
Branch: 2 branches
| Branch | True | False | Total |
| if ((nslots && h->nslots != nslots) |
312 |
0 |
312 |
| if ((nslots && h->nslots != nslots) |
312 |
0 |
312 |
|
| 233 |
312 |
▶ | || (slot_size && h->slot_size != slot_size)) { |
Branch: 2 branches
| Branch | True | False | Total |
| || (slot_size && h->slot_size != slot_size)) { |
312 |
0 |
312 |
| || (slot_size && h->slot_size != slot_size)) { |
0 |
312 |
312 |
|
| 234 |
0 |
▶ | if (err) *err = SA_E_NAME; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_NAME; |
0 |
0 |
0 |
|
| 235 |
0 |
| return NULL; |
| 236 |
|
| } |
| 237 |
312 |
▶ | if (serialise >= 0 && h->serialise != (serialise ? 1u : 0u)) { |
Branch: 3 branches
| Branch | True | False | Total |
| if (serialise >= 0 && h->serialise != (serialise ? 1u : 0u)) { |
309 |
3 |
312 |
| if (serialise >= 0 && h->serialise != (serialise ? 1u : 0u)) { |
3 |
306 |
309 |
| if (serialise >= 0 && h->serialise != (serialise ? 1u : 0u)) { |
1 |
308 |
309 |
|
| 238 |
1 |
▶ | if (err) *err = SA_E_SHAPE; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = SA_E_SHAPE; |
1 |
0 |
1 |
|
| 239 |
1 |
| return NULL; |
| 240 |
|
| } |
| 241 |
|
| |
| 242 |
311 |
| m = (sa_hash *)calloc(1, sizeof(sa_hash)); |
| 243 |
311 |
▶ | if (!m) { if (err) *err = SA_E_NOMEM; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!m) { if (err) *err = SA_E_NOMEM; return NULL; } |
0 |
311 |
311 |
| if (!m) { if (err) *err = SA_E_NOMEM; return NULL; } |
0 |
0 |
0 |
|
| 244 |
311 |
| m->arena = arena; |
| 245 |
311 |
| m->hdr = h; |
| 246 |
311 |
| m->slots = (char *)h + (size_t)h->slots_off; |
| 247 |
311 |
| m->slot_size = h->slot_size; |
| 248 |
311 |
| m->nslots = h->nslots; |
| 249 |
311 |
| m->pair_max = sa_hash_capacity(h->slot_size); |
| 250 |
311 |
| m->serialise = h->serialise; |
| 251 |
311 |
| return m; |
| 252 |
|
| #endif |
| 253 |
|
| } |
| 254 |
|
| |
| 255 |
311 |
| static void sa_hash_free(sa_hash *m) { free(m); } |
| 256 |
|
| |
| 257 |
|
| /* ---- reading, without a lock ----------------------------------------------- */ |
| 258 |
|
| |
| 259 |
|
| /* Look `key` up and copy its value into `out`. |
| 260 |
|
| * |
| 261 |
|
| * SA_H_HIT with *vlen set, SA_H_MISS, or SA_H_BUSY when a writer held the slot |
| 262 |
|
| * odd for longer than a reader was willing to wait. BUSY is deliberately not |
| 263 |
|
| * MISS: telling a caller a key is absent when it is merely being rewritten is |
| 264 |
|
| * how a cache turns an update into a delete. |
| 265 |
|
| */ |
| 266 |
|
| /* A live slot's deadline has passed. `now` of 0 means "do not check", which is |
| 267 |
|
| * how a caller that never set a TTL avoids reading the clock at all. */ |
| 268 |
|
| #define SA_H_EXPIRED(s, now) \ |
| 269 |
|
| ((now) && (s)->expires && (now) >= (s)->expires) |
| 270 |
|
| |
| 271 |
|
| /* Find the slot this key belongs in, under the caller's lock. Returns the slot |
| 272 |
|
| * to use, or NULL when the table is full. |
| 273 |
|
| * |
| 274 |
|
| * `*found` is 0 for a fresh slot (empty or tombstone, not counted in `used`), |
| 275 |
|
| * 1 for a live current match, and 2 for a live match whose deadline has passed |
| 276 |
|
| * - which is still counted in `used` but is logically absent, so the caller |
| 277 |
|
| * refreshes it in place rather than allocating, and never increments `used`. */ |
| 278 |
2697 |
| static sa_hash_slot *sa_hash_place(sa_hash *m, const char *key, uint32_t klen, |
| 279 |
|
| uint64_t tag, uint64_t now, int *found) |
| 280 |
|
| { |
| 281 |
|
| #if !SA_HAVE_ATOMICS |
| 282 |
|
| (void)m; (void)key; (void)klen; (void)tag; (void)now; (void)found; |
| 283 |
|
| return NULL; |
| 284 |
|
| #else |
| 285 |
2697 |
| uint64_t i, start = tag % m->nslots; |
| 286 |
2697 |
| sa_hash_slot *reuse = NULL; |
| 287 |
|
| |
| 288 |
2697 |
| *found = 0; |
| 289 |
3007 |
▶ | for (i = 0; i < m->nslots; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < m->nslots; i++) { |
2989 |
18 |
3007 |
|
| 290 |
2989 |
| sa_hash_slot *s = SA_HSLOT_AT(m, start + i); |
| 291 |
2989 |
| uint32_t st = sa_at_load32_acq(&s->state); |
| 292 |
|
| |
| 293 |
2989 |
▶ | if (st == SA_H_EMPTY) return reuse ? reuse : s; |
Branch: 2 branches
| Branch | True | False | Total |
| if (st == SA_H_EMPTY) return reuse ? reuse : s; |
878 |
2111 |
2989 |
| if (st == SA_H_EMPTY) return reuse ? reuse : s; |
11 |
867 |
878 |
|
| 294 |
2111 |
▶ | if (st == SA_H_DEAD) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (st == SA_H_DEAD) { |
12 |
2099 |
2111 |
|
| 295 |
|
| /* Remember the first tombstone, but keep probing: the key may be |
| 296 |
|
| * live further along, and inserting a second copy of it here would |
| 297 |
|
| * leave two entries that disagree. */ |
| 298 |
12 |
▶ | if (!reuse) reuse = s; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!reuse) reuse = s; |
11 |
1 |
12 |
|
| 299 |
12 |
| continue; |
| 300 |
|
| } |
| 301 |
2099 |
▶ | if (sa_at_load64_acq(&s->tag) == tag |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load64_acq(&s->tag) == tag |
1801 |
298 |
2099 |
|
| 302 |
1801 |
▶ | && s->klen == klen |
Branch: 1 branch
| Branch | True | False | Total |
| && s->klen == klen |
1801 |
0 |
1801 |
|
| 303 |
1801 |
▶ | && memcmp(s->bytes, key, klen) == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| && memcmp(s->bytes, key, klen) == 0) { |
1801 |
0 |
1801 |
|
| 304 |
1801 |
▶ | *found = SA_H_EXPIRED(s, now) ? 2 : 1; |
Branch: 3 branches
| Branch | True | False | Total |
| *found = SA_H_EXPIRED(s, now) ? 2 : 1; |
705 |
1096 |
1801 |
| *found = SA_H_EXPIRED(s, now) ? 2 : 1; |
705 |
0 |
705 |
| *found = SA_H_EXPIRED(s, now) ? 2 : 1; |
705 |
0 |
705 |
|
| 305 |
1801 |
| return s; |
| 306 |
|
| } |
| 307 |
|
| } |
| 308 |
18 |
| return reuse; |
| 309 |
|
| #endif |
| 310 |
|
| } |
| 311 |
|
| |
| 312 |
|
| /* Store, with an optional deadline. `ttl_ms` of 0 is "never expires"; anything |
| 313 |
|
| * else is a lifetime in milliseconds from now, and the clock is read only when |
| 314 |
|
| * one is asked for. */ |
| 315 |
|
| /* Collect an entry a reader found expired: tombstone it under the stripe lock, |
| 316 |
|
| * but only if it is STILL the same expired key - a writer may have refreshed it |
| 317 |
|
| * between the lock-free read and this lock. Best effort: if the lock is |
| 318 |
|
| * contended it is left for the next reader to notice, never waited on. */ |
| 319 |
705 |
| static void sa_hash_reap(sa_hash *m, const char *key, uint32_t klen, |
| 320 |
|
| uint64_t tag, uint64_t now) |
| 321 |
|
| { |
| 322 |
|
| #if SA_HAVE_ATOMICS |
| 323 |
705 |
| sa_hash_hdr *h = m->hdr; |
| 324 |
|
| sa_hash_slot *s; |
| 325 |
705 |
| int found = 0; |
| 326 |
|
| |
| 327 |
705 |
▶ | if (!sa_at_lock(h->locks, tag)) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!sa_at_lock(h->locks, tag)) return; |
0 |
705 |
705 |
|
| 328 |
705 |
| s = sa_hash_place(m, key, klen, tag, now, &found); |
| 329 |
705 |
▶ | if (s && found == 2) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (s && found == 2) { |
705 |
0 |
705 |
| if (s && found == 2) { |
705 |
0 |
705 |
|
| 330 |
705 |
| sa_at_store32_rel(&s->state, SA_H_DEAD); |
| 331 |
705 |
| sa_at_store32_rel(&s->vlen, 0); |
| 332 |
705 |
| sa_at_fetch_add64(&h->used, (uint64_t)-1); |
| 333 |
705 |
| sa_at_fetch_add64(&h->tombstones, 1); |
| 334 |
705 |
| sa_at_fetch_add64(&h->expired, 1); |
| 335 |
|
| } |
| 336 |
705 |
| sa_at_unlock(h->locks, tag); |
| 337 |
|
| #else |
| 338 |
|
| (void)m; (void)key; (void)klen; (void)tag; (void)now; |
| 339 |
|
| #endif |
| 340 |
|
| } |
| 341 |
|
| |
| 342 |
1146 |
| static int sa_hash_fetch(sa_hash *m, const char *key, uint32_t klen, |
| 343 |
|
| char *out, uint32_t outmax, uint32_t *vlen) |
| 344 |
|
| { |
| 345 |
|
| #if !SA_HAVE_ATOMICS |
| 346 |
|
| (void)m; (void)key; (void)klen; (void)out; (void)outmax; (void)vlen; |
| 347 |
|
| return SA_H_MISS; |
| 348 |
|
| #else |
| 349 |
1146 |
| uint64_t tag = sa_at_fnv(key, klen); |
| 350 |
1146 |
| uint64_t i, start = tag % m->nslots; |
| 351 |
|
| |
| 352 |
1194 |
▶ | for (i = 0; i < m->nslots; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < m->nslots; i++) { |
1194 |
0 |
1194 |
|
| 353 |
1194 |
| sa_hash_slot *s = SA_HSLOT_AT(m, start + i); |
| 354 |
1194 |
| uint32_t st = sa_at_load32_acq(&s->state); |
| 355 |
1194 |
| long spin = 0; |
| 356 |
|
| |
| 357 |
1194 |
▶ | if (st == SA_H_EMPTY) return SA_H_MISS; /* a probe stops here */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (st == SA_H_EMPTY) return SA_H_MISS; /* a probe stops here */ |
58 |
1136 |
1194 |
|
| 358 |
1136 |
▶ | if (st == SA_H_DEAD) continue; /* but never here */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (st == SA_H_DEAD) continue; /* but never here */ |
45 |
1091 |
1136 |
|
| 359 |
1091 |
▶ | if (sa_at_load64_acq(&s->tag) != tag) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load64_acq(&s->tag) != tag) continue; |
3 |
1088 |
1091 |
|
| 360 |
|
| |
| 361 |
0 |
| for (;;) { |
| 362 |
1088 |
| uint32_t v1 = sa_at_load32_acq(&s->version); |
| 363 |
|
| uint32_t kl, vl; |
| 364 |
|
| uint64_t exp; |
| 365 |
|
| |
| 366 |
1088 |
▶ | if (v1 & 1u) { /* mid-update: wait */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (v1 & 1u) { /* mid-update: wait */ |
0 |
1088 |
1088 |
|
| 367 |
0 |
▶ | if (++spin >= SA_HASH_SPIN) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (++spin >= SA_HASH_SPIN) { |
0 |
0 |
0 |
|
| 368 |
0 |
| sa_at_fetch_add64(&m->hdr->busy, 1); |
| 369 |
0 |
| return SA_H_BUSY; |
| 370 |
|
| } |
| 371 |
0 |
| continue; |
| 372 |
|
| } |
| 373 |
|
| |
| 374 |
1088 |
| kl = sa_at_load32_acq(&s->klen); |
| 375 |
1088 |
| vl = sa_at_load32_acq(&s->vlen); |
| 376 |
1088 |
| exp = sa_at_load64_acq(&s->expires); |
| 377 |
1088 |
▶ | if (kl != klen || (uint64_t)kl + vl > m->pair_max) break; |
Branch: 2 branches
| Branch | True | False | Total |
| if (kl != klen || (uint64_t)kl + vl > m->pair_max) break; |
1088 |
0 |
1088 |
| if (kl != klen || (uint64_t)kl + vl > m->pair_max) break; |
1088 |
0 |
1088 |
|
| 378 |
1088 |
▶ | if (memcmp(s->bytes, key, klen) != 0) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (memcmp(s->bytes, key, klen) != 0) break; |
0 |
1088 |
1088 |
|
| 379 |
|
| |
| 380 |
|
| /* THE EXPIRY CHECK COMES BEFORE THE too-big-for-buffer EARLY OUT. |
| 381 |
|
| * exists() passes a zero-length buffer, so a non-empty value takes |
| 382 |
|
| * the BUSY branch below - and an expired key returning BUSY reads |
| 383 |
|
| * as present, which is the exact bug this whole thing exists to |
| 384 |
|
| * prevent. The clock is only read when a deadline is set, so a map |
| 385 |
|
| * with no TTL still pays nothing. The reap re-verifies under the |
| 386 |
|
| * lock, so acting here on an `exp` that a concurrent refresh has |
| 387 |
|
| * already moved is harmless: a refreshed key is not collected. */ |
| 388 |
1088 |
▶ | if (exp) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (exp) { |
959 |
129 |
1088 |
|
| 389 |
959 |
| uint64_t nowms = sa_now_ms(); |
| 390 |
959 |
▶ | if (nowms >= exp) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (nowms >= exp) { |
705 |
254 |
959 |
|
| 391 |
705 |
| sa_hash_reap(m, key, klen, tag, nowms); |
| 392 |
705 |
| return SA_H_MISS; |
| 393 |
|
| } |
| 394 |
|
| } |
| 395 |
|
| |
| 396 |
383 |
▶ | if (vl > outmax) { if (vlen) *vlen = vl; return SA_H_BUSY; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (vl > outmax) { if (vlen) *vlen = vl; return SA_H_BUSY; } |
89 |
294 |
383 |
| if (vl > outmax) { if (vlen) *vlen = vl; return SA_H_BUSY; } |
89 |
0 |
89 |
|
| 397 |
|
| |
| 398 |
294 |
| memcpy(out, s->bytes + kl, (size_t)vl); |
| 399 |
294 |
| sa_at_fence_acq(); |
| 400 |
|
| |
| 401 |
|
| /* Unchanged either side of the copy? If not, what is in `out` may |
| 402 |
|
| * be half of one value and half of another. */ |
| 403 |
294 |
▶ | if (sa_at_load32_acq(&s->version) != v1) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (sa_at_load32_acq(&s->version) != v1) { |
0 |
294 |
294 |
|
| 404 |
0 |
▶ | if (++spin >= SA_HASH_SPIN) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (++spin >= SA_HASH_SPIN) { |
0 |
0 |
0 |
|
| 405 |
0 |
| sa_at_fetch_add64(&m->hdr->busy, 1); |
| 406 |
0 |
| return SA_H_BUSY; |
| 407 |
|
| } |
| 408 |
0 |
| continue; |
| 409 |
|
| } |
| 410 |
294 |
▶ | if (vlen) *vlen = vl; |
Branch: 1 branch
| Branch | True | False | Total |
| if (vlen) *vlen = vl; |
294 |
0 |
294 |
|
| 411 |
294 |
| return SA_H_HIT; |
| 412 |
|
| } |
| 413 |
|
| /* fell out of the seqlock loop: this slot is not our key */ |
| 414 |
|
| } |
| 415 |
0 |
| return SA_H_MISS; |
| 416 |
|
| #endif |
| 417 |
|
| } |
| 418 |
|
| |
| 419 |
|
| /* ---- writing, under a stripe lock ------------------------------------------ */ |
| 420 |
|
| |
| 421 |
|
| /* A WRITE PATH'S WAIT IS A GUESS ABOUT THE SCHEDULER TOO, and sa_at_lock's |
| 422 |
|
| * hundred thousand test-and-sets is the same guess sa_arena.h's sa_lock_wait |
| 423 |
|
| * was written to stop making. It burns about five milliseconds on a cache line |
| 424 |
|
| * whose owner is NOT RUNNING, then refuses - so a writer loses its write for |
| 425 |
|
| * being unlucky, not for anything being full. On a box running a dozen builds, |
| 426 |
|
| * not being scheduled for five milliseconds is ordinary. |
| 427 |
|
| * |
| 428 |
|
| * So the wait escalates, exactly as the carve path's does: a spin first, |
| 429 |
|
| * because the usual holder really is about to finish its one memcpy, then |
| 430 |
|
| * sleeps doubling from 50us. The retries after the first are a single |
| 431 |
|
| * test-and-set and never another spin - hammering the lock byte from several |
| 432 |
|
| * waiters is what keeps the HOLDER from reaching its own unlock. |
| 433 |
|
| * |
| 434 |
|
| * MUCH SHORTER THAN THE CARVE PATH'S TWO SECONDS, and deliberately. A carve is |
| 435 |
|
| * a rare operation whose caller can afford to wait; a store or an incr is on a |
| 436 |
|
| * per-request path, and a rate limiter that stalls two seconds behind a |
| 437 |
|
| * descheduled holder has done more damage than the lost count it prevented. |
| 438 |
|
| * About ten milliseconds covers an ordinary preemption, which is all that was |
| 439 |
|
| * ever wrong here, and still bounded because a process that died holding the |
| 440 |
|
| * stripe must not wedge everybody after it. That refusal is SA_H_WBUSY, so a |
| 441 |
|
| * caller that does want to insist can, and knows it is worth insisting. The |
| 442 |
|
| * loop is sa_arena.h's sa_lock_wait_brief, the same one the lease takes. */ |
| 443 |
1992 |
| static int sa_hash_wait(volatile unsigned char *locks, uint64_t h) { |
| 444 |
1992 |
| return sa_lock_wait_brief(locks, h); |
| 445 |
|
| } |
| 446 |
|
| |
| 447 |
796 |
| static int sa_hash_store_ttl(sa_hash *m, const char *key, uint32_t klen, |
| 448 |
|
| const char *val, uint32_t vlen, uint64_t ttl_ms) |
| 449 |
|
| { |
| 450 |
|
| #if !SA_HAVE_ATOMICS |
| 451 |
|
| (void)m; (void)key; (void)klen; (void)val; (void)vlen; (void)ttl_ms; |
| 452 |
|
| return SA_H_FULL; |
| 453 |
|
| #else |
| 454 |
796 |
| sa_hash_hdr *h = m->hdr; |
| 455 |
|
| uint64_t tag, exp; |
| 456 |
|
| sa_hash_slot *s; |
| 457 |
796 |
| int found = 0, rc = SA_H_OK; |
| 458 |
|
| |
| 459 |
796 |
▶ | if ((uint64_t)klen + vlen > m->pair_max) return SA_H_TOOBIG; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((uint64_t)klen + vlen > m->pair_max) return SA_H_TOOBIG; |
1 |
795 |
796 |
|
| 460 |
795 |
▶ | if (!klen) return SA_H_TOOBIG; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!klen) return SA_H_TOOBIG; |
1 |
794 |
795 |
|
| 461 |
|
| |
| 462 |
794 |
▶ | exp = ttl_ms ? sa_now_ms() + ttl_ms : 0; |
Branch: 1 branch
| Branch | True | False | Total |
| exp = ttl_ms ? sa_now_ms() + ttl_ms : 0; |
633 |
161 |
794 |
|
| 463 |
|
| |
| 464 |
794 |
| tag = sa_at_fnv(key, klen); |
| 465 |
794 |
▶ | if (!sa_hash_wait(h->locks, tag)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!sa_hash_wait(h->locks, tag)) { |
0 |
794 |
794 |
|
| 466 |
0 |
| sa_at_fetch_add64(&h->busy, 1); |
| 467 |
0 |
| return SA_H_WBUSY; |
| 468 |
|
| } |
| 469 |
|
| |
| 470 |
|
| /* now = 0: store overwrites the value and sets the new deadline whether the |
| 471 |
|
| * old entry was current or expired, so it need not tell the two apart - |
| 472 |
|
| * only whether the slot was already counted in `used`, which is found!=0. */ |
| 473 |
794 |
| s = sa_hash_place(m, key, klen, tag, 0, &found); |
| 474 |
794 |
▶ | if (!s) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!s) { |
18 |
776 |
794 |
|
| 475 |
18 |
| sa_at_unlock(h->locks, tag); |
| 476 |
18 |
| sa_at_fetch_add64(&h->full, 1); |
| 477 |
18 |
| return SA_H_FULL; |
| 478 |
|
| } |
| 479 |
|
| |
| 480 |
|
| /* Odd while writing, even when settled, with a barrier either side. The |
| 481 |
|
| * barriers are the protocol: without the first, the bytes below can reach |
| 482 |
|
| * another CPU before the odd version does, and a reader then sees new bytes |
| 483 |
|
| * under an old version and calls them whole. */ |
| 484 |
776 |
| sa_at_store32_rel(&s->version, sa_at_load32_acq(&s->version) | 1u); |
| 485 |
776 |
| sa_at_fence_rel(); |
| 486 |
|
| |
| 487 |
776 |
▶ | if (!found) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!found) { |
731 |
45 |
776 |
|
| 488 |
731 |
| uint32_t was = sa_at_load32_acq(&s->state); |
| 489 |
731 |
| memcpy(s->bytes, key, klen); |
| 490 |
731 |
| s->klen = klen; |
| 491 |
731 |
| sa_at_store64_rel(&s->tag, tag); |
| 492 |
731 |
▶ | if (was == SA_H_DEAD) sa_at_fetch_add64(&h->tombstones, (uint64_t)-1); |
Branch: 1 branch
| Branch | True | False | Total |
| if (was == SA_H_DEAD) sa_at_fetch_add64(&h->tombstones, (uint64_t)-1); |
4 |
727 |
731 |
|
| 493 |
731 |
| sa_at_fetch_add64(&h->used, 1); |
| 494 |
|
| } |
| 495 |
776 |
| memcpy(s->bytes + klen, val, vlen); |
| 496 |
776 |
| s->vlen = vlen; |
| 497 |
776 |
| sa_at_store64_rel(&s->expires, exp); |
| 498 |
|
| |
| 499 |
776 |
| sa_at_fence_rel(); |
| 500 |
776 |
| sa_at_store32_rel(&s->version, (sa_at_load32_acq(&s->version) + 1u) | 0u); |
| 501 |
776 |
| sa_at_store32_rel(&s->state, SA_H_LIVE); |
| 502 |
|
| |
| 503 |
776 |
| sa_at_unlock(h->locks, tag); |
| 504 |
776 |
| return rc; |
| 505 |
|
| #endif |
| 506 |
|
| } |
| 507 |
|
| |
| 508 |
161 |
| static int sa_hash_store(sa_hash *m, const char *key, uint32_t klen, |
| 509 |
|
| const char *val, uint32_t vlen) |
| 510 |
|
| { |
| 511 |
161 |
| return sa_hash_store_ttl(m, key, klen, val, vlen, 0); |
| 512 |
|
| } |
| 513 |
|
| |
| 514 |
7 |
| static int sa_hash_delete(sa_hash *m, const char *key, uint32_t klen) |
| 515 |
|
| { |
| 516 |
|
| #if !SA_HAVE_ATOMICS |
| 517 |
|
| (void)m; (void)key; (void)klen; |
| 518 |
|
| return 0; |
| 519 |
|
| #else |
| 520 |
7 |
| sa_hash_hdr *h = m->hdr; |
| 521 |
|
| uint64_t tag; |
| 522 |
|
| sa_hash_slot *s; |
| 523 |
7 |
| int found = 0; |
| 524 |
|
| |
| 525 |
7 |
▶ | if (!klen) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!klen) return 0; |
0 |
7 |
7 |
|
| 526 |
7 |
| tag = sa_at_fnv(key, klen); |
| 527 |
|
| /* NOT 0: that is what "the key was not there" answers, and a caller that |
| 528 |
|
| * deletes in order to rely on the key being gone - resetting a window |
| 529 |
|
| * counter before a fresh burst, say - would read a refusal as success and |
| 530 |
|
| * then count the old window's hits into the new one. */ |
| 531 |
7 |
▶ | if (!sa_hash_wait(h->locks, tag)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!sa_hash_wait(h->locks, tag)) { |
0 |
7 |
7 |
|
| 532 |
0 |
| sa_at_fetch_add64(&h->busy, 1); |
| 533 |
0 |
| return SA_H_WBUSY; |
| 534 |
|
| } |
| 535 |
|
| |
| 536 |
|
| /* now = 0: delete removes the entry whether current or expired, so it need |
| 537 |
|
| * not read the clock to classify it. */ |
| 538 |
7 |
| s = sa_hash_place(m, key, klen, tag, 0, &found); |
| 539 |
7 |
▶ | if (!s || !found) { sa_at_unlock(h->locks, tag); return 0; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!s || !found) { sa_at_unlock(h->locks, tag); return 0; } |
7 |
0 |
7 |
| if (!s || !found) { sa_at_unlock(h->locks, tag); return 0; } |
2 |
5 |
7 |
|
| 540 |
|
| |
| 541 |
|
| /* A TOMBSTONE, not an empty slot. An empty slot stops a probe, and a probe |
| 542 |
|
| * that stops early cannot find a key placed past this one. */ |
| 543 |
5 |
| sa_at_store32_rel(&s->state, SA_H_DEAD); |
| 544 |
5 |
| sa_at_store32_rel(&s->vlen, 0); |
| 545 |
5 |
| sa_at_fetch_add64(&h->used, (uint64_t)-1); |
| 546 |
5 |
| sa_at_fetch_add64(&h->tombstones, 1); |
| 547 |
|
| |
| 548 |
5 |
| sa_at_unlock(h->locks, tag); |
| 549 |
5 |
| return 1; |
| 550 |
|
| #endif |
| 551 |
|
| } |
| 552 |
|
| |
| 553 |
|
| /* Add to a counter, creating it at `by` when it is not there. |
| 554 |
|
| * |
| 555 |
|
| * A counter is an entry whose value is exactly eight bytes, and this is the one |
| 556 |
|
| * operation that does not go through the seqlock: the value IS a single aligned |
| 557 |
|
| * word, so the add is one atomic and a reader can never see it half-written. |
| 558 |
|
| * That is what makes a shared rate limiter or a request count cost the same as |
| 559 |
|
| * incrementing a variable. |
| 560 |
|
| * |
| 561 |
|
| * An entry that exists and is not eight bytes is left alone and refused, rather |
| 562 |
|
| * than reinterpreted: a caller that stored a string and then counted on it has |
| 563 |
|
| * a bug, and silently overwriting it would hide the bug and the string. */ |
| 564 |
|
| /* `ttl_ms` is set only when the increment CREATES the counter or RESETS an |
| 565 |
|
| * expired one: a live counter keeps the deadline it has, so a window does not |
| 566 |
|
| * slide. 0 means no deadline, which is what sa_hash_incr passes. |
| 567 |
|
| * |
| 568 |
|
| * `now_ms` is the caller's reading of the wall clock, or 0 to read it here. |
| 569 |
|
| * A caller that has just read the clock to compute the deadline it passes - |
| 570 |
|
| * a fixed-window rate limiter does exactly that - hands the reading in, so |
| 571 |
|
| * a hit on a counter with a deadline costs one clock read and not two. The |
| 572 |
|
| * clock is read at most once on this path, and only when a deadline is |
| 573 |
|
| * involved. */ |
| 574 |
1191 |
| static int sa_hash_incr_at(sa_hash *m, const char *key, uint32_t klen, |
| 575 |
|
| int64_t by, uint64_t ttl_ms, uint64_t now_ms, |
| 576 |
|
| uint64_t *now) |
| 577 |
|
| { |
| 578 |
|
| #if !SA_HAVE_ATOMICS |
| 579 |
|
| (void)m; (void)key; (void)klen; (void)by; (void)ttl_ms; (void)now_ms; |
| 580 |
|
| (void)now; |
| 581 |
|
| return SA_H_FULL; |
| 582 |
|
| #else |
| 583 |
1191 |
| sa_hash_hdr *h = m->hdr; |
| 584 |
|
| uint64_t tag; |
| 585 |
|
| sa_hash_slot *s; |
| 586 |
1191 |
| int found = 0; |
| 587 |
|
| |
| 588 |
1191 |
▶ | if (!klen) return SA_H_TOOBIG; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!klen) return SA_H_TOOBIG; |
0 |
1191 |
1191 |
|
| 589 |
1191 |
▶ | if ((uint64_t)klen + 8 > m->pair_max) return SA_H_TOOBIG; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((uint64_t)klen + 8 > m->pair_max) return SA_H_TOOBIG; |
0 |
1191 |
1191 |
|
| 590 |
|
| |
| 591 |
1191 |
| tag = sa_at_fnv(key, klen); |
| 592 |
1191 |
▶ | if (!sa_hash_wait(h->locks, tag)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!sa_hash_wait(h->locks, tag)) { |
0 |
1191 |
1191 |
|
| 593 |
0 |
| sa_at_fetch_add64(&h->busy, 1); |
| 594 |
0 |
| return SA_H_WBUSY; |
| 595 |
|
| } |
| 596 |
|
| |
| 597 |
|
| /* now = 0: find any live match, then check its own deadline below. Reading |
| 598 |
|
| * the clock only for a match that actually carries one keeps a counter |
| 599 |
|
| * with no TTL - the rate-limit hot path - free of a clock call. */ |
| 600 |
1191 |
| s = sa_hash_place(m, key, klen, tag, 0, &found); |
| 601 |
1191 |
▶ | if (!s) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!s) { |
0 |
1191 |
1191 |
|
| 602 |
0 |
| sa_at_unlock(h->locks, tag); |
| 603 |
0 |
| sa_at_fetch_add64(&h->full, 1); |
| 604 |
0 |
| return SA_H_FULL; |
| 605 |
|
| } |
| 606 |
|
| { |
| 607 |
|
| /* An EXPIRED counter is logically gone, so it is reset to zero rather |
| 608 |
|
| * than added to a stale value - the one thing a plain "found" flag |
| 609 |
|
| * would get wrong. A non-counter that has expired is likewise gone, so |
| 610 |
|
| * the deadline is checked before the not-a-counter refusal. */ |
| 611 |
1191 |
| int reset = 0; |
| 612 |
1191 |
▶ | if (found && sa_at_load64_acq(&s->expires)) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (found && sa_at_load64_acq(&s->expires)) { |
1046 |
145 |
1191 |
| if (found && sa_at_load64_acq(&s->expires)) { |
990 |
56 |
1046 |
|
| 613 |
990 |
▶ | if (!now_ms) now_ms = sa_now_ms(); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!now_ms) now_ms = sa_now_ms(); |
986 |
4 |
990 |
|
| 614 |
990 |
▶ | if (now_ms >= sa_at_load64_acq(&s->expires)) reset = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (now_ms >= sa_at_load64_acq(&s->expires)) reset = 1; |
129 |
861 |
990 |
|
| 615 |
|
| } |
| 616 |
|
| |
| 617 |
1191 |
▶ | if (found && !reset && sa_at_load32_acq(&s->vlen) != 8) { |
Branch: 3 branches
| Branch | True | False | Total |
| if (found && !reset && sa_at_load32_acq(&s->vlen) != 8) { |
1046 |
145 |
1191 |
| if (found && !reset && sa_at_load32_acq(&s->vlen) != 8) { |
917 |
129 |
1046 |
| if (found && !reset && sa_at_load32_acq(&s->vlen) != 8) { |
2 |
915 |
917 |
|
| 618 |
2 |
| sa_at_unlock(h->locks, tag); |
| 619 |
2 |
| return SA_H_NOTNUM; |
| 620 |
|
| } |
| 621 |
|
| |
| 622 |
1189 |
▶ | if (!found || reset) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (!found || reset) { |
1044 |
145 |
1189 |
| if (!found || reset) { |
129 |
915 |
1044 |
|
| 623 |
274 |
| uint32_t was = sa_at_load32_acq(&s->state); |
| 624 |
274 |
| uint64_t zero = 0; |
| 625 |
274 |
| sa_at_store32_rel(&s->version, sa_at_load32_acq(&s->version) | 1u); |
| 626 |
274 |
| sa_at_fence_rel(); |
| 627 |
274 |
| memcpy(s->bytes, key, klen); |
| 628 |
274 |
| s->klen = klen; |
| 629 |
274 |
| memcpy(s->bytes + klen, &zero, 8); |
| 630 |
274 |
| s->vlen = 8; |
| 631 |
274 |
| sa_at_store64_rel(&s->tag, tag); |
| 632 |
|
| /* A fresh counter's deadline, or none: a reset one starts its |
| 633 |
|
| * window now, never inherits the old deadline. */ |
| 634 |
274 |
▶ | if (ttl_ms && !now_ms) now_ms = sa_now_ms(); |
Branch: 2 branches
| Branch | True | False | Total |
| if (ttl_ms && !now_ms) now_ms = sa_now_ms(); |
183 |
91 |
274 |
| if (ttl_ms && !now_ms) now_ms = sa_now_ms(); |
95 |
88 |
183 |
|
| 635 |
274 |
▶ | sa_at_store64_rel(&s->expires, ttl_ms ? now_ms + ttl_ms : 0); |
Branch: 1 branch
| Branch | True | False | Total |
| sa_at_store64_rel(&s->expires, ttl_ms ? now_ms + ttl_ms : 0); |
183 |
91 |
274 |
|
| 636 |
274 |
| sa_at_fence_rel(); |
| 637 |
274 |
| sa_at_store32_rel(&s->version, sa_at_load32_acq(&s->version) + 1u); |
| 638 |
274 |
| sa_at_store32_rel(&s->state, SA_H_LIVE); |
| 639 |
274 |
▶ | if (was == SA_H_DEAD) sa_at_fetch_add64(&h->tombstones, (uint64_t)-1); |
Branch: 1 branch
| Branch | True | False | Total |
| if (was == SA_H_DEAD) sa_at_fetch_add64(&h->tombstones, (uint64_t)-1); |
5 |
269 |
274 |
|
| 640 |
|
| /* reset reuses a slot already counted in `used`; only a genuinely |
| 641 |
|
| * new key adds to it. */ |
| 642 |
274 |
▶ | if (!found) sa_at_fetch_add64(&h->used, 1); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!found) sa_at_fetch_add64(&h->used, 1); |
145 |
129 |
274 |
|
| 643 |
|
| } |
| 644 |
|
| } |
| 645 |
|
| |
| 646 |
|
| /* The counter itself, aligned inside the slot only if the key length says |
| 647 |
|
| * so - so it is read and written through a copy when it is not. The |
| 648 |
|
| * stripe lock is held, so no other writer can be here: a load and a |
| 649 |
|
| * release store of the aligned word, never a read-modify-write, which |
| 650 |
|
| * costs a locked instruction the lock has already paid for. A reader |
| 651 |
|
| * (`counter`, `fetch`) sees the old whole word or the new one, since an |
| 652 |
|
| * aligned 64-bit store cannot tear on any target with 64-bit atomics. */ |
| 653 |
|
| { |
| 654 |
1189 |
| char *p = s->bytes + s->klen; |
| 655 |
1189 |
▶ | if (((size_t)p & 7u) == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (((size_t)p & 7u) == 0) { |
3 |
1186 |
1189 |
|
| 656 |
3 |
| volatile uint64_t *w = (volatile uint64_t *)p; |
| 657 |
3 |
| uint64_t v = sa_at_load64_acq(w) + (uint64_t)by; |
| 658 |
3 |
| sa_at_store64_rel(w, v); |
| 659 |
3 |
▶ | if (now) *now = v; |
Branch: 1 branch
| Branch | True | False | Total |
| if (now) *now = v; |
3 |
0 |
3 |
|
| 660 |
|
| } |
| 661 |
|
| else { |
| 662 |
|
| uint64_t v; |
| 663 |
1186 |
| memcpy(&v, p, 8); |
| 664 |
1186 |
| v += (uint64_t)by; |
| 665 |
1186 |
| memcpy(p, &v, 8); |
| 666 |
1186 |
▶ | if (now) *now = v; |
Branch: 1 branch
| Branch | True | False | Total |
| if (now) *now = v; |
1186 |
0 |
1186 |
|
| 667 |
|
| } |
| 668 |
|
| } |
| 669 |
|
| |
| 670 |
1189 |
| sa_at_unlock(h->locks, tag); |
| 671 |
1189 |
| return SA_H_OK; |
| 672 |
|
| #endif |
| 673 |
|
| } |
| 674 |
|
| |
| 675 |
959 |
| static int sa_hash_incr_ttl(sa_hash *m, const char *key, uint32_t klen, |
| 676 |
|
| int64_t by, uint64_t ttl_ms, uint64_t *now) |
| 677 |
|
| { |
| 678 |
959 |
| return sa_hash_incr_at(m, key, klen, by, ttl_ms, 0, now); |
| 679 |
|
| } |
| 680 |
|
| |
| 681 |
225 |
| static int sa_hash_incr(sa_hash *m, const char *key, uint32_t klen, |
| 682 |
|
| int64_t by, uint64_t *now) |
| 683 |
|
| { |
| 684 |
225 |
| return sa_hash_incr_at(m, key, klen, by, 0, 0, now); |
| 685 |
|
| } |
| 686 |
|
| |
| 687 |
|
| #endif /* SA_HASH_H */ |