| 1 |
|
| #ifndef SA_FORMAT_H |
| 2 |
|
| #define SA_FORMAT_H |
| 3 |
|
| |
| 4 |
|
| /* sa_format.h - what a region looks like in memory. Perl-free. |
| 5 |
|
| * |
| 6 |
|
| * ---- NOTHING IN HERE IS EVER A POINTER -------------------------------------- |
| 7 |
|
| * |
| 8 |
|
| * Every reference from one part of a region to another is a BYTE OFFSET from |
| 9 |
|
| * the base of the mapping. That is the single rule this file exists to enforce, |
| 10 |
|
| * and it is what separates a region that can be attached from one that can only |
| 11 |
|
| * be inherited. |
| 12 |
|
| * |
| 13 |
|
| * The sibling design in Hyperman stores `hm_bus_group *groups` and `char *data` |
| 14 |
|
| * inside the shared mapping. That is correct for a fork child, which inherits |
| 15 |
|
| * the mapping at the same virtual address, and wrong for everything else - a |
| 16 |
|
| * process that maps the same segment at a different address reads those fields |
| 17 |
|
| * as addresses in ITS OWN space and follows them into whatever is there. It |
| 18 |
|
| * cannot be tested for either, because the one thing that reveals it is a |
| 19 |
|
| * second mapping at a second address, which that design cannot produce. |
| 20 |
|
| * |
| 21 |
|
| * Here it is testable, and t/03-relocatable.t is the test: map one named region |
| 22 |
|
| * twice IN ONE PROCESS, write through the first mapping, read through the |
| 23 |
|
| * second. No fork, no race, and any stray pointer fails it every time. |
| 24 |
|
| * |
| 25 |
|
| * ---- who may share a region ------------------------------------------------- |
| 26 |
|
| * |
| 27 |
|
| * Two processes sharing a named region must agree about its shape, and they are |
| 28 |
|
| * not necessarily the same build: a 32-bit perl and a 64-bit perl can open the |
| 29 |
|
| * same name. So the header carries its own dimensions - layout version, header |
| 30 |
|
| * size, pointer width and an endian probe - and a process whose compiled layout |
| 31 |
|
| * disagrees FAILS OPEN rather than dereferencing a shape it does not share. |
| 32 |
|
| * |
| 33 |
|
| * The endian probe cannot fire between two processes on one machine. It is |
| 34 |
|
| * there for the case where a region is ever persisted or forwarded, and it |
| 35 |
|
| * costs one comparison at attach. |
| 36 |
|
| */ |
| 37 |
|
| |
| 38 |
|
| #include "sa/sa_atomic.h" |
| 39 |
|
| #include "sa/sa_time.h" |
| 40 |
|
| |
| 41 |
|
| #include <string.h> |
| 42 |
|
| |
| 43 |
|
| /* "SARN" read as a native word. Not a byte-order-independent spelling, because |
| 44 |
|
| * the endian probe below is what answers that question. */ |
| 45 |
|
| #define SA_MAGIC 0x4E524153u /* 'S','A','R','N' little-endian */ |
| 46 |
|
| /* Bumped to 2 for 0.03: the map's slot layout changed (a per-key `expires` |
| 47 |
|
| * field), so a 0.02 and a 0.03 build sharing one NAMED arena would read each |
| 48 |
|
| * other's map slots at the wrong stride. The layout number is checked at attach |
| 49 |
|
| * exactly so that disagreement FAILS OPEN rather than silently misreading. |
| 50 |
|
| * |
| 51 |
|
| * Bumped to 3 for 0.08: the map and cache headers carry a `serialise` flag, |
| 52 |
|
| * which moves the map's lock stripes. A 0.07 build attaching a 0.08 arena would |
| 53 |
|
| * lock on the wrong bytes, so it is refused at the door instead. */ |
| 54 |
|
| #define SA_LAYOUT_VERSION 3 |
| 55 |
|
| #define SA_ENDIAN_PROBE 0x01020304u |
| 56 |
|
| |
| 57 |
|
| #define SA_ALIGN 16 /* every carved region starts here */ |
| 58 |
|
| #define SA_NAMELEN 32 /* including the NUL */ |
| 59 |
|
| #define SA_REGIONS_MAX 64 /* registry entries, sized at create */ |
| 60 |
|
| #define SA_PEERS_MAX 256 /* processes that may register */ |
| 61 |
|
| |
| 62 |
|
| /* what a registry entry is for, so a consumer can refuse a region that is not |
| 63 |
|
| * the kind it expected */ |
| 64 |
|
| #define SA_T_RAW 0u |
| 65 |
|
| #define SA_T_RING 1u |
| 66 |
|
| #define SA_T_MAP 2u |
| 67 |
|
| #define SA_T_BLOOM 3u |
| 68 |
|
| #define SA_T_HIST 4u |
| 69 |
|
| #define SA_T_CACHE 5u |
| 70 |
|
| #define SA_T_RATE 6u |
| 71 |
|
| #define SA_T_CMS 7u |
| 72 |
|
| #define SA_T_FROZEN 8u |
| 73 |
|
| #define SA_T_CUCKOO 9u |
| 74 |
|
| #define SA_T_LEASE 10u |
| 75 |
|
| #define SA_T_SCOREBOARD 11u |
| 76 |
|
| #define SA_T_HLL 12u |
| 77 |
|
| |
| 78 |
|
| /* registry entry states. `state` is published LAST with a release store, so a |
| 79 |
|
| * reader either sees a complete entry or no entry at all. */ |
| 80 |
|
| #define SA_R_EMPTY 0u |
| 81 |
|
| #define SA_R_LIVE 1u |
| 82 |
|
| |
| 83 |
|
| typedef struct { |
| 84 |
|
| volatile uint32_t state; /* SA_R_* - published last */ |
| 85 |
|
| uint32_t type; /* SA_T_* */ |
| 86 |
|
| uint64_t off; /* from the base of the mapping */ |
| 87 |
|
| uint64_t len; |
| 88 |
|
| char name[SA_NAMELEN]; |
| 89 |
|
| } sa_reg; |
| 90 |
|
| |
| 91 |
|
| /* ---- the peer table -------------------------------------------------------- |
| 92 |
|
| * |
| 93 |
|
| * Who is using this region, so that a hole left in a ring can be ATTRIBUTED |
| 94 |
|
| * rather than merely waited on. A timeout cannot tell a publisher that died |
| 95 |
|
| * from one that lost the CPU, and on a loaded machine a live publisher can be |
| 96 |
|
| * away for longer than any bound worth setting. |
| 97 |
|
| * |
| 98 |
|
| * `epoch` is what makes a peer slot an identity rather than an index. A slot |
| 99 |
|
| * reused by a later process gets a new epoch, so a claim naming (slot, epoch) |
| 100 |
|
| * is recognisably stale with no syscall at all - the same job the pid in a |
| 101 |
|
| * filename does for an orphaned log elsewhere in this workspace. |
| 102 |
|
| * |
| 103 |
|
| * `heartbeat` is the in-memory equivalent of that log's mtime. It is bumped on |
| 104 |
|
| * publishes AND on drains, so a peer that is merely idle still ticks, and it |
| 105 |
|
| * catches what a pid check cannot: a process that is alive but wedged passes |
| 106 |
|
| * kill(0) for ever and is never coming back. |
| 107 |
|
| * |
| 108 |
|
| * `want` is the residual-window mitigation. A publisher raises it before it |
| 109 |
|
| * reserves a sequence and lowers it after it commits, so a reader that finds a |
| 110 |
|
| * hole with no usable claim - because the publisher died in the few |
| 111 |
|
| * instructions between the two - can still ask whether any DEAD peer has an |
| 112 |
|
| * outstanding reservation. */ |
| 113 |
|
| #define SA_P_FREE 0u |
| 114 |
|
| #define SA_P_LIVE 1u |
| 115 |
|
| #define SA_P_REAPED 2u |
| 116 |
|
| |
| 117 |
|
| typedef struct { |
| 118 |
|
| volatile uint32_t state; /* SA_P_* */ |
| 119 |
|
| volatile uint32_t epoch; /* bumped every time this slot is taken */ |
| 120 |
|
| volatile uint64_t pid; |
| 121 |
|
| volatile uint64_t heartbeat; /* bumped on publish and on drain */ |
| 122 |
|
| volatile uint64_t want; /* reservations begun and not yet committed */ |
| 123 |
|
| } sa_peer; |
| 124 |
|
| |
| 125 |
|
| /* The region header. Its own size is recorded in it, so a build that grew the |
| 126 |
|
| * struct cannot silently read an older one's registry at the wrong offset. */ |
| 127 |
|
| typedef struct { |
| 128 |
|
| volatile uint32_t magic; /* SA_MAGIC - published LAST at create */ |
| 129 |
|
| uint16_t layout; /* SA_LAYOUT_VERSION */ |
| 130 |
|
| uint16_t hdr_size; /* sizeof(sa_header) */ |
| 131 |
|
| uint32_t endian; /* SA_ENDIAN_PROBE */ |
| 132 |
|
| uint32_t word; /* sizeof(void *) - 32- and 64-bit builds |
| 133 |
|
| * must not share a region */ |
| 134 |
|
| uint64_t total; /* the whole mapping, in bytes */ |
| 135 |
|
| |
| 136 |
|
| volatile uint64_t brk; /* bump high-water offset */ |
| 137 |
|
| uint64_t reg_off; /* offset of the sa_reg array */ |
| 138 |
|
| uint32_t reg_max; |
| 139 |
|
| volatile uint32_t reg_used; /* claimed entries, not necessarily live */ |
| 140 |
|
| volatile uint32_t reg_refused;/* entries whose extent is not in the |
| 141 |
|
| * mapping: corruption, or a writer who |
| 142 |
|
| * should not be there */ |
| 143 |
|
| |
| 144 |
|
| uint64_t peers_off; /* offset of the sa_peer array */ |
| 145 |
|
| uint32_t peers_max; |
| 146 |
|
| volatile uint32_t peers_used; /* high water, not a live count */ |
| 147 |
|
| |
| 148 |
|
| /* How long a reader waits for a hole before it starts asking whether the |
| 149 |
|
| * publisher is dead. A field rather than a constant so a test can shorten |
| 150 |
|
| * it; the default is set at create. */ |
| 151 |
|
| volatile uint32_t reap_grace_us; |
| 152 |
|
| |
| 153 |
|
| /* A test hook, and deliberately a FIELD rather than an #ifdef: a forked |
| 154 |
|
| * child has to honour it, and a child of a build that compiled it out |
| 155 |
|
| * cannot. Zero unless a test sets it. See t/10-crash.t - the window |
| 156 |
|
| * between reserving a record and committing it is a few instructions |
| 157 |
|
| * wide, and a crash-safety test that races it is a test that gets marked |
| 158 |
|
| * TODO and then stops meaning anything. */ |
| 159 |
|
| volatile uint32_t stall_us; |
| 160 |
|
| |
| 161 |
|
| volatile unsigned char locks[SA_LOCK_STRIPES]; |
| 162 |
|
| } sa_header; |
| 163 |
|
| |
| 164 |
|
| /* Round up to the carve alignment. */ |
| 165 |
47581 |
| static uint64_t sa_align_up(uint64_t n) { |
| 166 |
47581 |
| return (n + (SA_ALIGN - 1)) & ~(uint64_t)(SA_ALIGN - 1); |
| 167 |
|
| } |
| 168 |
|
| |
| 169 |
|
| /* Addressing. Every access into a region goes through these two, so there is |
| 170 |
|
| * one place where an offset becomes a pointer and it is never stored. */ |
| 171 |
|
| #define SA_AT(base, off) ((void *)((char *)(base) + (size_t)(off))) |
| 172 |
|
| #define SA_REGS(base, h) ((sa_reg *)SA_AT((base), (h)->reg_off)) |
| 173 |
|
| #define SA_PEERS(base, h) ((sa_peer *)SA_AT((base), (h)->peers_off)) |
| 174 |
|
| |
| 175 |
|
| /* How much mapping a header plus its registry needs, before any carving. */ |
| 176 |
469 |
| static uint64_t sa_header_bytes(uint32_t reg_max) { |
| 177 |
469 |
| return sa_align_up((uint64_t)sizeof(sa_header)) |
| 178 |
469 |
| + sa_align_up((uint64_t)reg_max * (uint64_t)sizeof(sa_reg)) |
| 179 |
469 |
| + sa_align_up((uint64_t)SA_PEERS_MAX * (uint64_t)sizeof(sa_peer)); |
| 180 |
|
| } |
| 181 |
|
| |
| 182 |
154 |
| static uint64_t sa_peers_offset(uint32_t reg_max) { |
| 183 |
154 |
| return sa_align_up((uint64_t)sizeof(sa_header)) |
| 184 |
154 |
| + sa_align_up((uint64_t)reg_max * (uint64_t)sizeof(sa_reg)); |
| 185 |
|
| } |
| 186 |
|
| |
| 187 |
|
| /* Is this mapping one of ours, and one this build can read? |
| 188 |
|
| * |
| 189 |
|
| * Returns an SA_E_* code. The caller fails open on anything but SA_E_OK: a |
| 190 |
|
| * region whose shape we do not share is not a region we may touch, and saying |
| 191 |
|
| * so costs four comparisons at attach and nothing afterwards. */ |
| 192 |
|
| #define SA_E_OK 0 |
| 193 |
|
| #define SA_E_MAGIC (-1) |
| 194 |
|
| #define SA_E_LAYOUT (-2) |
| 195 |
|
| #define SA_E_HDRSIZE (-3) |
| 196 |
|
| #define SA_E_ENDIAN (-4) |
| 197 |
|
| #define SA_E_WORD (-5) |
| 198 |
|
| #define SA_E_SHORT (-6) |
| 199 |
|
| #define SA_E_NOMEM (-7) |
| 200 |
|
| #define SA_E_MAP (-8) |
| 201 |
|
| #define SA_E_EXISTS (-9) |
| 202 |
|
| #define SA_E_NOENT (-10) |
| 203 |
|
| #define SA_E_NAME (-11) |
| 204 |
|
| #define SA_E_FULL (-12) |
| 205 |
|
| #define SA_E_NOATOMICS (-13) |
| 206 |
|
| #define SA_E_SHAPE (-14) |
| 207 |
|
| /* The stripe was held for the whole of a bounded wait. A TRANSIENT answer, and |
| 208 |
|
| * the reason it is not SA_E_FULL: "the arena is full" tells a caller to stop, |
| 209 |
|
| * and this one means try again. They were the same code until a loaded smoker |
| 210 |
|
| * reported two refused carves in an arena with room for four hundred more, and |
| 211 |
|
| * nothing in the answer said which of the two had happened. */ |
| 212 |
|
| #define SA_E_BUSY (-15) |
| 213 |
|
| |
| 214 |
|
| /* What a bind asks about a map's or a cache's values: 0 for opaque bytes, 1 for |
| 215 |
|
| * Struct::Codec's encoding, and SA_SER_ANY to take whatever the tenant already |
| 216 |
|
| * is (creating it as bytes). The answer lives in the SHARED tenant header, so a |
| 217 |
|
| * process asking for the other one is refused with SA_E_SHAPE: a cache one |
| 218 |
|
| * process treats as encoded and another as bytes is two caches that disagree |
| 219 |
|
| * about every value. */ |
| 220 |
|
| #define SA_SER_ANY (-1) |
| 221 |
|
| |
| 222 |
44 |
| static const char *sa_strerror(int rc) { |
| 223 |
44 |
| switch (rc) { |
| 224 |
0 |
| case SA_E_OK: return "no error"; |
| 225 |
1 |
| case SA_E_MAGIC: return "is not a Shared::Arena region"; |
| 226 |
0 |
| case SA_E_LAYOUT: return "was made by a build with a different layout version"; |
| 227 |
0 |
| case SA_E_HDRSIZE: return "was made by a build whose header is a different size"; |
| 228 |
0 |
| case SA_E_ENDIAN: return "was made on the other endianness"; |
| 229 |
0 |
| case SA_E_WORD: return "was made by a build with a different pointer width"; |
| 230 |
0 |
| case SA_E_SHORT: return "is shorter than a header"; |
| 231 |
0 |
| case SA_E_NOMEM: return "could not be allocated"; |
| 232 |
0 |
| case SA_E_MAP: return "could not be mapped"; |
| 233 |
0 |
| case SA_E_EXISTS: return "already exists"; |
| 234 |
1 |
| case SA_E_NOENT: return "does not exist"; |
| 235 |
0 |
| case SA_E_NAME: return "has a name that is too long or empty"; |
| 236 |
0 |
| case SA_E_FULL: return "has no room left"; |
| 237 |
0 |
| case SA_E_NOATOMICS:return "needs atomics this build does not have"; |
| 238 |
42 |
| case SA_E_SHAPE: return "is already carved with a different type or size"; |
| 239 |
0 |
| case SA_E_BUSY: return "was held by another process for the whole of a bounded wait"; |
| 240 |
0 |
| default: return "is not usable"; |
| 241 |
|
| } |
| 242 |
|
| } |
| 243 |
|
| |
| 244 |
159 |
| static int sa_check_header(const void *base, uint64_t len) { |
| 245 |
159 |
| const sa_header *h = (const sa_header *)base; |
| 246 |
159 |
▶ | if (len < (uint64_t)sizeof(sa_header)) return SA_E_SHORT; |
Branch: 1 branch
| Branch | True | False | Total |
| if (len < (uint64_t)sizeof(sa_header)) return SA_E_SHORT; |
0 |
159 |
159 |
|
| 247 |
|
| /* magic first: everything else is meaningless until it holds */ |
| 248 |
159 |
▶ | if (h->magic != SA_MAGIC) return SA_E_MAGIC; |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->magic != SA_MAGIC) return SA_E_MAGIC; |
0 |
159 |
159 |
|
| 249 |
159 |
▶ | if (h->layout != SA_LAYOUT_VERSION) return SA_E_LAYOUT; |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->layout != SA_LAYOUT_VERSION) return SA_E_LAYOUT; |
0 |
159 |
159 |
|
| 250 |
159 |
▶ | if (h->hdr_size != (uint16_t)sizeof(sa_header)) return SA_E_HDRSIZE; |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->hdr_size != (uint16_t)sizeof(sa_header)) return SA_E_HDRSIZE; |
0 |
159 |
159 |
|
| 251 |
159 |
▶ | if (h->endian != SA_ENDIAN_PROBE) return SA_E_ENDIAN; |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->endian != SA_ENDIAN_PROBE) return SA_E_ENDIAN; |
0 |
159 |
159 |
|
| 252 |
159 |
▶ | if (h->word != (uint32_t)sizeof(void *)) return SA_E_WORD; |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->word != (uint32_t)sizeof(void *)) return SA_E_WORD; |
0 |
159 |
159 |
|
| 253 |
159 |
▶ | if (h->total > len) return SA_E_SHORT; |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->total > len) return SA_E_SHORT; |
0 |
159 |
159 |
|
| 254 |
159 |
▶ | if (h->reg_off + (uint64_t)h->reg_max * sizeof(sa_reg) > h->total) |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->reg_off + (uint64_t)h->reg_max * sizeof(sa_reg) > h->total) |
0 |
159 |
159 |
|
| 255 |
0 |
| return SA_E_SHORT; |
| 256 |
159 |
▶ | if (h->peers_off + (uint64_t)h->peers_max * sizeof(sa_peer) > h->total) |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->peers_off + (uint64_t)h->peers_max * sizeof(sa_peer) > h->total) |
0 |
159 |
159 |
|
| 257 |
0 |
| return SA_E_SHORT; |
| 258 |
159 |
| return SA_E_OK; |
| 259 |
|
| } |
| 260 |
|
| |
| 261 |
|
| #endif /* SA_FORMAT_H */ |