| 1 | package engines |
| 2 | |
| 3 | import "sort" |
| 4 | |
| 5 | // The edge side of the internal mark (spec §5.1 "Setting the mark: the |
| 6 | // serving barrier", "What the edge does with it"; §5.9 box-wide fence; §6.3). |
| 7 | // |
| 8 | // The registry holds the mark (the intent); the edge serves the map its last |
| 9 | // successful reload swapped in, and publishes the registry change it has |
| 10 | // fenced. A launch trusts only the fence. |
| 11 | |
| 12 | // loadEdge swaps the registry into the edge's map: rows by value (a later |
| 13 | // registry edit does not leak into the served map) and their marks. |
| 14 | // |
| 15 | // The edge resolves owners at load (spec §5.1, "Platform-minted rows"): a |
| 16 | // row that follows an owner carries the resolved owner in its copy's Owner; |
| 17 | // one whose owner cannot be found, or is found ambiguously, is served NULL |
| 18 | // (refused) until the reconciler records its owner. Any other row's copy has |
| 19 | // no Owner, so edgeGroup is its own host. |
| 20 | func (b *box) loadEdge() { |
| 21 | b.EdgeRows = make(map[string]row, len(b.Rows)) |
| 22 | b.Serving = make(map[string]mark, len(b.Rows)) |
| 23 | for h, r := range b.Rows { |
| 24 | c := *r |
| 25 | c.PathTo = make(map[string]string, len(r.PathTo)) |
| 26 | for p, to := range r.PathTo { |
| 27 | c.PathTo[p] = to |
| 28 | } |
| 29 | b.Serving[h] = b.Mark[h] |
| 30 | c.Owner = "" |
| 31 | if followsOwner(r) { |
| 32 | if o, ok := b.resolveOwner(r); ok { |
| 33 | c.Owner = o |
| 34 | } else { |
| 35 | b.Serving[h] = markNull |
| 36 | } |
| 37 | } |
| 38 | b.EdgeRows[h] = c |
| 39 | } |
| 40 | } |
| 41 | |
| 42 | // groupHosts is every registry row of group g, sorted. |
| 43 | func (w *world) groupHosts(b *box, g string) []string { |
| 44 | var out []string |
| 45 | for h := range b.Rows { |
| 46 | if w.group(b, h) == g { |
| 47 | out = append(out, h) |
| 48 | } |
| 49 | } |
| 50 | sort.Strings(out) |
| 51 | return out |
| 52 | } |
| 53 | |
| 54 | // groupMark is the registry's mark of group g: internal only if every row of |
| 55 | // the group is, NULL if any row is NULL or the group has no row, else public. |
| 56 | func (w *world) groupMark(b *box, g string) mark { |
| 57 | hosts := w.groupHosts(b, g) |
| 58 | if len(hosts) == 0 { |
| 59 | return markNull |
| 60 | } |
| 61 | all := markInternal |
| 62 | for _, h := range hosts { |
| 63 | switch b.Mark[h] { |
| 64 | case markNull: |
| 65 | return markNull |
| 66 | case markPublic: |
| 67 | all = markPublic |
| 68 | } |
| 69 | } |
| 70 | return all |
| 71 | } |
| 72 | |
| 73 | // writeMark writes mark m on every registry row of group g: one registry |
| 74 | // change, so Wrote counts it. A change that closes a group the edge has not |
| 75 | // fenced closed (an open group, or a new row's NULL the edge has never |
| 76 | // loaded) is the one a fence must reach: it records the group's fence |
| 77 | // generation (SetAt). 1 written over a NULL whose generation is recorded |
| 78 | // moves nothing: the edge already refuses it. |
| 79 | func (w *world) writeMark(b *box, g string, m mark) { |
| 80 | wasClosed := w.closed(b, g) && (w.recorded(b, g) || !on("new-group-fenced")) |
| 81 | b.Wrote++ |
| 82 | for _, h := range w.groupHosts(b, g) { |
| 83 | b.Mark[h] = m |
| 84 | } |
| 85 | if !wasClosed && m != markPublic { |
| 86 | b.SetAt[g] = b.Wrote |
| 87 | } |
| 88 | w.logf("box%d: registry change %d: %s marked %v", b.ID, b.Wrote, g, m) |
| 89 | if m != markPublic { |
| 90 | w.dropListeners(b, g) // before any fence of this write (ports-excluded) |
| 91 | } |
| 92 | } |
| 93 | |
| 94 | // recorded: group g has a fence generation, the registry change at which it |
| 95 | // last closed (SetAt has the key). A group whose rows are new, or were |
| 96 | // created NULL and never written, has none. |
| 97 | func (w *world) recorded(b *box, g string) bool { |
| 98 | _, ok := b.SetAt[g] |
| 99 | return ok |
| 100 | } |
| 101 | |
| 102 | // fenced is the gate's reading of I1's "fenced": the group is closed, it has |
| 103 | // a fence generation, and the edge's fenced counter has reached it (no later |
| 104 | // change has cleared it). |
| 105 | // |
| 106 | // NULL counts as closed here only once the edge has loaded that NULL: the |
| 107 | // group has a recorded generation, set by the change that closed it, and the |
| 108 | // reload that reached it bumped the epoch and drained every older public |
| 109 | // request on the box (the upgrade's restart is such a fence). A newly created |
| 110 | // or unseen row is NULL in the registry but has no generation, so a first |
| 111 | // declaring launch writes 1 and waits for the fence like any other |
| 112 | // (new-group-fenced; final review, finding 1). |
| 113 | func (w *world) fenced(b *box, g string) bool { |
| 114 | return (w.recorded(b, g) || !on("new-group-fenced")) && w.closed(b, g) && b.Fenced >= b.SetAt[g] |
| 115 | } |
| 116 | |
| 117 | // fencedTruth is the oracle's fenced: fenced with every rule in place. I1 |
| 118 | // reads it, so a mutation that weakens the gate's reading cannot weaken the |
| 119 | // invariant too. |
| 120 | func (w *world) fencedTruth(b *box, g string) bool { |
| 121 | return w.recorded(b, g) && w.closed(b, g) && b.Fenced >= b.SetAt[g] |
| 122 | } |
| 123 | |
| 124 | // closed: group g has a row and none of its registry rows is 0. |
| 125 | func (w *world) closed(b *box, g string) bool { |
| 126 | hosts := w.groupHosts(b, g) |
| 127 | if len(hosts) == 0 { |
| 128 | return false |
| 129 | } |
| 130 | for _, h := range hosts { |
| 131 | if b.Mark[h] == markPublic { |
| 132 | return false |
| 133 | } |
| 134 | } |
| 135 | return true |
| 136 | } |
| 137 | |
| 138 | // reload is the edge's registry poll. A failed reload swaps nothing and |
| 139 | // advances nothing. A successful one swaps the map; if any row went from not |
| 140 | // internal to internal it bumps the box's admission epoch and cancels every |
| 141 | // public request admitted under an older one (including those waiting in the |
| 142 | // activator's queue); then the fenced counter reaches the registry. |
| 143 | func (w *world) reload(b *box) bool { |
| 144 | if b.ReloadFails { |
| 145 | if !on("fence-needs-reload") { |
| 146 | b.Fenced = b.Wrote |
| 147 | w.logf("box%d: reload failed; fenced %d anyway", b.ID, b.Fenced) |
| 148 | return false |
| 149 | } |
| 150 | w.logf("box%d: reload failed; nothing swapped, fenced stays %d", b.ID, b.Fenced) |
| 151 | return false |
| 152 | } |
| 153 | old := b.Serving |
| 154 | b.loadEdge() |
| 155 | changed := map[string]bool{} |
| 156 | for h, m := range b.Serving { |
| 157 | if (m == markInternal && old[h] != markInternal) || (m == markNull && old[h] == markPublic) { |
| 158 | changed[h] = true |
| 159 | } |
| 160 | } |
| 161 | if len(changed) > 0 { |
| 162 | b.Epoch++ |
| 163 | if on("fence-drains-admitted") { |
| 164 | kept := b.Admitted[:0] |
| 165 | for _, r := range b.Admitted { |
| 166 | // box-wide: every older public request on any row, deleted |
| 167 | // rows included (spec §5.9); without it, only the rows the |
| 168 | // change marked |
| 169 | if r.Public && r.Epoch < b.Epoch && (on("fence-box-wide") || changed[r.Row]) { |
| 170 | w.logf("box%d: fence cancels request %d (row %s, epoch %d)", b.ID, r.ID, r.Row, r.Epoch) |
| 171 | continue |
| 172 | } |
| 173 | kept = append(kept, r) |
| 174 | } |
| 175 | b.Admitted = kept |
| 176 | } |
| 177 | } |
| 178 | b.Fenced = b.Wrote |
| 179 | w.logf("box%d: reload: map swapped, epoch %d, fenced %d", b.ID, b.Epoch, b.Fenced) |
| 180 | return true |
| 181 | } |
| 182 | |
| 183 | // admitPublic is the edge's internal check for a request with no caller: it |
| 184 | // resolves the alias, the path map and the minted row to the final row, and |
| 185 | // refuses when that row is internal or NULL (spec §5.1: the check runs on the |
| 186 | // final resolved upstream's route). A static row answers without a proxy, so |
| 187 | // nothing is admitted. Otherwise the request is admitted under the box's |
| 188 | // epoch, holding the final row's backend. |
| 189 | func (w *world) admitPublic(b *box, host, path string) *req { |
| 190 | r, _ := w.admit(b, host, path) |
| 191 | return r |
| 192 | } |
| 193 | |
| 194 | // The outcomes of admit. |
| 195 | const ( |
| 196 | admitted = "admitted" // proxied: the request holds a backend |
| 197 | answered = "answered" // a static row: the edge answers it itself |
| 198 | refused = "refused" // the internal refusal |
| 199 | unknown = "unknown" // no such host, alias target or path target |
| 200 | ) |
| 201 | |
| 202 | // admit is admitPublic with its outcome, for INV-AV. The edge treats NULL |
| 203 | // like 1 (classify-null-refused). |
| 204 | func (w *world) admit(b *box, host, path string) (*req, string) { |
| 205 | asked, ok := b.EdgeRows[host] |
| 206 | if !ok { |
| 207 | w.logf("box%d: public %s%s: unknown host", b.ID, host, path) |
| 208 | return nil, unknown |
| 209 | } |
| 210 | final := asked |
| 211 | if asked.Alias != "" { |
| 212 | if final, ok = b.EdgeRows[asked.Alias]; !ok { |
| 213 | w.logf("box%d: public %s%s: alias target %s unknown", b.ID, host, path, asked.Alias) |
| 214 | return nil, unknown |
| 215 | } |
| 216 | } |
| 217 | if to, ok := final.PathTo[path]; ok { |
| 218 | if final, ok = b.EdgeRows[to]; !ok { |
| 219 | w.logf("box%d: public %s%s: path target %s unknown", b.ID, host, path, to) |
| 220 | return nil, unknown |
| 221 | } |
| 222 | } |
| 223 | checked := final |
| 224 | if !on("mark-on-final-upstream") { |
| 225 | checked = asked |
| 226 | } |
| 227 | m := b.Serving[checked.Host] |
| 228 | if m == markNull && !on("classify-null-refused") { |
| 229 | w.logf("box%d: public %s%s: %s is NULL, served like 0", b.ID, host, path, checked.Host) |
| 230 | m = markPublic |
| 231 | } |
| 232 | if m != markPublic { |
| 233 | w.logf("box%d: public %s%s: internal refusal (%s is %v)", b.ID, host, path, checked.Host, m) |
| 234 | return nil, refused |
| 235 | } |
| 236 | if final.Backend == "" { |
| 237 | w.logf("box%d: public %s%s: answered by the edge (%s)", b.ID, host, path, final.Host) |
| 238 | return nil, answered |
| 239 | } |
| 240 | if why := w.dedicatedRefusal(b, final); why != "" { |
| 241 | w.logf("box%d: public %s%s: internal refusal: %s", b.ID, host, path, why) |
| 242 | return nil, refused |
| 243 | } |
| 244 | w.nextID++ |
| 245 | r := &req{ID: w.nextID, Epoch: b.Epoch, Row: checked.Host, Backend: final.Backend, Public: true, Box: b.ID} |
| 246 | b.Admitted = append(b.Admitted, r) |
| 247 | w.logf("box%d: public %s%s admitted as request %d (row %s, backend %s, epoch %d)", b.ID, host, path, r.ID, r.Row, r.Backend, r.Epoch) |
| 248 | return r, admitted |
| 249 | } |
| 250 | |
| 251 | // backendGroup is the group whose process listens on backend: the group of |
| 252 | // the instance row that carries it, whatever row the request came in by. A |
| 253 | // minted row copies its source's backend; the process is the source's, so |
| 254 | // the source's own row decides (the truth, whatever the edge resolved). |
| 255 | func (w *world) backendGroup(b *box, backend string) string { |
| 256 | hosts := make([]string, 0, len(b.Rows)) |
| 257 | for h := range b.Rows { |
| 258 | hosts = append(hosts, h) |
| 259 | } |
| 260 | sort.Strings(hosts) |
| 261 | for _, h := range hosts { |
| 262 | if r := b.Rows[h]; r.Kind == "instance" && !r.Platform && r.Backend == backend { |
| 263 | return w.group(b, h) |
| 264 | } |
| 265 | } |
| 266 | return "" |
| 267 | } |
| 268 | |
| 269 | // deliver resumes an admitted request: unless the fence cancelled it, its |
| 270 | // proxy reaches the newest process of the group listening on its backend. |
| 271 | // INV-P: a public request never reaches a process whose build declares |
| 272 | // doc_engine, nor one of a group that holds the doc-engine grant once the |
| 273 | // edge has loaded the grant (the grant sets 1 whatever the manifest says, |
| 274 | // spec §5.1 "The column"; a grant whose barrier timed out protects nothing |
| 275 | // until the edge loads it, and the load drains every request admitted before). |
| 276 | func (w *world) deliver(r *req) { |
| 277 | b := w.boxes[r.Box] |
| 278 | idx := -1 |
| 279 | for i, x := range b.Admitted { |
| 280 | if x == r { |
| 281 | idx = i |
| 282 | } |
| 283 | } |
| 284 | if idx < 0 { |
| 285 | w.logf("box%d: request %d was cancelled; nothing delivered", b.ID, r.ID) |
| 286 | return |
| 287 | } |
| 288 | b.Admitted = append(b.Admitted[:idx], b.Admitted[idx+1:]...) |
| 289 | r.Held = false |
| 290 | g := w.backendGroup(b, r.Backend) |
| 291 | if g == "" && w.deliverDirect(b, r) { |
| 292 | return |
| 293 | } |
| 294 | var p *proc |
| 295 | for _, x := range b.Procs { |
| 296 | if x.Group == g && g != "" { |
| 297 | p = x |
| 298 | } |
| 299 | } |
| 300 | if p == nil { |
| 301 | w.logf("box%d: request %d: no process on %s; wake failure answer", b.ID, r.ID, r.Backend) |
| 302 | return |
| 303 | } |
| 304 | r.Reached = p.ID |
| 305 | w.events["delivered"]++ |
| 306 | w.logf("box%d: request %d delivered to process %d (%s v%d)", b.ID, r.ID, p.ID, p.Group, p.Ver) |
| 307 | if r.Public && w.builds[p.Ver].Declares { |
| 308 | w.failProc(b, p, "INV-P", true, "box%d: public request %d (row %s) delivered to process %d of %s running v%d, which declares doc_engine", b.ID, r.ID, r.Row, p.ID, p.Group, p.Ver) |
| 309 | } else if r.Public && w.grantLoaded(b, g) != "" { |
| 310 | w.failProc(b, p, "INV-P", true, "box%d: public request %d (row %s) delivered to process %d of %s running v%d, whose group holds the doc-engine grant (on %s)", b.ID, r.ID, r.Row, p.ID, p.Group, p.Ver, w.grantLoaded(b, g)) |
| 311 | } |
| 312 | if p.Ver == b.Live[g] { |
| 313 | b.Good[g] = p.Ver // the live build answered: it is the good version now |
| 314 | } |
| 315 | } |
| 316 | |
amadan