ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
CircuitFromMMap.cpp
Go to the documentation of this file.
1/**
2 * @file CircuitFromMMap.cpp
3 * @brief Build in-memory circuits from the mmap-backed store.
4 *
5 * Implements the free functions declared in @c CircuitFromMMap.h:
6 * - @c getBooleanCircuit(): reads the mmap store (via the background
7 * worker IPC channel) and constructs a @c BooleanCircuit.
8 * - @c getGenericCircuit(): same but constructs a @c GenericCircuit.
9 *
10 * The internal @c getCircuitFromMMap<C>() template handles the IPC
11 * protocol: it sends a request through the shared-memory pipe,
12 * receives a Boost-serialised circuit blob from the background worker,
13 * and deserialises it into the appropriate circuit type.
14 */
15#include <cmath>
16
17#include <boost/archive/binary_iarchive.hpp>
18#include <boost/iostreams/device/array.hpp>
19#include <boost/iostreams/stream.hpp>
20
21#include "CircuitFromMMap.h"
22#include "MMappedCircuit.h"
23#include "HybridEvaluator.h"
24#include "RangeCheck.h"
25#include "having_semantics.hpp"
26#include "semiring/BoolExpr.h"
27#include "provsql_utils_cpp.h"
28#include "provsql_interrupt.h"
29
30#include <vector>
31
32extern "C" {
33#include "miscadmin.h"
34#include "provsql_shmem.h"
35#include "provsql_mmap.h"
36#include "provsql_utils.h"
37}
38
39/**
40 * @brief What the statement has left of @c provsql.max_memory, in bytes, for
41 * building a circuit; 0 for no limit.
42 *
43 * The circuit store builds and serialises the circuit in the worker, a
44 * process of its own, which the budget would not see otherwise; the request
45 * carries what is left of it, and the worker refuses past it (GitHub #104).
46 */
47static unsigned long circuit_budget()
48{
49 if(provsql_max_memory <= 0)
50 return 0;
51 const std::size_t max = (std::size_t) provsql_max_memory * 1024 * 1024;
52 const std::size_t used = provsql_memory_used();
53 return used >= max ? 1 : max - used;
54}
55
56/** @brief Stop at @c provsql.max_memory: the circuit to load is larger than
57 * the statement has left of it. */
58[[noreturn]] static void circuit_over_budget()
59{
61 "memory-limit",
62 ("the circuit to evaluate is larger than provsql.max_memory (" +
63 std::to_string(provsql_max_memory) + " MB) allows").c_str(),
64 "Raise provsql.max_memory (e.g., SET provsql.max_memory = '2GB'), or "
65 "set it to 0 for no limit.");
66 throw CircuitBudgetExceeded(); /* not reached */
67}
68
69/** @brief Stop for a cancel (or a terminate) of the statement, received
70 * while its circuit was loaded: as the evaluation loops do, by a throw
71 * that the entry point turns into PostgreSQL's own error. */
72[[noreturn]] static void circuit_load_cancelled()
73{
75 throw CircuitException("Interrupted");
76}
77
78#ifndef PROVSQL_INPROCESS_STORE
79/**
80 * @brief Read the worker's answer to a @c 'g' / @c 'j' request just sent,
81 * and release the store lock.
82 *
83 * @return The serialised circuit, of @p size bytes, to be freed by the
84 * caller; what stops the load (the budget, a cancel) is thrown.
85 */
86static char *readCircuitReply(unsigned long &size, char message_char)
87{
88 const bool cancelled = provsql_wait_reply();
89
90 if(!READB(size, unsigned long))
91 provsql_error("Cannot read from pipe (message type %c)", message_char);
92 if(size == PROVSQL_CIRCUIT_OVER_BUDGET ||
95 if(cancelled)
98 }
99
100 char *buf = new char[size];
101 if(!READB_BYTES(buf, size)) {
103 delete [] buf;
104 provsql_error("Cannot read from pipe (message type %c)", message_char);
105 }
107
108 if(cancelled) {
109 delete [] buf;
111 }
112 return buf;
113}
114
115/**
116 * @brief Read and deserialise a circuit rooted at @p token from the mmap worker.
117 * @tparam C Circuit type to deserialise (@c BooleanCircuit or @c GenericCircuit).
118 * @param token UUID of the root gate to retrieve.
119 * @param message_char IPC message-type byte sent to the background worker.
120 * @return Deserialised circuit of type @c C.
121 */
122template<typename C>
123static C getCircuitFromMMap(pg_uuid_t token, char message_char)
124{
125 unsigned long budget = circuit_budget();
126
127 STARTWRITEM();
128 ADDWRITEM(&message_char, char);
129 ADDWRITEDB();
130 ADDWRITEM(&token, pg_uuid_t);
131 ADDWRITEM(&budget, unsigned long);
132
136 if(!SENDWRITEM())
137 provsql_error("Cannot write to pipe (message type %c)", message_char);
138
139 unsigned long size;
140 char *buf = readCircuitReply(size, message_char);
141
142 C c;
143 try {
145 boost::iostreams::stream<boost::iostreams::array_source> stream(buf, size);
146 boost::archive::binary_iarchive ia(stream);
147 ia >> c;
148 } catch(...) {
149 delete [] buf;
150 throw;
151 }
152
153 delete [] buf;
155
156 return c;
157}
158#endif
159
161 GenericCircuit &gc,
162 pg_uuid_t token,
163 gate_t &gate,
164 std::unordered_map<gate_t, gate_t> &gc_to_bc)
165{
166 auto ggate = gc.getGate(uuid2string(token));
168 for(gate_t u: gc.getInputs()) {
169 gc_to_bc[u]=c.setGate(gc.getUUID(u), BooleanGate::IN, gc.getProb(u));
170 }
171 for(size_t i=0; i<gc.getNbGates(); ++i) {
172 auto u=static_cast<gate_t>(i);
173 if(gc.getGateType(u)==gate_mulinput) {
174 gc_to_bc[u]=c.setGate(gc.getUUID(u), BooleanGate::MULIN, gc.getProb(u));
175 c.setInfo(gc_to_bc[u], gc.getInfos(u).first);
176 c.addWire(
177 gc_to_bc[u],
178 gc_to_bc[gc.getWires(u)[0]]);
179 }
180 }
182 provsql_having(gc, ggate, gc_to_bc, semiring);
183 gate=gc.evaluate(ggate, gc_to_bc, semiring);
184 propagateDNNFCertificate(gc, gc_to_bc, c);
185
186 return c;
187}
188
190 const GenericCircuit &gc,
191 const std::unordered_map<gate_t, gate_t> &gc_to_bc,
193{
194 for(const auto &[u, b]: gc_to_bc) {
195 const auto t = gc.getGateType(u);
196 if((t != gate_plus && t != gate_times) ||
197 gc.getInfos(u).first != DNNF_CERT_INFO)
198 continue;
199 const auto bt = c.getGateType(b);
200 if((t == gate_plus && bt == BooleanGate::OR) ||
201 (t == gate_times && bt == BooleanGate::AND))
203 }
204}
205
207{
209 std::unordered_map<gate_t, gate_t> gc_to_bc;
210 return getBooleanCircuit(gc, token, gate, gc_to_bc);
211}
212
213/**
214 * @brief Apply the universal load-time simplification passes to @p gc.
215 *
216 * Extracted from @c getGenericCircuit so the joint-circuit loader
217 * (@c getJointCircuit) runs the same passes on its multi-root output.
218 * Gated by the @c provsql.simplify_on_load GUC, identical semantics.
219 */
221{
222 /* A comparison whose two sides are the very same gate is settled by the
223 * operator alone -- and settling it true is the OR over the group's
224 * k-gates, not gate_one. It has to be decided BEFORE the folds below,
225 * which would otherwise read it as a constant and lose with it the fact
226 * that the group is there. Not gated by simplify_on_load: it is a
227 * structural rewrite, and leaving it undone is a wrong answer, not a
228 * missed simplification. */
232 /* Fold deterministic @c gate_arith subtrees to @c gate_value
233 * before @c foldSemiringIdentities (which then collapses any
234 * single-wire @c gate_times / @c gate_plus wrappers around the
235 * resulting @c gate_value). Constant folding is uniformly safe
236 * across consumers: a @c gate_value carries no random identity,
237 * so no shared-RV coupling is decoupled by the rewrite. Lifts
238 * common parser shapes -- the @c -c::random_variable cast emits
239 * @c arith(NEG, value:c) where @c value:-c would round-trip
240 * identically -- into the canonical form so downstream
241 * @c collectRvConstraints / @c asRvVsConstCmp recognise them. */
242 /* Collapse Bernoulli mixtures whose selector is the constant
243 * gate_one / gate_zero (a comparison decided above, say) to the
244 * surviving arm, before constant folding. Nothing here reads a
245 * probability: a mixture over a tuple's token is left in place
246 * whatever that token's probability, so the circuit every consumer
247 * sees -- the displayed one included -- keeps its provenance. The
248 * probability readouts fold those too, separately
249 * (applyProbabilisticSimplification). */
253 }
254 /* Class-gated simplification, independent of simplify_on_load
255 * (dropping the universal passes does not drop these). Under the
256 * 'boolean' provenance class the full rule set applies
257 * (times-idempotence and times-absorbs-plus included); under
258 * 'absorptive', only the rules sound in every absorptive semiring
259 * (plus-idempotence, plus-with-one absorber, plus-absorbs-times).
260 * Each rule application marks the gate in the matching in-memory
261 * side-band set, the load-time signal to the evaluator that
262 * semirings outside the rule's class must refuse. */
267 }
268}
269
271{
273 return;
274 /* A mixture whose selector is certain by the probabilities of its
275 * inputs (every one 1 or 0, the default 1 of a tuple no probability
276 * has been written on included) reads as its surviving arm in every
277 * world, so the readouts, which already depend on probabilities, may
278 * fold it; the same constant folding as at load time then reduces,
279 * e.g., avg's count over certain tuples to a gate_value. */
280 if (provsql::foldDegenerateMixtures(gc, true) > 0) {
283 }
284}
285
287{
288#ifdef PROVSQL_INPROCESS_STORE
290 try {
291 gc = provsql_inproc_generic_circuit(token, circuit_budget());
292 } catch(const CircuitBudgetExceeded &) {
294 } catch(const CircuitCancelled &) {
296 }
297#else
299#endif
300
301 /* Apply universal cmp-resolution passes (currently RangeCheck) at
302 * load time so every downstream consumer -- semiring evaluators,
303 * MC, view_circuit, PROV export -- sees the simplified circuit.
304 * Each pass replaces decided gate_cmps with Bernoulli gate_input
305 * gates with probability 0 or 1 via
306 * GenericCircuit::resolveCmpToBernoulli; the rewrite is uniform
307 * across semirings (gate_zero / gate_one are the additive /
308 * multiplicative identities in any semiring) so a single sweep
309 * here is correct for every later evaluator.
310 *
311 * Gated by the provsql.simplify_on_load GUC so users debugging
312 * raw circuit structure can opt out. */
314
315 return gc;
316}
317
318/**
319 * @brief IPC: ship a 'j' (joint) request to the mmap worker and
320 * deserialise the returned @c GenericCircuit.
321 *
322 * Mirrors @c getCircuitFromMMap but writes the multi-root payload
323 * the worker's @c 'j' handler expects: <tt>'j' Oid nb_roots {pg_uuid_t}*</tt>.
324 * The response shape is identical to @c 'g' -- @c unsigned @c long
325 * size prefix followed by a Boost-serialised @c GenericCircuit.
326 */
328 const std::vector<pg_uuid_t> &tokens)
329{
330#ifdef PROVSQL_INPROCESS_STORE
331 try {
332 return provsql_inproc_joint_circuit(tokens, circuit_budget());
333 } catch(const CircuitBudgetExceeded &) {
335 } catch(const CircuitCancelled &) {
337 }
338#else
339 char message_char = 'j';
340 unsigned nb_roots = static_cast<unsigned>(tokens.size());
341 STARTWRITEM();
342 ADDWRITEM(&message_char, char);
343 ADDWRITEDB();
344 ADDWRITEM(&nb_roots, unsigned);
345 for(const pg_uuid_t &t : tokens)
346 ADDWRITEM(&t, pg_uuid_t);
347 unsigned long budget = circuit_budget();
348 ADDWRITEM(&budget, unsigned long);
349
353 if(!SENDWRITEM())
354 provsql_error("Cannot write to pipe (message type j)");
355
356 unsigned long size;
357 char *buf = readCircuitReply(size, message_char);
358
360 try {
362 boost::iostreams::stream<boost::iostreams::array_source> stream(buf, size);
363 boost::archive::binary_iarchive ia(stream);
364 ia >> c;
365 } catch(...) {
366 delete [] buf;
367 throw;
368 }
369
370 delete [] buf;
372
373 return c;
374#endif /* PROVSQL_INPROCESS_STORE */
375}
376
377FormulaRegions getFormulaRegions(const std::vector<FormulaRequest> &requests,
378 unsigned long cap, unsigned long wide_cap)
379{
381#ifdef PROVSQL_INPROCESS_STORE
382 r = provsql_inproc_formula_regions(requests, cap, wide_cap);
383#else
384 char message_char = 'F';
385 unsigned nb = static_cast<unsigned>(requests.size());
386 STARTWRITEM();
387 ADDWRITEM(&message_char, char);
388 ADDWRITEDB();
389 ADDWRITEM(&cap, unsigned long);
390 ADDWRITEM(&wide_cap, unsigned long);
391 ADDWRITEM(&nb, unsigned);
392 for(const auto &q : requests) {
393 ADDWRITEM(&q.gate, pg_uuid_t);
394 ADDWRITEM(&q.from, unsigned long);
395 ADDWRITEM(&q.count, unsigned long);
396 }
397
401 if(!SENDWRITEM())
402 provsql_error("Cannot write to pipe (message type F)");
403
404 const bool cancelled = provsql_wait_reply();
405 unsigned long size;
406 if(!READB(size, unsigned long))
407 provsql_error("Cannot read from pipe (message type F)");
408 char *buf = new char[size];
409 if(!READB_BYTES(buf, size)) {
411 delete [] buf;
412 provsql_error("Cannot read from pipe (message type F)");
413 }
415 if(cancelled) {
416 delete [] buf;
418 }
419
420 try {
422 boost::iostreams::stream<boost::iostreams::array_source> stream(buf, size);
423 boost::archive::binary_iarchive ia(stream);
424 ia >> r;
425 } catch(...) {
426 delete [] buf;
427 throw;
428 }
429 delete [] buf;
430#endif
431
433 return r;
434}
435
437 const std::vector<pg_uuid_t> &tokens,
438 std::vector<gate_t> &gates)
439{
441
443 /* Every caller of the joint loader reads a distribution or a
444 * probability (moments, quantiles, support, samples, histograms,
445 * covariance, information measures), never the displayed circuit. */
447
448 /* Resolve the gate_t for the roots AFTER simplification. The
449 * passes mutate gate types in place but never delete gates, so the
450 * UUID-to-gate_t map (and therefore @c getGate) stays valid. */
451 gates.resize(tokens.size());
452 for(std::size_t i = 0; i < tokens.size(); ++i)
453 gates[i] = gc.getGate(uuid2string(tokens[i]));
454
455 return gc;
456}
457
459 pg_uuid_t root_token,
460 pg_uuid_t event_token,
461 gate_t &root_gate,
462 gate_t &event_gate)
463{
464 std::vector<gate_t> gates;
465 GenericCircuit gc =
466 getJointCircuit(std::vector<pg_uuid_t>{root_token, event_token}, gates);
467 root_gate = gates[0];
468 event_gate = gates[1];
469 return gc;
470}
Boolean-expression (lineage formula) semiring.
constexpr unsigned DNNF_CERT_INFO
d-DNNF certificate value for the (gate-type-specific) per-gate info field.
@ OR
Logical disjunction of child gates.
@ AND
Logical conjunction of child gates.
@ IN
Input (variable) gate representing a base tuple.
@ MULIN
Multivalued-input gate (one of several options).
FormulaRegions getFormulaRegions(const std::vector< FormulaRequest > &requests, unsigned long cap, unsigned long wide_cap)
The regions of requests, for sr_formula_rows (see FormulaRegions), with the load-time simplification ...
BooleanCircuit getBooleanCircuit(GenericCircuit &gc, pg_uuid_t token, gate_t &gate, std::unordered_map< gate_t, gate_t > &gc_to_bc)
Build a BooleanCircuit from an already-loaded GenericCircuit.
void applyProbabilisticSimplification(GenericCircuit &gc)
Simplify a loaded circuit for a probability readout.
static char * readCircuitReply(unsigned long &size, char message_char)
Read the worker's answer to a 'g' / 'j' request just sent, and release the store lock.
void propagateDNNFCertificate(const GenericCircuit &gc, const std::unordered_map< gate_t, gate_t > &gc_to_bc, BooleanCircuit &c)
Propagate the per-gate d-DNNF certificate from gc to c.
static unsigned long circuit_budget()
What the statement has left of provsql.max_memory, in bytes, for building a circuit; 0 for no limit.
static void circuit_load_cancelled()
Stop for a cancel (or a terminate) of the statement, received while its circuit was loaded: as the ev...
GenericCircuit getJointCircuit(const std::vector< pg_uuid_t > &tokens, std::vector< gate_t > &gates)
Multi-root variant of getJointCircuit.
static C getCircuitFromMMap(pg_uuid_t token, char message_char)
Read and deserialise a circuit rooted at token from the mmap worker.
static GenericCircuit getJointCircuitFromMMap(const std::vector< pg_uuid_t > &tokens)
IPC: ship a 'j' (joint) request to the mmap worker and deserialise the returned GenericCircuit.
GenericCircuit getGenericCircuit(pg_uuid_t token)
Build a GenericCircuit from the mmap store rooted at token.
static void applyLoadTimeSimplification(GenericCircuit &gc)
Apply the universal load-time simplification passes to gc.
static void circuit_over_budget()
Stop at provsql.max_memory: the circuit to load is larger than the statement has left of it.
Build in-memory circuits from the mmap-backed persistent store.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Peephole simplifier for continuous gate_arith sub-circuits.
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...
Support-based bound check for continuous-RV comparators.
Boolean circuit for provenance formula evaluation.
gate_t setGate(BooleanGate type) override
Allocate a new gate with type type and no UUID.
void setInfo(gate_t g, unsigned info)
Store an integer annotation on gate g.
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...
Exception type thrown by circuit operations on invalid input.
Definition Circuit.h:382
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
Definition Circuit.h:311
gateType getGateType(gate_t g) const
Return the type of gate g.
Definition Circuit.h:301
void addWire(gate_t f, gate_t t)
Add a directed wire from gate f (parent) to gate t (child).
Definition Circuit.hpp:195
uuid getUUID(gate_t g) const
Return the UUID string associated with gate g.
Definition Circuit.hpp:65
gate_t getGate(const uuid &u)
Return (or create) the gate associated with UUID u.
Definition Circuit.hpp:50
std::vector< gate_t >::size_type getNbGates() const
Return the total number of gates in the circuit.
Definition Circuit.h:252
const S::value_type & evaluate(gate_t g, std::unordered_map< gate_t, typename S::value_type > &provenance_mapping, S semiring) const
Evaluate the sub-circuit rooted at gate g over semiring semiring.
bool foldSemiringIdentities()
Drop semiring identity wires and collapse single-wire gate_times / gate_plus to their lone non-identi...
void foldAbsorptiveIdentities()
Absorptive-rules-only variant of foldBooleanIdentities(): the joint fixpoint of the absorptive fold r...
double getProb(gate_t g) const
Return the probability for gate g.
const std::set< gate_t > & getInputs() const
Return the set of input (leaf) gates.
std::pair< unsigned, unsigned > getInfos(gate_t g) const
Return the integer annotation pair for gate g.
void foldBooleanIdentities()
Apply the Boolean-only AND the absorptive simplification rules to gate_plus and gate_times,...
Provenance-as-Boolean-circuit semiring.
Definition BoolExpr.h:48
Provenance evaluation helper for HAVING-clause circuits.
void provsql_having(GenericCircuit &c, gate_t g, MapT &mapping, SemiringT S=SemiringT{})
Rewrite HAVING comparison gates in the circuit into their possible-world provenance (world enumeratio...
unsigned foldDegenerateMixtures(GenericCircuit &gc, bool read_probabilities)
Collapse degenerate Bernoulli gate_mixture gates whose selector is certainly true (pi = 1) or certain...
unsigned runConstantFold(GenericCircuit &gc)
Constant-fold pass over every gate_arith in gc.
unsigned runReflexiveCmpRewriter(GenericCircuit &gc)
Probability-side pre-pass: rewrite HAVING-style gate_cmp gates that are provably TRUE on the agg's va...
unsigned runRangeCheck(GenericCircuit &gc)
Run the support-based pruning pass over gc.
bool provsql_absorptive_provenance
Derived flag: the session's provenance class is 'absorptive' or 'boolean' – licenses constructions so...
Definition provsql.c:154
bool provsql_simplify_on_load
Run universal cmp-resolution passes when getGenericCircuit returns; controlled by the provsql....
Definition provsql.c:138
bool provsql_interrupted
Set by provsql_sigint_handler: this backend received a cancel.
Definition provsql.c:111
bool provsql_boolean_provenance
Derived flag: the session's provenance class is 'boolean' – enables the Boolean-only machinery (safe-...
Definition provsql.c:153
int provsql_max_memory
Memory, in MB, that the evaluations of a statement may add to the backend's resident set,...
Definition provsql.c:131
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current transaction.
void provsql_limit_exceeded(const char *tag, const char *message, const char *hint)
Stop the evaluation at a resource limit (provsql.max_memory, provsql.max_worlds): throws,...
size_t provsql_memory_used(void)
How much the backend's resident memory has grown since the first evaluation of the statement,...
void provsql_check_memory(void)
Throw if the evaluations of the statement have made the backend's resident memory grow by more than p...
Cancellation of the long C++ evaluation loops.
void provsql_request_start(void)
Start a request that may keep the worker busy (the building of a circuit): no cancel is pending for i...
bool provsql_wait_reply(void)
Wait, under the store lock, until the worker's reply to this backend's request can be read.
Background worker and IPC primitives for mmap-backed circuit storage.
#define ADDWRITEDB()
Append the per-message database header to the write buffer.
#define READB_BYTES(ptr, n)
Read exactly n bytes of a reply from the main-to-background pipe.
#define READB(var, type)
Read one value of type from the main-to-background pipe.
#define STARTWRITEM()
Reset the shared write buffer for a new batched write.
#define ADDWRITEM(pvar, type)
Append one value of type to the shared write buffer.
#define SENDWRITEM()
Flush the shared write buffer to the background-to-main pipe atomically.
void provsql_shmem_unlock(void)
Release the ProvSQL LWLock.
bool provsql_shmem_lock_exclusive_unless_cancelled(void)
Acquire the ProvSQL LWLock in exclusive mode, unless the statement is cancelled (or the backend termi...
Shared-memory segment and inter-process pipe management.
Core types, constants, and utilities shared across ProvSQL.
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.
GenericCircuit circuit
The gates of the regions.