ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
MMappedCircuit.cpp
Go to the documentation of this file.
1/**
2 * @file MMappedCircuit.cpp
3 * @brief Persistent mmap-backed circuit: implementation and background-worker entry points.
4 *
5 * Implements the @c MMappedCircuit methods declared in @c MMappedCircuit.h,
6 * the @c createGenericCircuit() free function, and the background-worker
7 * entry points declared in @c provsql_mmap.h:
8 *
9 * - @c initialize_provsql_mmap(): called by the background worker at
10 * startup; the per-database @c MMappedCircuit instances themselves are
11 * opened lazily, on the first message for their database.
12 * - @c destroy_provsql_mmap(): called on shutdown; syncs and deletes the
13 * singleton.
14 * - @c provsql_mmap_main_loop(): the worker's main loop; receives gate-
15 * creation messages from backends over the IPC pipe and writes them
16 * to the mmap store.
17 *
18 * The @c createGenericCircuit() function performs a BFS from a root UUID,
19 * reading gates from the mmap store and building an in-memory @c GenericCircuit.
20 */
21#include <cerrno>
22#include <cmath>
23#include <map>
24#include <queue>
25#include <unordered_map>
26#include <unordered_set>
27#include <sstream>
28#include <string>
29
30#include "MMappedCircuit.h"
31#include "process_memory.h"
32#include "GenericCircuit.h"
33#include "Circuit.hpp"
34#include "provsql_utils_cpp.h"
35
36#include <poll.h>
37#ifdef __GLIBC__
38#include <malloc.h>
39#endif
40#ifndef PROVSQL_INPROCESS_STORE
41#include <boost/iostreams/device/back_inserter.hpp>
42#include <boost/iostreams/stream.hpp>
43#endif
44#include <fcntl.h>
45#include <unistd.h>
46#include <cstring>
47
48extern "C" {
49#include "miscadmin.h"
50#include "common/relpath.h"
51#include "utils/palloc.h"
52#include "provsql_mmap.h"
53
54/* Whether the message being applied comes from the replay spool, which only
55 the build with a separate worker has. */
56#ifdef PROVSQL_INPROCESS_STORE
57#define PROVSQL_FROM_SPOOL false
58#else
59#define PROVSQL_FROM_SPOOL provsql_worker_from_spool
60#endif
61#include "provsql_shmem.h"
62}
63
64/** @brief Per-database mmap-backed provenance circuits, keyed by database OID. */
65static std::map<Oid, MMappedCircuit*> circuits;
66
67/** @brief Whether any circuit has been written to since the last flush.
68 *
69 * The store's bytes reach the kernel as soon as a message is applied, but
70 * they reach the disk only when someone forces them; a machine that loses
71 * power in between loses whatever the kernel had not written back. The
72 * worker forces them a short while after the last write (see the main
73 * loop below), which bounds that loss the way
74 * @c synchronous_commit @c = @c off bounds the heap's. */
75static bool store_dirty = false;
76
77std::string MMappedCircuit::storePath(Oid db_oid, Oid db_tablespace,
78 const char *filename)
79{
80 /* GetDatabasePath yields the directory relative to the data directory:
81 "base/<oid>" for the default tablespace, and
82 "pg_tblspc/<ts>/PG_<ver>_<cat>/<oid>" for a database created in (or
83 moved to) another one. Resolving it here, rather than hardcoding
84 base/, is what makes the store follow CREATE DATABASE ... TABLESPACE
85 and ALTER DATABASE ... SET TABLESPACE. */
86 char *rel = GetDatabasePath(db_oid, db_tablespace);
87 std::string path = std::string(DataDir) + "/" + rel + "/" + filename;
88 pfree(rel);
89 return path;
90}
91
92MMappedCircuit::MMappedCircuit(Oid db_oid, Oid db_tablespace, bool read_only) :
94 storePath(db_oid, db_tablespace, MAPPING_FILENAME),
95 storePath(db_oid, db_tablespace, GATES_FILENAME),
96 storePath(db_oid, db_tablespace, WIRES_FILENAME),
97 storePath(db_oid, db_tablespace, EXTRA_FILENAME),
98 read_only) {}
99
100bool MMappedCircuit::storeExists(Oid db_oid, Oid db_tablespace)
101{
102 std::string gates = storePath(db_oid, db_tablespace, GATES_FILENAME);
103 return !(access(gates.c_str(), F_OK) != 0 && errno == ENOENT);
104}
105
107{
108 /* circuits are opened lazily on first IPC message */
109}
110
112{
113 for(auto &kv: circuits)
114 delete kv.second;
115 circuits.clear();
116}
117
118/** @brief Add a gate record and only then make it reachable under @p token.
119 *
120 * The record has to be complete before the mapping entry that points at
121 * it exists: killed between the two, the store keeps an unreferenced
122 * record, which costs nothing, whereas the other order leaves a mapping
123 * entry indexing past the end of the record vector and every gate
124 * created afterwards resolves one slot off, for the rest of the store's
125 * life. */
127 const std::vector<pg_uuid_t> &children)
128{
129 const unsigned long idx = gates.nbElements();
130 const unsigned long wires_idx = wires.nbElements();
131 for(const auto &c: children)
132 wires.add(c);
133 gates.add({type, static_cast<unsigned>(children.size()), wires_idx});
134 mapping.publish(token, idx);
135}
136
138 pg_uuid_t token, gate_type type, const std::vector<pg_uuid_t> &children)
139{
140 auto idx = mapping[token];
142 // The gate may have been lazy-added as a default gate_input below
143 // (when an earlier-arriving parent createGate referenced it as a
144 // child whose own createGate had not yet been received). Under
145 // concurrent backends, parent/child IPCs from different sessions
146 // can be interleaved such that the parent's lazy-add wins and the
147 // real create for the child is then silently dropped. Detect that
148 // case and upgrade the placeholder in place; otherwise leave the
149 // existing gate alone (real duplicate creation, idempotent).
150 bool placeholder = gates[idx].type == gate_input
151 && gates[idx].nb_children == 0;
152 bool real_create = type != gate_input || !children.empty();
153 if(placeholder && real_create) {
154 const unsigned long wires_idx = wires.nbElements();
155 for(const auto &c: children)
156 wires.add(c);
157 // Wires first, then the record's own fields: an upgrade seen
158 // half-done would otherwise claim children that are not there yet.
159 gates[idx].children_idx = wires_idx;
160 gates[idx].nb_children = static_cast<unsigned>(children.size());
161 gates[idx].type = type;
162 for(const auto &c: children)
164 appendGate(c, gate_input, {});
165 }
166 return;
167 }
168
169 appendGate(token, type, children);
170
171 for(const auto &c: children)
173 appendGate(c, gate_input, {});
174}
175
177{
178 auto idx = mapping[token];
180 return gate_input;
181 else
182 return gates[idx].type;
183}
184
185std::vector<pg_uuid_t> MMappedCircuit::getChildren(pg_uuid_t token) const
186{
187 std::vector<pg_uuid_t> result;
188 auto idx = mapping[token];
190 const GateInformation &gi = gates[idx];
191 for(unsigned long k=gi.children_idx; k<gi.children_idx+gi.nb_children; ++k)
192 result.push_back(wires[k]);
193 }
194 return result;
195}
196
197/** @brief Whether @p type is one of the gate kinds that carry a probability. */
198static bool carriesProb(gate_type type)
199{
200 return type == gate_input || type == gate_update || type == gate_mulinput;
201}
202
204 pg_uuid_t token, double prob, double *existing)
205{
206 auto idx = mapping[token];
208 idx = gates.nbElements();
209 appendGate(token, gate_input, {});
210 }
211
212 if(!carriesProb(gates[idx].type))
214
215 /* Clearing (the rollback path) always succeeds: it restores the gate
216 to the state it was in before the aborted transaction wrote to it. */
217 if(std::isnan(prob)) {
218 gates[idx].prob = NAN;
220 }
221
222 if(!hasProbAt(idx)) {
223 gates[idx].prob = prob;
225 }
226 if(gates[idx].prob == prob)
228 if(existing)
229 *existing = gates[idx].prob;
231}
232
233/** @brief Whether the record at @p idx holds a probability someone wrote.
234 *
235 * A version-1 @c gates file cannot distinguish "written as 1.0" from
236 * "never written" -- both are stored as @c 1.0 -- so on such a file a
237 * @c 1.0 counts as unset and stays writable. See @c GATES_VERSION. */
238bool MMappedCircuit::hasProbAt(unsigned long idx) const
239{
240 double p = gates[idx].prob;
241 if(std::isnan(p))
242 return false;
243 if(gates.version() < 2 && p == 1.)
244 return false;
245 return true;
246}
247
249{
250 return probAt(mapping[token]);
251}
252
253double MMappedCircuit::probAt(unsigned long idx) const
254{
255 if(idx == MMappedUUIDHashTable::NOTHING || !carriesProb(gates[idx].type))
256 return NAN;
257 if(!std::isnan(gates[idx].prob))
258 return gates[idx].prob;
259 /* A repaired row nobody gave a probability evaluates at the uniform
260 weight of its block, whose size repair_key recorded in info2. */
261 if(gates[idx].type == gate_mulinput && gates[idx].info2 > 0)
262 return 1. / gates[idx].info2;
263 /* Otherwise an unwritten probability evaluates as 1: a tuple nobody
264 gave a probability is certainly there. */
265 return 1.;
266}
267
268bool MMappedCircuit::hasProb(pg_uuid_t token, double *prob) const
269{
270 auto idx = mapping[token];
271 if(idx == MMappedUUIDHashTable::NOTHING || !carriesProb(gates[idx].type))
272 return false;
273 if(!hasProbAt(idx))
274 return false;
275 if(prob)
276 *prob = gates[idx].prob;
277 return true;
278}
279
280/* The two info fields are written once each, not once as a pair,
281 because they are written by different parties at different moments:
282 CertifiedDDMaterialize marks a gate certified (info1) as it builds it,
283 and tags it afterwards with the route that made it a query's root
284 (info2), which it only knows once the whole d-D is built. Zero is
285 "nothing recorded" for each field, so a field can go 0 -> v once and
286 a write of 0 over a v records nothing rather than clearing it. */
288 pg_uuid_t token, unsigned info1, unsigned info2,
289 std::pair<unsigned, unsigned> *existing)
290{
291 auto idx = mapping[token];
294
295 GateInformation &gi = gates[idx];
296
297 if((info1 != 0 && gi.info1 != 0 && gi.info1 != info1)
298 || (info2 != 0 && gi.info2 != 0 && gi.info2 != info2)) {
299 if(existing)
300 *existing = std::make_pair(gi.info1, gi.info2);
302 }
303
304 const unsigned w1 = info1 != 0 ? info1 : gi.info1;
305 const unsigned w2 = info2 != 0 ? info2 : gi.info2;
306 if(w1 == gi.info1 && w2 == gi.info2)
308
309 gi.info1 = w1;
310 gi.info2 = w2;
312}
313
315 pg_uuid_t token, const std::string &s, std::string *existing)
316{
317 auto idx = mapping[token];
320
321 /* Already carries exactly these bytes: nothing to do. Every caller
322 writes the extra string right after creating a content-addressed
323 gate, so recomputing the same expression offers the same bytes back;
324 appending them a second time would abandon the first copy in the
325 extra file for good, which is the store's main source of dead
326 space. */
327 if(gates[idx].extra_len == s.size()) {
328 bool same = true;
329 for(unsigned long k=0; k<s.size(); ++k)
330 if(extra[gates[idx].extra_idx + k] != s[k]) {
331 same = false;
332 break;
333 }
334 if(same)
336 }
337
338 if(gates[idx].extra_len > 0) {
339 if(existing)
340 *existing = getExtra(token);
342 }
343
344 gates[idx].extra_idx=extra.nbElements();
345 for(auto c: s)
346 extra.add(c);
347 gates[idx].extra_len=s.size();
349}
350
351std::pair<unsigned, unsigned> MMappedCircuit::getInfos(pg_uuid_t token) const
352{
353 auto idx = mapping[token];
355 return std::make_pair(0, 0);
356 } else {
357 const GateInformation &gi = gates[idx];
358 return std::make_pair(gi.info1, gi.info2);
359 }
360}
361
362std::string MMappedCircuit::getExtra(pg_uuid_t token) const
363{
364 return extraAt(mapping[token]);
365}
366
367std::string MMappedCircuit::extraAt(unsigned long idx) const
368{
369 std::string result;
370
372 for(unsigned long start=gates[idx].extra_idx, k=start, end=start+gates[idx].extra_len; k<end; ++k)
373 result+=extra[k];
374 }
375
376 return result;
377}
378
379/** @brief Suffix of the files a clean-up builds beside the live ones. */
380static constexpr const char *CLEANUP_SUFFIX = ".new";
381/** @brief Marker file present only while a clean-up's rename sequence is
382 * in flight; see @c finishInterruptedCleanup. */
383static constexpr const char *CLEANUP_MARKER = "provsql_cleanup.commit";
384
385/**
386 * @brief Bring a database's store to a definite state before opening it.
387 *
388 * A clean-up writes four new files, then renames them over the live ones
389 * one at a time. A crash inside that sequence would leave a mixture, so
390 * the sequence is bracketed by a marker file: present, it says the new
391 * files are complete and the renames must be finished; absent, it says
392 * any @c ".new" files are the debris of a clean-up that never got that
393 * far and are to be discarded.
394 */
395static void finishInterruptedCleanup(Oid db_oid, Oid db_tablespace)
396{
397 const char *names[4] = { "provsql_mapping.mmap", "provsql_gates.mmap",
398 "provsql_wires.mmap", "provsql_extra.mmap" };
399 std::string marker = MMappedCircuit::storePath(db_oid, db_tablespace,
401 const bool committed = (access(marker.c_str(), F_OK) == 0);
402
403 for(const char *name: names) {
404 std::string target = MMappedCircuit::storePath(db_oid, db_tablespace, name);
405 std::string fresh = target + CLEANUP_SUFFIX;
406 if(access(fresh.c_str(), F_OK) != 0)
407 continue;
408 if(committed)
409 rename(fresh.c_str(), target.c_str());
410 else
411 unlink(fresh.c_str());
412 }
413
414 if(committed)
415 unlink(marker.c_str());
416}
417
418/** @brief The tablespace of each open circuit, to find its files again. */
419static std::map<Oid, Oid> circuit_tablespaces;
420
421/**
422 * @brief Close the circuits of the databases dropped since they were opened.
423 *
424 * Dropping a database removes its directory, the circuit files with it, but
425 * not the worker's descriptors and mappings of them: kept, they would hold
426 * the disk space of every dropped database, and four descriptors each, until
427 * opening one more failed for lack of descriptors -- which a test run that
428 * creates and drops a database per test reached after a few hundred. A
429 * circuit whose gates file is gone belongs to a dropped database (one being
430 * cleaned up keeps it until the swap, and is not open meanwhile).
431 */
433{
434 for(auto it = circuits.begin(); it != circuits.end(); ) {
435 auto ts = circuit_tablespaces.find(it->first);
437 it->first,
438 ts == circuit_tablespaces.end() ? InvalidOid : ts->second)) {
439 delete it->second;
440 circuit_tablespaces.erase(it->first);
441 it = circuits.erase(it);
442 } else
443 ++it;
444 }
445}
446
447/** @brief Return (creating lazily if needed) the circuit for @p db_oid. */
448static MMappedCircuit *getCircuit(Oid db_oid, Oid db_tablespace)
449{
450 auto it = circuits.find(db_oid);
451 if(it == circuits.end()) {
452 /* Opening a database the worker has not seen yet is when the open
453 circuits grow: release those of the dropped databases first. */
455 finishInterruptedCleanup(db_oid, db_tablespace);
456 circuits[db_oid] = new MMappedCircuit(db_oid, db_tablespace);
457 circuit_tablespaces[db_oid] = db_tablespace;
458 return circuits[db_oid];
459 }
460 return it->second;
461}
462
463/**
464 * @brief Rebuild a database's store, keeping only what @p roots reach.
465 *
466 * The store only ever grows: a gate is never removed, because removing
467 * one is unsafe while anything might still reference it, and because a
468 * content-addressed gate can be re-adopted by a query at any moment.
469 * This is the one operation allowed to remove gates, and it is safe only
470 * because the caller holds the database exclusively -- no other session
471 * is connected, so nothing can adopt an orphan while the sweep runs.
472 *
473 * On @p dry_run the mark phase runs and the counts are reported, but
474 * nothing is written.
475 */
476static void cleanupStore(Oid db_oid, Oid db_tablespace,
477 const std::vector<pg_uuid_t> &roots, bool dry_run,
479{
480 MMappedCircuit *circuit = getCircuit(db_oid, db_tablespace);
481
482 auto before = circuit->counts();
483 out->gates_before = before.gates;
484 out->wires_before = before.wires;
485 out->extra_before = before.extra_bytes;
486
487 std::vector<bool> live;
488 unsigned long nb_live = circuit->mark(roots, live);
489
490 if(dry_run) {
491 /* Report what a real run would keep, without the wire and extra
492 counts of the rewrite -- those need the sweep to be exact. The
493 live gate count is what the operator is deciding on. */
494 out->gates_after = nb_live;
495 out->wires_after = 0;
496 out->extra_after = 0;
497 return;
498 }
499
500 const char *names[4] = { "provsql_mapping.mmap", "provsql_gates.mmap",
501 "provsql_wires.mmap", "provsql_extra.mmap" };
502 std::string target[4], fresh[4];
503 for(int i=0; i<4; ++i) {
504 target[i] = MMappedCircuit::storePath(db_oid, db_tablespace, names[i]);
505 fresh[i] = target[i] + CLEANUP_SUFFIX;
506 unlink(fresh[i].c_str());
507 }
508
509 auto after = circuit->sweepInto(live, fresh[0], fresh[1], fresh[2], fresh[3]);
510 out->gates_after = after.gates;
511 out->wires_after = after.wires;
512 out->extra_after = after.extra_bytes;
513
514 /* Close the live store before the swap, so its dirty bits are cleared
515 and the next message reopens the rebuilt files. */
516 delete circuit;
517 circuits.erase(db_oid);
518 circuit_tablespaces.erase(db_oid);
519
520 std::string marker = MMappedCircuit::storePath(db_oid, db_tablespace,
522 int mfd = open(marker.c_str(), O_CREAT | O_WRONLY | O_TRUNC, 0600); // flawfinder: ignore
523 if(mfd == -1) {
524 const char *reason = strerror(errno);
525 provsql_error("circuit_cleanup: cannot create %s: %s",
526 marker.c_str(), reason);
527 }
528 fsync(mfd);
529 close(mfd);
530
531 for(int i=0; i<4; ++i)
532 if(rename(fresh[i].c_str(), target[i].c_str())) {
533 const char *reason = strerror(errno);
534 provsql_error("circuit_cleanup: cannot replace %s: %s",
535 target[i].c_str(), reason);
536 }
537
538 unlink(marker.c_str());
539}
540
541#ifdef PROVSQL_INPROCESS_STORE
542/* Single-process build: the backend builds the in-memory circuit directly
543 from this process's store, instead of round-tripping a Boost-serialised
544 copy through the FIFO (which only existed to cross the worker/backend
545 process boundary). This is also what lets the WASM build avoid the
546 compiled libboost_serialization dependency. */
547GenericCircuit provsql_inproc_generic_circuit(pg_uuid_t token,
548 std::size_t budget)
549{
550 return getCircuit(MyDatabaseId, MyDatabaseTableSpace)->createGenericCircuit(token, budget);
551}
552
553GenericCircuit provsql_inproc_joint_circuit(
554 const std::vector<pg_uuid_t> &roots, std::size_t budget)
555{
556 return getCircuit(MyDatabaseId, MyDatabaseTableSpace)->createGenericCircuit(roots, budget);
557}
558
559FormulaRegions provsql_inproc_formula_regions(
560 const std::vector<FormulaRequest> &requests, unsigned long cap,
561 unsigned long wide_cap)
562{
563 return getCircuit(MyDatabaseId, MyDatabaseTableSpace)->formulaRegions(
564 requests, cap, wide_cap);
565}
566#endif
567
568extern "C" void provsql_store_flush(void)
569{
570 for(auto &kv: circuits)
571 kv.second->flush();
572 store_dirty = false;
573}
574
575#ifndef PROVSQL_INPROCESS_STORE
576/**
577 * @brief Answer a @c 'g' / @c 'j' request: the circuit reachable from
578 * @p roots, serialised, preceded by its size.
579 *
580 * The circuit is serialised straight into the buffer that is sent, without
581 * the copy a @c std::stringstream makes of its content, and is freed before
582 * it is sent. With a @p budget (bytes, 0 for none: what the requesting
583 * statement has left of @c provsql.max_memory), building and serialising it
584 * may not make this process grow by more; past it, the answer is
585 * @c PROVSQL_CIRCUIT_OVER_BUDGET and no circuit; if the requesting statement
586 * is cancelled meanwhile, it is @c PROVSQL_CIRCUIT_CANCELLED. The memory is
587 * given back afterwards, so that one large request does not stay resident
588 * in the worker.
589 */
590static void send_circuit(const MMappedCircuit *circuit,
591 const std::vector<pg_uuid_t> &roots,
592 unsigned long budget, char message_char)
593{
594 const std::size_t base_rss = budget ? provsql_process_rss(getpid()) : 0;
595 std::vector<char> buf;
596 unsigned long size;
597
598 try {
599 {
600 const GenericCircuit gc = circuit->createGenericCircuit(roots, budget);
601 /* Not serialised for a statement cancelled while it was built */
603 throw CircuitCancelled();
604 boost::iostreams::stream<
605 boost::iostreams::back_insert_device<std::vector<char>>> out(buf);
606 boost::archive::binary_oarchive oa(out);
607 oa << gc;
608 out.flush();
609 }
610 size = buf.size();
611 if(budget) {
612 std::size_t rss = provsql_process_rss(getpid());
613 if(rss > base_rss && rss - base_rss > budget)
615 }
616 } catch(const CircuitBudgetExceeded &) {
618 } catch(const CircuitCancelled &) {
620 }
621 const bool no_circuit = size == PROVSQL_CIRCUIT_OVER_BUDGET ||
623 if(no_circuit)
624 std::vector<char>().swap(buf);
625
626 if(!WRITEB(&size, unsigned long) ||
627 (!no_circuit && !WRITEB_BYTES(buf.data(), size)))
628 provsql_error("Cannot write to pipe (message type %c)", message_char);
629
630 std::vector<char>().swap(buf);
631#ifdef __GLIBC__
632 malloc_trim(0);
633#endif
634}
635#endif
636
637/** @brief The body of @c provsql_mmap_dispatch, which may throw. */
638static void dispatch(char c, Oid db_oid, Oid db_tablespace)
639{
640 MMappedCircuit *circuit = getCircuit(db_oid, db_tablespace);
641
642 if(c=='C' || c=='G' || c=='P' || c=='I' || c=='E')
643 store_dirty = true;
644
645 switch(c) {
646 case 'C':
647 {
648 pg_uuid_t token;
649 gate_type type;
650 unsigned nb_children;
651
652 if(!READM(token, pg_uuid_t) || !READM(type, gate_type) || !READM(nb_children, unsigned))
653 provsql_error("Cannot read from pipe (message type C)"); ;
654
655 std::vector<pg_uuid_t> children(nb_children);
656 for(unsigned i=0; i<nb_children; ++i)
657 if(!READM(children[i], pg_uuid_t))
658 provsql_error("Cannot read from pipe (message type C)");
659
660 circuit->createGate(token, type, children);
661 break;
662 }
663
664 case 'G':
665 {
666 /* A gate with what it records, in one message that is not answered:
667 the sender's address determines the infos and the text, so the
668 write-once rule cannot refuse them. If it does, someone wrote
669 something else at that address by hand (or hashes collided): the
670 first value stays, and the worker's log says so. */
671 pg_uuid_t token;
672 gate_type type;
673 unsigned nb_children, info1, info2, len;
674 char has_infos;
675
676 if(!READM(token, pg_uuid_t) || !READM(type, gate_type) || !READM(nb_children, unsigned))
677 provsql_error("Cannot read from pipe (message type G)");
678
679 std::vector<pg_uuid_t> children(nb_children);
680 for(unsigned i=0; i<nb_children; ++i)
681 if(!READM(children[i], pg_uuid_t))
682 provsql_error("Cannot read from pipe (message type G)");
683 if(!READM(has_infos, char) || !READM(info1, unsigned) || !READM(info2, unsigned)
684 || !READM(len, unsigned))
685 provsql_error("Cannot read from pipe (message type G)");
686 std::vector<char> data(len);
687 if(len > 0 && !READM_BYTES(data.data(), len))
688 provsql_error("Cannot read from pipe (message type G)");
689
690 circuit->createGate(token, type, children);
691 if(has_infos) {
692 std::pair<unsigned, unsigned> existing{0, 0};
693 if(circuit->setInfos(token, info1, info2, &existing)
695 provsql_warning("gate %s already records the annotation (%u, %u), not (%u, %u)",
696 uuid2string(token).c_str(), existing.first, existing.second,
697 info1, info2);
698 }
699 if(len > 0) {
700 std::string existing;
701 if(circuit->setExtra(token, std::string(data.data(), len), &existing)
703 provsql_warning("gate %s already records the annotation \"%s\", not \"%s\"",
704 uuid2string(token).c_str(), existing.c_str(),
705 std::string(data.data(), len).c_str());
706 }
707 break;
708 }
709
710 case 'P':
711 {
712 pg_uuid_t token;
713 double prob, existing = 0.;
714
715 if(!READM(token, pg_uuid_t) || !READM(prob, double))
716 provsql_error("Cannot read from pipe (message type P)");
717
718 auto result = circuit->setProb(token, prob, &existing);
719 char return_value = static_cast<char>(result);
720
721 /* A message of the replay spool has nobody waiting for its answer */
722 if(!PROVSQL_FROM_SPOOL &&
723 (!WRITEB(&return_value, char) || !WRITEB(&existing, double)))
724 provsql_error("Cannot write response to pipe (message type P)");
725 break;
726 }
727
728 case 'q':
729 {
730 /* Is a probability written on this gate, and which one? Distinct
731 from 'p', which reports the value an evaluation would use and so
732 cannot tell an unwritten probability from one written as 1. */
733 pg_uuid_t token;
734 double prob = 0.;
735
736 if(!READM(token, pg_uuid_t))
737 provsql_error("Cannot read from pipe (message type q)");
738
739 char has = circuit->hasProb(token, &prob) ? 1 : 0;
740
741 if(!WRITEB(&has, char) || !WRITEB(&prob, double))
742 provsql_error("Cannot write response to pipe (message type q)");
743 break;
744 }
745
746 case 'I':
747 case 'E':
748 {
749 /* Infos or text written after the gate. Nothing in this version
750 sends them (a gate is created with what it records, message G);
751 the install scripts of earlier versions, run by an upgrade, and
752 WAL records of earlier versions still do. Applied write-once
753 like G, and not answered. */
754 pg_uuid_t token;
755
756 if(!READM(token, pg_uuid_t))
757 provsql_error("Cannot read from pipe (message type %c)", c);
758 if(c == 'I') {
759 unsigned info1, info2;
760 std::pair<unsigned, unsigned> existing{0, 0};
761 if(!READM(info1, unsigned) || !READM(info2, unsigned))
762 provsql_error("Cannot read from pipe (message type I)");
763 if(circuit->setInfos(token, info1, info2, &existing)
765 provsql_warning("gate %s already records the annotation (%u, %u), not (%u, %u)",
766 uuid2string(token).c_str(), existing.first, existing.second,
767 info1, info2);
768 } else {
769 unsigned len;
770 if(!READM(len, unsigned))
771 provsql_error("Cannot read from pipe (message type E)");
772 if(len > 0) {
773 std::vector<char> data(len);
774 std::string existing;
775 if(!READM_BYTES(data.data(), len))
776 provsql_error("Cannot read from pipe (message type E)");
777 if(circuit->setExtra(token, std::string(data.data(), len), &existing)
779 provsql_warning("gate %s already records the annotation \"%s\", not \"%s\"",
780 uuid2string(token).c_str(), existing.c_str(),
781 std::string(data.data(), len).c_str());
782 }
783 }
784 break;
785 }
786
787 case 't':
788 {
789 pg_uuid_t token;
790
791 if(!READM(token, pg_uuid_t))
792 provsql_error("Cannot read from pipe (message type t)");
793
794 gate_type type = circuit->getGateType(token);
795
796 if(!WRITEB(&type, gate_type))
797 provsql_error("Cannot write response to pipe (message type t)");
798 break;
799 }
800
801 case 'n':
802 {
803 unsigned long nb = circuit->getNbGates();
804
805 if(!WRITEB(&nb, unsigned long))
806 provsql_error("Cannot write response to pipe (message type n)");
807 break;
808 }
809
810 case 'c':
811 {
812 pg_uuid_t token;
813
814 if(!READM(token, pg_uuid_t))
815 provsql_error("Cannot read from pipe (message type c)");
816
817 auto children = circuit->getChildren(token);
818 unsigned nb_children = children.size();
819 if(!WRITEB(&nb_children, unsigned))
820 provsql_error("Cannot write response to pipe (message type c)");
821
822 if(!WRITEB_BYTES(children.data(), nb_children*sizeof(pg_uuid_t)))
823 provsql_error("Cannot write response to pipe (message type c)");
824 break;
825 }
826
827 case 'p':
828 {
829 pg_uuid_t token;
830
831 if(!READM(token, pg_uuid_t))
832 provsql_error("Cannot read from pipe (message type p)");
833
834 double prob = circuit->getProb(token);
835
836 if(!WRITEB(&prob, double))
837 provsql_error("Cannot write response to pipe (message type p)");
838 break;
839 }
840
841 case 'i':
842 {
843 pg_uuid_t token;
844
845 if(!READM(token, pg_uuid_t))
846 provsql_error("Cannot read from pipe (message type i)");
847
848 auto infos = circuit->getInfos(token);
849
850 if(!WRITEB(&infos.first, unsigned) || !WRITEB(&infos.second, unsigned))
851 provsql_error("Cannot write response to pipe (message type i)");
852 break;
853 }
854
855 case 'e':
856 {
857 pg_uuid_t token;
858
859 if(!READM(token, pg_uuid_t))
860 provsql_error("Cannot read from pipe (message type e)");
861
862 auto str = circuit->getExtra(token);
863 unsigned len = str.size();
864
865 if(!WRITEB(&len, unsigned) || !WRITEB_BYTES(str.data(), len))
866 provsql_error("Cannot write response to pipe (message type e)");
867 break;
868 }
869
870 case 'g':
871 {
872 pg_uuid_t token;
873 unsigned long budget;
874
875 if(!READM(token, pg_uuid_t) || !READM(budget, unsigned long))
876 provsql_error("Cannot read from pipe (message type g)");
877
878#ifdef PROVSQL_INPROCESS_STORE
879 /* Unreachable: the backend calls provsql_inproc_generic_circuit
880 directly instead of issuing the 'g' message. */
881 provsql_error("message type g is not used by the in-process store");
882#else
883 send_circuit(circuit, std::vector<pg_uuid_t>{token}, budget, 'g');
884#endif
885 break;
886 }
887
888
889
890
891
892
893
894 case 'X':
895 {
896 /* Clean-up: rebuild the store keeping only what the roots reach.
897 The caller holds the database exclusively (see
898 provsql.circuit_cleanup), so nothing can adopt an orphan while
899 this runs. */
900 char dry_run;
901 unsigned long nb_roots;
902
903 if(!READM(dry_run, char) || !READM(nb_roots, unsigned long))
904 provsql_error("Cannot read from pipe (message type X)");
905
906 std::vector<pg_uuid_t> roots(nb_roots);
907 for(unsigned long i=0; i<nb_roots; ++i)
908 if(!READM(roots[i], pg_uuid_t))
909 provsql_error("Cannot read from pipe (message type X)");
910
912 cleanupStore(db_oid, db_tablespace, roots, dry_run != 0, &res);
913
914 if(!WRITEB(&res.gates_before, uint64) || !WRITEB(&res.gates_after, uint64)
915 || !WRITEB(&res.wires_before, uint64) || !WRITEB(&res.wires_after, uint64)
916 || !WRITEB(&res.extra_before, uint64) || !WRITEB(&res.extra_after, uint64))
917 provsql_error("Cannot write response to pipe (message type X)");
918 break;
919 }
920
921 case 'S':
922 {
923 /* Sync barrier: force everything written so far to stable storage
924 and say so. Because the pipe is FIFO and the worker single
925 threaded, the reply also proves every earlier message from this
926 backend has been *applied*, not merely queued. */
928
929 char ack = 1;
930 if(!WRITEB(&ack, char))
931 provsql_error("Cannot write response to pipe (message type S)");
932 break;
933 }
934
935 case 'k':
936 {
937 /* Consistency report; see MMappedCircuit::Check. */
938 MMappedCircuit::Check chk = circuit->check();
939 char unclean = chk.unclean ? 1 : 0;
940 if(!WRITEB(&unclean, char)
941 || !WRITEB(&chk.nb_gates, unsigned long)
942 || !WRITEB(&chk.nb_mapping, unsigned long)
943 || !WRITEB(&chk.next_value, unsigned long)
944 || !WRITEB(&chk.dangling_indices, unsigned long)
945 || !WRITEB(&chk.unreferenced, unsigned long)
946 || !WRITEB(&chk.bad_wires, unsigned long)
947 || !WRITEB(&chk.bad_extra, unsigned long))
948 provsql_error("Cannot write response to pipe (message type k)");
949 break;
950 }
951
952 case 'j':
953 {
954 /* Joint-circuit load: BFS from a vector of roots so a shared
955 * subgraph reachable from multiple roots collapses to a single
956 * gate_t. Used by getJointCircuit() to load an RV's sub-DAG
957 * together with a conditioning gate that sits above it in the
958 * persisted DAG. */
959 unsigned nb_roots;
960 if(!READM(nb_roots, unsigned))
961 provsql_error("Cannot read from pipe (message type j)");
962
963 std::vector<pg_uuid_t> roots(nb_roots);
964 for(unsigned i=0; i<nb_roots; ++i)
965 if(!READM(roots[i], pg_uuid_t))
966 provsql_error("Cannot read from pipe (message type j)");
967 unsigned long budget;
968 if(!READM(budget, unsigned long))
969 provsql_error("Cannot read from pipe (message type j)");
970
971#ifdef PROVSQL_INPROCESS_STORE
972 /* Unreachable: the backend calls provsql_inproc_joint_circuit
973 directly instead of issuing the 'j' message. */
974 provsql_error("message type j is not used by the in-process store");
975#else
976 send_circuit(circuit, roots, budget, 'j');
977#endif
978 break;
979 }
980
981 case 'F':
982 {
983 /* The regions of a few rows of sr_formula_rows */
984 unsigned long cap, wide_cap;
985 unsigned nb;
986 if(!READM(cap, unsigned long) || !READM(wide_cap, unsigned long)
987 || !READM(nb, unsigned))
988 provsql_error("Cannot read from pipe (message type F)");
989 std::vector<FormulaRequest> requests(nb);
990 for(unsigned i = 0; i < nb; ++i)
991 if(!READM(requests[i].gate, pg_uuid_t)
992 || !READM(requests[i].from, unsigned long)
993 || !READM(requests[i].count, unsigned long))
994 provsql_error("Cannot read from pipe (message type F)");
995
996#ifdef PROVSQL_INPROCESS_STORE
997 provsql_error("message type F is not used by the in-process store");
998#else
999 std::vector<char> buf;
1000 {
1001 boost::iostreams::stream<
1002 boost::iostreams::back_insert_device<std::vector<char>>> out(buf);
1003 boost::archive::binary_oarchive oa(out);
1004 const FormulaRegions regions =
1005 circuit->formulaRegions(requests, cap, wide_cap);
1006 oa << regions;
1007 out.flush();
1008 }
1009 unsigned long size = buf.size();
1010 if(!WRITEB(&size, unsigned long) || !WRITEB_BYTES(buf.data(), size))
1011 provsql_error("Cannot write to pipe (message type F)");
1012#endif
1013 break;
1014 }
1015
1016 default:
1017 provsql_error("Wrong message type: %c", c);
1018 }
1019}
1020
1021/**
1022 * @brief Serve one message of the store's protocol.
1023 *
1024 * A C++ exception escaping here -- a file that cannot be opened or mapped,
1025 * an allocation that fails -- would reach the C frames of the worker and
1026 * terminate it with an abort, which the postmaster answers by resetting
1027 * every backend of the cluster. It is reported as the error it is instead,
1028 * as the worker's other failures are: the worker exits and is restarted,
1029 * and the other databases keep their sessions.
1030 */
1031extern "C" void provsql_mmap_dispatch(char c, Oid db_oid, Oid db_tablespace)
1032{
1033 std::string what;
1034 try {
1035 dispatch(c, db_oid, db_tablespace);
1036 return;
1037 } catch(const std::exception &e) {
1038 what = e.what();
1039 } catch(...) {
1040 what = "unknown exception";
1041 }
1042 /* Outside the handler: the error does not return. */
1043 provsql_error("ProvSQL circuit store: %s", what.c_str());
1044}
1045
1046#ifndef PROVSQL_INPROCESS_STORE
1048{
1049 char c;
1050
1051 for(;;) {
1052 struct pollfd pfd;
1053 pfd.fd = provsql_shared_state->pipebmr;
1054 pfd.events = POLLIN;
1055 pfd.revents = 0;
1056
1057 /* Wait indefinitely while there is nothing to force out; once a write
1058 has landed, wake up after the flush interval and force it, so an
1059 idle store is never more than that far behind the disk. Bytes
1060 already read into the buffer are served first: poll() does not see
1061 them. */
1063 int r = poll(&pfd, 1,
1065 if(r < 0) {
1066 if(errno == EINTR)
1067 continue;
1068 break;
1069 }
1070 if(r == 0) {
1072 continue;
1073 }
1074 }
1075
1077 if(!READM(c, char))
1078 break;
1079 Oid db_oid, db_tablespace;
1080 if(!READM(db_oid, Oid) || !READM(db_tablespace, Oid))
1081 provsql_error("Cannot read message header from pipe");
1082 provsql_mmap_dispatch(c, db_oid, db_tablespace);
1083 }
1084
1085 int e = errno;
1086 provsql_error("Reading from pipe: %s", strerror(e));
1087}
1088#endif
1089
1091{
1092 gates.sync();
1093 wires.sync();
1094 mapping.sync();
1095 extra.sync();
1096}
1097
1099{
1100 /* Order matters as much here as it does on the write path: the records
1101 a mapping entry points at must be on disk before the entry is, so
1102 that a machine crash between the two flushes leaves an unreferenced
1103 record rather than a dangling index. */
1104 wires.flush();
1105 extra.flush();
1106 gates.flush();
1107 mapping.flush();
1108}
1109
1111{
1112 return mapping.uncleanShutdown() || gates.uncleanShutdown()
1113 || wires.uncleanShutdown() || extra.uncleanShutdown();
1114}
1115
1117{
1118 Check c{};
1120 c.nb_gates = gates.nbElements();
1121 c.nb_mapping = mapping.nbElements();
1122 c.next_value = mapping.nextValue();
1123
1124 std::vector<bool> referenced(c.nb_gates, false);
1125 for(unsigned long k=0; k<mapping.capacity(); ++k) {
1126 unsigned long v = mapping.slotValue(k);
1128 continue;
1129 if(v >= c.nb_gates)
1130 ++c.dangling_indices;
1131 else
1132 referenced[v] = true;
1133 }
1134 for(unsigned long i=0; i<c.nb_gates; ++i) {
1135 if(!referenced[i])
1136 ++c.unreferenced;
1137 const GateInformation &gi = gates[i];
1138 if(gi.children_idx + gi.nb_children > wires.nbElements())
1139 ++c.bad_wires;
1140 if(gi.extra_idx + gi.extra_len > extra.nbElements())
1141 ++c.bad_extra;
1142 }
1143 return c;
1144}
1145
1146
1147unsigned long MMappedCircuit::mark(const std::vector<pg_uuid_t> &roots,
1148 std::vector<bool> &live) const
1149{
1150 const unsigned long n = gates.nbElements();
1151 live.assign(n, false);
1152 unsigned long nb_live = 0;
1153
1154 std::vector<unsigned long> stack;
1155 for(const auto &r: roots) {
1156 auto idx = mapping[r];
1157 if(idx != MMappedUUIDHashTable::NOTHING && idx < n && !live[idx]) {
1158 live[idx] = true;
1159 ++nb_live;
1160 stack.push_back(idx);
1161 }
1162 }
1163
1164 while(!stack.empty()) {
1165 unsigned long idx = stack.back();
1166 stack.pop_back();
1167 const GateInformation &gi = gates[idx];
1168 if(gi.children_idx + gi.nb_children > wires.nbElements())
1169 continue; /* a torn record; check() reports it, do not follow it */
1170 for(unsigned long k=gi.children_idx; k<gi.children_idx+gi.nb_children; ++k) {
1171 auto child = mapping[wires[k]];
1172 if(child != MMappedUUIDHashTable::NOTHING && child < n && !live[child]) {
1173 live[child] = true;
1174 ++nb_live;
1175 stack.push_back(child);
1176 }
1177 }
1178 }
1179
1180 return nb_live;
1181}
1182
1184 const std::vector<bool> &live,
1185 const std::string &mp, const std::string &gp,
1186 const std::string &wp, const std::string &ep) const
1187{
1188 Counts out{};
1189 const unsigned long n = gates.nbElements();
1190
1191 /* Old index -> new index, assigned in old order so the rewritten store
1192 keeps the creation order of what it keeps. */
1193 std::vector<unsigned long> newidx(n, MMappedUUIDHashTable::NOTHING);
1194 {
1195 unsigned long next = 0;
1196 for(unsigned long i=0; i<n; ++i)
1197 if(live[i])
1198 newidx[i] = next++;
1199 }
1200
1201 const bool legacy = legacyProbabilities();
1202
1203 {
1204 MMappedUUIDHashTable nmapping(mp.c_str(), false, MAGIC_MAPPING);
1205 MMappedVector<GateInformation> ngates(gp.c_str(), false, MAGIC_GATES,
1207 MMappedVector<pg_uuid_t> nwires(wp.c_str(), false, MAGIC_WIRES);
1208 MMappedVector<char> nextra(ep.c_str(), false, MAGIC_EXTRA);
1209
1210 for(unsigned long i=0; i<n; ++i) {
1211 if(!live[i])
1212 continue;
1213 GateInformation gi = gates[i];
1214
1215 /* A record whose ranges run past the vectors they index is torn --
1216 check() counts them -- so copying by those ranges would read off
1217 the end. Keep the gate, drop what cannot be read: the rebuilt
1218 store is then at least internally consistent, which is the point
1219 of running the clean-up on a damaged store. */
1220 const unsigned long old_children = gi.children_idx;
1221 gi.children_idx = nwires.nbElements();
1222 if(old_children + gi.nb_children > wires.nbElements())
1223 gi.nb_children = 0;
1224 for(unsigned c=0; c<gi.nb_children; ++c)
1225 nwires.add(wires[old_children + c]);
1226
1227 const unsigned long old_extra = gi.extra_idx;
1228 if(old_extra + gi.extra_len > extra.nbElements())
1229 gi.extra_len = 0;
1230 if(gi.extra_len > 0) {
1231 gi.extra_idx = nextra.nbElements();
1232 for(unsigned k=0; k<gi.extra_len; ++k)
1233 nextra.add(extra[old_extra + k]);
1234 } else {
1235 gi.extra_idx = 0;
1236 }
1237
1238 /* A version-1 file stored 1.0 both for "written as certain" and for
1239 "never written"; the rewrite is where that ambiguity is settled,
1240 conservatively, in favour of unwritten -- the reading the store
1241 has been giving those gates all along. */
1242 if(legacy && gi.prob == 1.
1243 && (gi.type == gate_input || gi.type == gate_update
1244 || gi.type == gate_mulinput))
1245 gi.prob = NAN;
1246
1247 ngates.add(gi);
1248 }
1249
1250 for(unsigned long k=0; k<mapping.capacity(); ++k) {
1251 unsigned long v = mapping.slotValue(k);
1252 if(v == MMappedUUIDHashTable::NOTHING || v >= n || !live[v])
1253 continue;
1254 nmapping.publish(mapping.slotKey(k), newidx[v]);
1255 }
1256
1257 out.gates = ngates.nbElements();
1258 out.wires = nwires.nbElements();
1259 out.extra_bytes = nextra.nbElements();
1260
1261 ngates.flush();
1262 nwires.flush();
1263 nextra.flush();
1264 nmapping.flush();
1265 }
1266
1267 return out;
1268}
1269
1270/**
1271 * @brief Lexicographic less-than comparison for @c pg_uuid_t.
1272 * @param a Left UUID.
1273 * @param b Right UUID.
1274 * @return @c true if @p a is lexicographically less than @p b.
1275 */
1276bool operator<(const pg_uuid_t a, const pg_uuid_t b)
1277{
1278 return memcmp(&a, &b, sizeof(pg_uuid_t))<0;
1279}
1280
1282 std::size_t budget) const
1283{
1284 return createGenericCircuit(std::vector<pg_uuid_t>{token}, budget);
1285}
1286
1288 const std::vector<pg_uuid_t> &roots, std::size_t budget) const
1289{
1290 /* The resident memory the building may add, read every few thousand
1291 * gates: a circuit of millions of gates is otherwise built, and shipped,
1292 * whole before anything checks it (GitHub #104). */
1293 const std::size_t base_rss = budget ? provsql_process_rss(getpid()) : 0;
1294 unsigned steps = 0;
1295 /* Counted per gate and per wire: a single gate (the agg of a SUM over
1296 * millions of rows) can have millions of children. A cancel of the
1297 * statement that asked for the circuit is looked for at the same pace. */
1298 auto check_budget = [&]() {
1299 if(++steps % 4096 == 0) {
1301 throw CircuitCancelled();
1302 if(budget) {
1303 std::size_t rss = provsql_process_rss(getpid());
1304 if(rss > base_rss && rss - base_rss > budget)
1305 throw CircuitBudgetExceeded();
1306 }
1307 }
1308 };
1309
1310 /* Seed the work list with every root. A UUID listed twice (or reached
1311 * as a child of one root and the other's root itself) is processed only
1312 * once. Shared subgraphs therefore land on a single gate_t in `result`
1313 * -- the property that lets the conditional MC sampler couple the
1314 * indicator and value paths through @c Sampler::scalar_cache_ /
1315 * @c bool_cache_. The smallest UUID waiting is processed first, which
1316 * fixes the numbering of the gates (a gate is numbered when first met):
1317 * a min-heap, which a gate enters when first met as a child; a root met
1318 * so before it is processed is in it twice, and skipped the second
1319 * time. */
1320 auto greater = [](const gate_uuid &a, const gate_uuid &b) {
1321 return b < a;
1322 };
1323 std::priority_queue<gate_uuid, std::vector<gate_uuid>, decltype(greater)>
1324 to_process(greater);
1325 for(const auto &r : roots)
1326 to_process.push(gate_uuid::fromBytes(r.data));
1327
1328 GenericCircuit result;
1329 std::vector<bool> processed;
1330
1331 while(!to_process.empty()) {
1332 check_budget();
1333 const gate_uuid key = to_process.top();
1334 to_process.pop();
1335 pg_uuid_t uuid;
1336 key.toBytes(uuid.data);
1337 const gate_t id = result.getGate(key);
1338 const std::size_t i = static_cast<std::size_t>(id);
1339 if(i < processed.size() && processed[i])
1340 continue;
1341 if(i >= processed.size())
1342 processed.resize(std::max<std::size_t>(i + 1, 2 * processed.size()));
1343 processed[i] = true;
1344
1345 const unsigned long idx = mapping[uuid];
1346 copyGateAt(result, id, idx);
1348 continue;
1349
1350 const GateInformation &gi = gates[idx];
1351 for(unsigned long k = gi.children_idx; k < gi.children_idx + gi.nb_children;
1352 ++k) {
1353 check_budget();
1354 const gate_uuid child = gate_uuid::fromBytes(wires[k].data);
1355 auto [c, first] = result.findOrAddGate(child);
1356 if(first)
1357 to_process.push(child);
1358 result.addWire(id, c);
1359 }
1360 }
1361
1362 return result;
1363}
1364
1366{
1367 const gate_t id = result.getGate(gate_uuid::fromBytes(uuid.data));
1368 copyGateAt(result, id, mapping[uuid]);
1369 return id;
1370}
1371
1373 unsigned long idx) const
1374{
1375 const bool absent = idx == MMappedUUIDHashTable::NOTHING;
1376 gate_type type = absent ? gate_input : gates[idx].type;
1377 result.setGate(id, type);
1378 double prob = probAt(idx);
1379 if(!std::isnan(prob))
1380 result.setProb(id, prob);
1381
1382 if(type==gate_mulinput || type==gate_eq || type==gate_agg
1383 || type==gate_cmp || type==gate_arith || type==gate_fixpoint) {
1384 const unsigned info1 = absent ? 0 : gates[idx].info1;
1385 const unsigned info2 = absent ? 0 : gates[idx].info2;
1386 result.setInfos(id, info1, info2);
1387 } else if(type==gate_plus || type==gate_times || type==gate_assumed) {
1388 /* The d-DNNF certificate (DNNF_CERT_INFO in info1: deterministic
1389 * plus / decomposable times) and, alongside it in info2, the tag of
1390 * the planner-time route that produced the root (@c provsql_route);
1391 * on a gate_assumed the route tag is in info1. Copied only when
1392 * set, so unmarked gates do not bloat the in-memory infos map with
1393 * zeros. */
1394 const unsigned info1 = absent ? 0 : gates[idx].info1;
1395 const unsigned info2 = absent ? 0 : gates[idx].info2;
1396 if(info1 != 0 || info2 != 0)
1397 result.setInfos(id, info1, info2);
1398 }
1399
1400 if(type==gate_project || type==gate_value || type==gate_agg
1401 || type==gate_rv || type==gate_mulinput || type==gate_annotation
1402 || type==gate_assumed || type==gate_mobius || type==gate_arith
1403 || type==gate_observe) {
1404 /* gate_assumed carries its assumption kind ('boolean' /
1405 * 'absorptive') in extra; gate_mobius carries its per-child integer
1406 * coefficients ("uuid:coeff" tokens); a gate_arith PERCENTILE
1407 * carries its fraction (agg-carrier arith gates carry a display
1408 * value there, inert for evaluation); gates stored without the
1409 * label have none and default to 'boolean' at
1410 * evaluation. */
1411 auto extra = extraAt(idx);
1412 result.setExtra(id, extra);
1413 }
1414}
1415
1417 const std::vector<FormulaRequest> &requests, unsigned long cap,
1418 unsigned long wide_cap) const
1419{
1421 constexpr unsigned long NOTHING = MMappedUUIDHashTable::NOTHING;
1422
1423 /* The size of the formula of each gate met, by its index, counted up to
1424 * wide_cap + 1 only: past it, the rest of the children are not looked at.
1425 * A wire closing a cycle counts for one. */
1426 std::unordered_map<unsigned long, unsigned long> size;
1427 struct Frame {
1428 unsigned long idx;
1429 unsigned long k; ///< Next child to count
1430 unsigned long acc; ///< Size so far
1431 };
1432 auto size_of = [&](unsigned long root) -> unsigned long {
1433 if(root == NOTHING)
1434 return 1;
1435 auto it = size.find(root);
1436 if(it != size.end())
1437 return it->second;
1438 std::unordered_map<unsigned long, bool> on_stack;
1439 std::vector<Frame> stack{{root, 0, 1}};
1440 on_stack[root] = true;
1441 while(!stack.empty()) {
1442 Frame &f = stack.back();
1443 const GateInformation &gi = gates[f.idx];
1444 bool pushed = false;
1445 /* An equation system is rendered whole: its unknowns have no formula
1446 * of their own */
1447 if(gi.type != gate_fixpoint)
1448 while(f.k < gi.nb_children && f.acc <= wide_cap) {
1449 const unsigned long c = mapping[wires[gi.children_idx + f.k]];
1450 unsigned long s;
1451 if(c == NOTHING)
1452 s = 1;
1453 else if(on_stack.count(c))
1454 s = 1;
1455 else {
1456 auto ic = size.find(c);
1457 if(ic == size.end()) {
1458 stack.push_back({c, 0, 1});
1459 on_stack[c] = true;
1460 pushed = true;
1461 break;
1462 }
1463 s = ic->second;
1464 }
1465 f.acc += s > cap ? 1 : s;
1466 ++f.k;
1467 }
1468 if(pushed)
1469 continue;
1470 const unsigned long done = std::min(f.acc, wide_cap + 1);
1471 size[f.idx] = done;
1472 on_stack.erase(f.idx);
1473 stack.pop_back();
1474 }
1475 return size.at(root);
1476 };
1477
1478 std::unordered_set<unsigned long> stubbed;
1479 std::unordered_set<gate_uuid, gate_uuid_hash> included;
1480 auto stub = [&](pg_uuid_t u, unsigned long idx) {
1481 if(!stubbed.insert(idx).second)
1482 return;
1483 const GateInformation &gi = gates[idx];
1485 gate_input);
1486 r.stubs.push_back({uuid2string(u), gi.type, gi.info1, gi.info2,
1487 gi.nb_children});
1488 };
1489 /* The region of @p u: it, and the gates below down to the named ones,
1490 * stubs (all of them below an equation system) */
1491 auto include = [&](pg_uuid_t u) {
1492 std::vector<std::pair<pg_uuid_t, bool> > todo{{u, false}};
1493 while(!todo.empty()) {
1494 auto [v, whole] = todo.back();
1495 todo.pop_back();
1496 if(!included.insert(gate_uuid::fromBytes(v.data)).second)
1497 continue;
1498 const gate_t id = copyGate(r.circuit, v);
1499 const unsigned long idx = mapping[v];
1500 if(idx == NOTHING)
1501 continue;
1502 const GateInformation &gi = gates[idx];
1503 whole = whole || gi.type == gate_fixpoint;
1504 for(unsigned long k = 0; k < gi.nb_children; ++k) {
1505 const pg_uuid_t w = wires[gi.children_idx + k];
1506 const unsigned long wi = mapping[w];
1508 if(!whole && wi != NOTHING && size_of(wi) > cap)
1509 stub(w, wi);
1510 else
1511 todo.push_back({w, whole});
1512 }
1513 }
1514 };
1515
1516 for(const auto &q : requests) {
1517 const unsigned long idx = mapping[q.gate];
1518 if(q.count == 0) {
1519 if(idx != NOTHING) {
1520 const GateInformation &gi = gates[idx];
1521 if(gi.nb_children > 1 && size_of(idx) > wide_cap
1522 && (gi.type == gate_plus || gi.type == gate_times
1523 || gi.type == gate_agg)) {
1524 stub(q.gate, idx);
1525 continue;
1526 }
1527 }
1528 include(q.gate);
1529 } else if(idx != NOTHING) {
1530 const GateInformation &gi = gates[idx];
1531 for(unsigned long k = q.from; k < q.from + q.count && k < gi.nb_children;
1532 ++k) {
1533 const pg_uuid_t w = wires[gi.children_idx + k];
1534 const unsigned long wi = mapping[w];
1535 r.children.push_back(uuid2string(w));
1536 if(wi != NOTHING && size_of(wi) > cap)
1537 stub(w, wi);
1538 else
1539 include(w);
1540 }
1541 }
1542 }
1543
1544 return r;
1545}
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Out-of-line template method implementations for Circuit<gateType>.
Semiring-agnostic in-memory provenance circuit.
static std::map< Oid, Oid > circuit_tablespaces
The tablespace of each open circuit, to find its files again.
static constexpr const char * CLEANUP_SUFFIX
Suffix of the files a clean-up builds beside the live ones.
static void finishInterruptedCleanup(Oid db_oid, Oid db_tablespace)
Bring a database's store to a definite state before opening it.
static void cleanupStore(Oid db_oid, Oid db_tablespace, const std::vector< pg_uuid_t > &roots, bool dry_run, provsql_cleanup_result *out)
Rebuild a database's store, keeping only what roots reach.
static bool carriesProb(gate_type type)
Whether type is one of the gate kinds that carry a probability.
#define PROVSQL_FROM_SPOOL
static std::map< Oid, MMappedCircuit * > circuits
Per-database mmap-backed provenance circuits, keyed by database OID.
void destroy_provsql_mmap()
Unmap and close the mmap files.
void provsql_store_flush(void)
Force every open circuit to stable storage.
void provsql_mmap_dispatch(char c, Oid db_oid, Oid db_tablespace)
Serve one message of the store's protocol.
bool operator<(const pg_uuid_t a, const pg_uuid_t b)
Lexicographic less-than comparison for pg_uuid_t.
void provsql_mmap_main_loop()
Main processing loop of the mmap background worker.
static MMappedCircuit * getCircuit(Oid db_oid, Oid db_tablespace)
Return (creating lazily if needed) the circuit for db_oid.
void initialize_provsql_mmap()
Initialise the circuit store.
static bool store_dirty
Whether any circuit has been written to since the last flush.
static void send_circuit(const MMappedCircuit *circuit, const std::vector< pg_uuid_t > &roots, unsigned long budget, char message_char)
Answer a 'g' / 'j' request: the circuit reachable from roots, serialised, preceded by its size.
static constexpr const char * CLEANUP_MARKER
Marker file present only while a clean-up's rename sequence is in flight; see finishInterruptedCleanu...
static void closeDroppedCircuits()
Close the circuits of the databases dropped since they were opened.
static void dispatch(char c, Oid db_oid, Oid db_tablespace)
The body of provsql_mmap_dispatch, which may throw.
Persistent, mmap-backed storage for the full provenance circuit.
constexpr unsigned long PROVSQL_CIRCUIT_OVER_BUDGET
The size the worker answers a 'g' / 'j' request with, in place of a circuit, when building it went pa...
constexpr unsigned long PROVSQL_CIRCUIT_CANCELLED
The size the worker answers a 'g' / 'j' request with, in place of a circuit, when the requesting stat...
Thrown by MMappedCircuit::createGenericCircuit when the circuit it builds takes the process past the ...
Thrown by MMappedCircuit::createGenericCircuit when the statement that asked for the circuit is cance...
void addWire(gate_t f, gate_t t)
Add a directed wire from gate f (parent) to gate t (child).
Definition Circuit.hpp:195
std::pair< gate_t, bool > findOrAddGate(const gate_uuid &u)
Return (or create) the gate associated with UUID u, and whether it was created.
Definition Circuit.hpp:39
gate_t getGate(const uuid &u)
Return (or create) the gate associated with UUID u.
Definition Circuit.hpp:50
void setInfos(gate_t g, unsigned info1, unsigned info2)
Set the integer annotation pair for gate g.
gate_t setGate(gate_type type) override
Allocate a new gate with type type and no UUID.
void setExtra(gate_t g, const std::string &ex)
Attach a string extra to gate g.
void setProb(gate_t g, double p)
Set the probability for gate g.
Persistent mmap-backed representation of the provenance circuit.
static constexpr uint16_t GATES_VERSION
Format version of the gates file this build writes.
unsigned long mark(const std::vector< pg_uuid_t > &roots, std::vector< bool > &live) const
Mark every gate reachable from roots.
FormulaRegions formulaRegions(const std::vector< FormulaRequest > &requests, unsigned long cap, unsigned long wide_cap) const
The regions of requests, for sr_formula_rows (see FormulaRegions).
SetAnnotationResult setInfos(pg_uuid_t token, unsigned info1, unsigned info2, std::pair< unsigned, unsigned > *existing=nullptr)
Write the info1 / info2 annotations of a gate, once.
MMappedUUIDHashTable mapping
UUID → gate-index hash table.
void createGate(pg_uuid_t token, gate_type type, const std::vector< pg_uuid_t > &children)
Persist a new gate to the mmap store.
Counts counts() const
This store's current size.
std::string getExtra(pg_uuid_t token) const
Return the variable-length string annotation for gate token.
bool legacyProbabilities() const
Whether this store's gates file predates the NaN unset-probability convention (see GATES_VERSION).
SetProbResult setProb(pg_uuid_t token, double prob, double *existing=nullptr)
Write a gate's probability, once.
void appendGate(pg_uuid_t token, gate_type type, const std::vector< pg_uuid_t > &children)
Append a complete gate record, then publish token for it.
double probAt(unsigned long idx) const
getProb of the record idx.
unsigned long getNbGates() const
Return the total number of gates stored in the circuit.
SetProbResult
Outcome of setProb.
@ NotProbGate
The token names a gate that carries no probability.
@ Unchanged
The gate already held exactly this probability.
@ Written
The gate had no probability and now holds the given one.
@ AlreadySet
The gate holds a different probability; refused.
std::string extraAt(unsigned long idx) const
getExtra of the record idx.
static constexpr const char * GATES_FILENAME
Backing file for gates.
Counts sweepInto(const std::vector< bool > &live, const std::string &mp, const std::string &gp, const std::string &wp, const std::string &ep) const
Copy the gates flagged in live into a fresh set of files beside the current ones (suffix "....
gate_type getGateType(pg_uuid_t token) const
Return the type of the gate identified by token.
Check check() const
Walk the store and report what does not add up.
void sync()
Flush all backing files to disk with msync().
static std::string storePath(Oid db_oid, Oid db_tablespace, const char *filename)
Build the full path of a file in a database's store directory, the one GetDatabasePath resolves for d...
static constexpr const char * WIRES_FILENAME
Backing file for wires.
void copyGateAt(GenericCircuit &result, gate_t id, unsigned long idx) const
Give the gate id of result what the record idx (NOTHING for a gate not stored: an input) records but ...
MMappedCircuit(const std::string &mp, const std::string &gp, const std::string &wp, const std::string &ep, bool read_only)
Delegating constructor that accepts pre-built paths.
gate_t copyGate(GenericCircuit &result, pg_uuid_t uuid) const
Add the gate uuid to result, with what it records but its wires.
static bool storeExists(Oid db_oid, Oid db_tablespace)
Whether the store of db_oid in db_tablespace still has its gates file: false once the database is dro...
bool uncleanShutdown() const
Whether any backing file was found still marked open-for-writing when it was opened – the previous wr...
static constexpr const char * EXTRA_FILENAME
Backing file for extra.
static constexpr uint64_t MAGIC_WIRES
static constexpr uint64_t MAGIC_GATES
8-byte magic constants identifying each mmap file type.
static constexpr const char * MAPPING_FILENAME
Backing file for mapping.
bool hasProb(pg_uuid_t token, double *prob) const
Report whether token names a gate that holds a probability.
MMappedVector< char > extra
Variable-length string data.
static constexpr uint64_t MAGIC_EXTRA
double getProb(pg_uuid_t token) const
Return the probability an evaluation would use for token.
std::vector< pg_uuid_t > getChildren(pg_uuid_t token) const
Return the child UUIDs of the gate identified by token.
MMappedVector< GateInformation > gates
Gate metadata array.
SetAnnotationResult setExtra(pg_uuid_t token, const std::string &s, std::string *existing=nullptr)
Attach a variable-length string annotation to a gate, once.
SetAnnotationResult
Outcome of setInfos or setExtra.
@ Unchanged
The gate already held exactly this annotation.
@ Written
The gate had none and now holds the given annotation.
@ NoSuchGate
The token names no gate.
@ AlreadySet
The gate holds a different annotation; refused.
bool hasProbAt(unsigned long idx) const
Whether the gate record at index idx holds a written probability (see GATES_VERSION for the version-1...
MMappedVector< pg_uuid_t > wires
Flattened child UUID array.
GenericCircuit createGenericCircuit(pg_uuid_t token, std::size_t budget=0) const
Build an in-memory GenericCircuit rooted at token.
static constexpr uint64_t MAGIC_MAPPING
std::pair< unsigned, unsigned > getInfos(pg_uuid_t token) const
Return the info1 / info2 pair for the gate token.
void flush()
Force every backing file to stable storage.
Persistent open-addressing hash table mapping UUIDs to integers.
std::pair< unsigned long, bool > publish(pg_uuid_t u, unsigned long value)
Insert UUID u with a caller-chosen value.
static constexpr unsigned long NOTHING
Sentinel returned by operator[]() when the UUID is not present.
void flush()
Force the backing file to stable storage (MappedRegion::flush()).
Append-only, mmap-backed vector of elements of type T.
void flush()
Force the backing file to stable storage (MappedRegion::flush()).
unsigned long nbElements() const
Return the number of elements currently stored.
void add(const T &value)
Append an element to the end of the vector.
std::size_t provsql_process_rss(pid_t pid)
The resident memory of process pid, in bytes, or 0 where the platform does not say.
Resident memory of a process, or of a process group.
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current transaction.
#define provsql_warning(fmt,...)
Emit a ProvSQL warning message (execution continues).
static constexpr unsigned long NOTHING
bool provsql_worker_spooled(void)
Whether store messages spooled during crash recovery remain to be applied (they come before the pipe)...
bool provsql_worker_buffered(void)
Whether the worker's read buffer holds unread bytes, which poll() cannot see.
bool provsql_store_cancel_requested(void)
Whether the circuit being built should be given up: in the worker, the backend that asked for it was ...
bool provsql_worker_from_spool
Whether the message being applied comes from the replay spool: it is not answered,...
Background worker and IPC primitives for mmap-backed circuit storage.
#define WRITEB_BYTES(ptr, n)
Write n reply bytes to the main-to-background pipe.
#define READM(var, type)
Read one value of type from the background-to-main pipe.
#define WRITEB(pvar, type)
Write one value of type to the main-to-background pipe.
#define PROVSQL_STORE_FLUSH_INTERVAL_MS
How long the worker waits after a write before forcing the store to stable storage.
#define READM_BYTES(ptr, n)
Read exactly n bytes of a request from the background-to-main pipe.
provsqlSharedState * provsql_shared_state
Pointer to the ProvSQL shared-memory segment (set in provsql_shmem_startup).
Shared-memory segment and inter-process pipe management.
@ gate_observe
Latent-variable observation (likelihood-weighting evidence): one wire → an observed bare gate_rv leaf...
@ gate_rv
Continuous random-variable leaf (extra encodes distribution).
@ gate_annotation
Transparent single-child wrapper carrying a query-level annotation in extra (inversion-free certifica...
@ gate_mobius
Signed Möbius combination: a MEASURE-only gate carrying one integer coefficient per child (in extra,...
@ gate_fixpoint
Component of the least solution of an equation system: one wire to a gate_fixsystem,...
@ gate_arith
n-ary arithmetic gate over scalar-valued children (info1 holds operator tag)
@ gate_assumed
Structural marker over a single child whose sub-circuit was computed under a Boolean-provenance assum...
string uuid2string(pg_uuid_t uuid)
Format a pg_uuid_t as a std::string.
C++ utility functions for UUID manipulation.
The regions of a few requests, in one circuit.
std::vector< std::string > children
The children asked for, in order.
GenericCircuit circuit
The gates of the regions.
std::vector< FormulaStub > stubs
The gates left out.
Per-gate metadata stored in the gates MMappedVector.
double prob
Associated probability, NaN when unset.
unsigned info2
General-purpose integer annotation 2.
unsigned long children_idx
Start index of this gate's children in wires.
unsigned info1
General-purpose integer annotation 1.
unsigned long extra_idx
Start index in extra for string data.
unsigned extra_len
Byte length of the string data in extra.
unsigned nb_children
Number of children.
gate_type type
Kind of gate (input, plus, times…).
What provsql.check_store() reports about a store.
unsigned long dangling_indices
Mapping entries indexing past the records.
unsigned long nb_gates
Gate records.
unsigned long bad_extra
Records whose extra runs past the extra file.
bool unclean
A file was left marked open-for-writing.
unsigned long nb_mapping
Mapping entries.
unsigned long unreferenced
Records no mapping entry points at.
unsigned long bad_wires
Records whose children run past the wires.
unsigned long next_value
Next index the mapping would assign.
The size of a store, in the three units that matter.
unsigned long extra_bytes
Bytes of variable-length annotation.
unsigned long gates
Gate records.
unsigned long wires
Child wires.
A UUID as its 16 bytes, read as two big-endian words.
Definition Circuit.h:62
void toBytes(unsigned char *p) const
Write the 16 bytes of the UUID to p.
Definition Circuit.h:77
static gate_uuid fromBytes(const unsigned char *p)
The UUID whose 16 bytes start at p.
Definition Circuit.h:67
What provsql.circuit_cleanup() reports.
uint64 wires_before
Child wires before.
uint64 wires_after
Child wires kept.
uint64 extra_before
Annotation bytes before.
uint64 gates_after
Gate records kept.
uint64 extra_after
Annotation bytes kept.
uint64 gates_before
Gate records before.