oxenstored maintains two datastructures about watches; one global trie, and
one hashtable tracked per domain. Both need keeping in sync, and right now
the global trie is not emptied when a xenbus reconnect is requested.
This is basically the same bug as XSA-330, commit 491a077ed4
("tools/ocaml/xenstored: delete watch from trie too when resetting watches"),
just tickled via another path.
Arrange for both Process.do_reset_watches() and Process.do_reconnect() to
share a common codepath for the resetting of watches and transactions.
Notably, this means that the latter now calls Connections.del_watches() which
clears the global trie too.
Connections.del_watches() already calls Connection.del_watches() so remove the
re-clearing of the state from Connection.do_reconnect().
Move History.trim() into reset_watches_and_transactions() so it's on the
common path, and place it after removing the transactions rather than before.
This is part of XSA-512 / CVE-2026-79604.
Reported-by: David Korczynski <David@Adalogics.com>
Fixes: 674ad2be40 ("xenstore: extend the xenstore ring with a 'closing' signal")
Signed-off-by: Andrii Sultanov <andriy.sultanov@vates.tech>
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Reviewed-by: Andrii Sultanov <andriy.sultanov@vates.tech>
The logic flow here is complicated. In preparation to fix a bug, factor out
reconnecting a xenbus connection, and fold History.reconnect into it's single
caller.
No functional change.
This is part of XSA-512 / CVE-2026-79604.
Signed-off-by: Andrii Sultanov <andriy.sultanov@vates.tech>
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Reviewed-by: Andrii Sultanov <andriy.sultanov@vates.tech>
The quota object contains both limits and the current node usage counts.
When a domain is torn down, the node data itself is cleaned up but the node
usage counts are not. A later domain reusing the same domid can create fewer
nodes before being deemed to be over quota.
Reset the count when the node permissions are cleaned up.
This is XSA-483 / CVE-2026-23556.
Signed-off-by: Andrii Sultanov <andriy.sultanov@vates.tech>
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Use the apply-build-vars make macro to replace the @xxx@ markers in
most *.in files only at build time.
As some of the markers are local to tools/configure, introduce
config/Tools-paths.mk.in and add the related make variables to it.
Add Tools-paths to the PATH_FILES make variable in order to include
the definitions for replacing them in the *.in files.
Add the generated files to the distclean target.
Signed-off-by: Juergen Gross <jgross@suse.com>
Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
OCaml, in preparation for a renaming of the error string associated with
conversion failure in 'int_of_string' functions, started to issue this
warning:
File "process.ml", line 440, characters 13-28:
440 | | (Failure "int_of_string") -> reply_error "EINVAL"
^^^^^^^^^^^^^^^
Warning 52 [fragile-literal-pattern]: Code should not depend on the actual values of
this constructor's arguments. They are only for information
and may change in future versions. (See manual section 11.5)
Deal with this at the source, and instead create our own stable
ConversionFailure exception that's raised on the None case in
'int_of_string_opt'.
'c_int_of_string' is safe and does not raise such exceptions.
Signed-off-by: Andrii Sultanov <andrii.sultanov@cloud.com>
Acked-by: Christian Lindig <christian.lindig@cloud.com>
Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
Oxenstored dynamically loads the plugin provided in ocaml/libs/xsd_glue.
The plugin is verified to be providing the specified plugin_interface
during its loading.
If a V2 of the plugin is produced, V1 will still be present, and a new
version should only be loaded if it's verified to exist
(New oxenstored can run in an environment with only V1 of the plugin).
The plugin is not switched to as of yet, the old Xenctrl stubs are still
used.
Signed-off-by: Andrii Sultanov <andrii.sultanov@cloud.com>
Acked-by: Christian Lindig <christian.lindig@cloud.com>
Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
The root .gitignore is quite stale from recent (and less recent) removals, but
also fails to work for the forthcoming dynamic plugin work.
Strip all Ocaml content out of the root .gitignore, and provide a more local
.gitignore's with up-to-date patterns.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Acked-by: Christian Lindig <christian.lindig@cloud.com>
Fixes warnings such as:
File "config.ml", line 102, characters 12-27:
102 | | Failure "int_of_string" -> append (k, "expect int arg")
^^^^^^^^^^^^^^^
Warning 52: Code should not depend on the actual values of
this constructor's arguments. They are only for information
and may change in future versions. (See manual section 9.5)
Do not rely on the string values of the `Failure` exception, but use the
`_opt` functions instead.
Signed-off-by: Edwin Török <edwin.torok@cloud.com>
Acked-by: Christian Lindig <christian.lindig@cloud.com>
Tested-by: Andrew Cooper <andrew.cooper3@citrix.com>
Now that we no longer have a hashtable inside we can make Quota.t pure, and
push the mutable update to its callers. Store.t already had a mutable Quota.t
field.
No functional change.
Signed-off-by: Edwin Török <edwin.torok@cloud.com>
Acked-by: Christian Lindig <christian.lindig@cloud.com>
On a stress test running 1000 VMs flamegraphs have shown that
`oxenstored` spends a large amount of time in `Hashtbl.copy` and the GC.
Hashtable complexity:
* read/write: O(1) average
* copy: O(domains) -- copying the entire table
Map complexity:
* read/write: O(log n) worst case
* copy: O(1) -- a word copy
We always perform at least one 'copy' when processing each xenstore
packet (regardless whether it is a readonly operation or inside a
transaction or not), so the actual complexity per packet is:
* Hashtbl: O(domains)
* Map: O(log domains)
Maps are the clear winner, and a better fit for the immutable xenstore
tree.
Signed-off-by: Edwin Török <edwin.torok@cloud.com>
Acked-by: Christian Lindig <christian.lindig@cloud.com>
Char.lowercase got removed in OCaml 5.0 (it has been deprecated since 2014),
and doesn't build any more.
Char.lowercase_ascii has existed since OCaml 4.03, so that is the new
minimum version for oxenstored.
However, OCaml 4.05 is the oldest new-enough version found in common distros,
so pick this as a baseline.
Signed-off-by: Edwin Török <edwin.torok@cloud.com>
Acked-by: Christian Lindig <christian.lindig@cloud.com>
Acked-by: Anthony PERARD <anthony.perard@citrix.com>
[Update CHANGELOG.md]
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
The configuration file can contain typos or various errors that could prevent
live update from succeeding (e.g. a flag only valid on a different version).
Unknown entries in the config file would be ignored on startup normally,
add a strict --config-test that live-update can use to check that the config file
is valid *for the new binary*.
For compatibility with running old code during live update recognize
--live --help as an equivalent to --config-test.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
The manually established link order is fragile to code changes. Use ocamldep
to calculate the appropriate link order.
No functional change.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
fallback_exception_handler feeds a string with embedded newlines directly into
syslog(). While this is an improvement on getting nothing, syslogd escapes
all control characters it gets, and emits one (long) log line.
Fix the problem generally in the syslog stub. As we already have a local copy
of the string, split it in place and emit one syslog() call per line.
Also tweak Logging.msg_of to avoid putting an extra newline on a string which
already ends with one.
Fixes: ee7815f49f ("tools/oxenstored: Set uncaught exception handler")
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
strdup() may return NULL. Check for this before passing to syslog().
Drop const from c_msg. It is bogus, as demonstrated by the need to cast to
void * in order to free the memory.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Unhandled exceptions go to stderr by default, but this doesn't typically work
for oxenstored because:
* daemonize reopens stderr as /dev/null
* systemd redirects stderr to /dev/null too
Debugging an unhandled exception requires reproducing the issue locally when
using --no-fork, and is not conducive to figuring out what went wrong on a
remote system.
Install a custom handler which also tries to render the backtrace to the
configured syslog facility, and DAEMON|ERR otherwise.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
During live update, oxenstored tries a best effort approach to recover as many
domains and information as possible even if it encounters errors restoring
some domains.
However, logging about misunderstood input is more severe than simply info.
Log it at warning instead.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Closing the evtchn handle will unbind and free all local ports. The new
xenstored would need to rebind all evtchns, which is work that we don't want
or need to be doing during the critical handover period.
However, it turns out that the Windows PV drivers also rebind their local port
too across suspend/resume, leaving (o)xenstored with a stale idea of the
remote port to use. In this case, reusing the established connection is the
only robust option.
Therefore:
* Have oxenstored open /dev/xen/evtchn without CLOEXEC at start of day.
* Extend the handover information with the evtchn fd, domexc virq local port,
and the local port number for each domain connection.
* Have (the new) oxenstored recover the open handle using Xeneventchn.fdopen,
and use the provided local ports rather than trying to rebind them.
When this new information isn't present (i.e. live updating from an oxenstored
prior to this change), the best-effort status quo will have to do.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Inter-domain event channels are always a pair of local and remote ports.
Right now the handling is asymmetric, caused by the fact that the evtchn is
bound after the associated Domain object is constructed.
First, move binding of the event channel into the Domain.make() constructor.
This means the local port no longer needs to be an option. It also removes
the final callers of Domain.bind_interdomain.
Next, introduce a new port_pair type to encapsulate the fact that these two
should be updated together, and replace the previous port and remote_port
fields. This refactoring also changes the Domain.get_port interface (removing
an option) so take the opportunity to name it get_local_port instead.
Also, this fixes a use-after-free risk with Domain.close. Once the evtchn has
been unbound, the same local port number can be reused for a different
purpose, so explicitly invalidate the ports to prevent their accidental misuse
in the future.
This also cleans up some of the debugging, to always print a port pair.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Reviewed-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Generally speaking, the event channel local/remote port is fixed for the
lifetime of the associated domain object. The exception to this is a
secondary XS_INTRODUCE (defined to re-bind to a new event channel) which pokes
around at the domain object's internal state.
We need to refactor the evtchn handling to support live update, so start by
moving the relevant manipulation into Domain.
No practical change.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Reviewed-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
This will make the logic clearer when we plumb local_port through these
functions.
While doing this, rearrange the construct in Domains.create0 to separate the
remote port handling from the interface handling. (The interface logic is
dubious in several ways, but not altered by this cleanup.)
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Reviewed-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Xenstored always needs to bind the DOM_EXC VIRQ.
Instead of doing it shortly after the call to Event.init(), do it in the
constructor directly. This removes the need for the field to be a mutable
option.
It will also simplify a future change to support live update. Rename the
field from virq_port (which could be any VIRQ) to it's proper name.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Reviewed-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
This file has some style problems so severe that they interfere with the
readability of the subsequent bugfix patches.
Fix these issues ahead of time, to make the subsequent changes more readable.
No functional change.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Reviewed-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
A debug statement got inserted into a single-expression if statement.
Insert brackets to give the intended meaning, rather than the actual meaning
where the "let con = Connections..." is outside and executed unconditionally.
This results in some unnecessary ring checks for domains which otherwise have
IO credit.
Fixes: 42f0581a91 ("tools/oxenstored: Implement live update for socket connections")
Reported-by: Edwin Török <edvin.torok@citrix.com>
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Building with Dune in release mode fails with:
```
File "ocaml/xenstored/store.ml", line 464, characters 13-32:
Warning 18: this type-based record disambiguation is not principal.
File "ocaml/xenstored/store.ml", line 1:
Error: Some fatal warnings were triggered (1 occurrences)
```
This is a warning to help keep the code futureproof, quoting from its
documentation:
> Check information path during type-checking, to make sure that all types are
> derived in a principal way. When using labelled arguments and/or polymorphic
> methods, this flag is required to ensure future versions of the compiler will
> be able to infer types correctly, even if internal algorithms change. All
> programs accepted in -principal mode are also accepted in the default mode with
> equivalent types, but different binary signatures, and this may slow down type
> checking; yet it is a good idea to use it once before publishing source code.
Fixes: db471408ed "tools/ocaml/xenstored: Fix quota bypass on domain shutdown"
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Release-acked-by: Henry Wang <Henry.Wang@arm.com>
Integers in Ocaml have 63 or 31 bits of signed precision.
On 64-bit builds of Ocaml, this is fine because a C uint32_t always fits
within a 63-bit signed integer.
In 32-bit builds of Ocaml, this goes wrong. The C uint32_t is truncated
first (loses the top bit), then has a unsigned/signed mismatch.
A "negative" value (i.e. a packet on the ring of between 1G and 2G in size)
will trigger an exception later in Bytes.make in xb.ml, and because the packet
is not removed from the ring, the exception re-triggers on every subsequent
query, creating a livelock.
Fix both the source of the exception in Xb, and as defence in depth, mark the
domain as bad for any Invalid_argument exceptions to avoid the risk of
livelock.
This is XSA-420 / CVE-2022-42324.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
XSA-322 fixed a domid reuse vulnerability by assigning Dom0 as the owner of
any nodes left after a domain is shutdown (e.g. outside its /local/domain/N
tree).
However Dom0 has no quota on purpose, so this opened up another potential
attack vector. Avoid it by deleting these nodes instead of assigning them to
Dom0.
This is part of XSA-419 / CVE-2022-42323.
Fixes: c46eff9212 ("tools/ocaml/xenstored: clean up permissions for dead domains")
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Introduce a limit on the number of outstanding reply packets in the xenbus
queue. This limits the number of in-flight requests: when the output queue is
full we'll stop processing inputs until the output queue has room again.
To avoid a busy loop on the Unix socket we only add it to the watched input
file descriptor set if we'd be able to call `input` on it. Even though Dom0
is trusted and exempt from quotas a flood of events might cause a backlog
where events are produced faster than daemons in Dom0 can consume them, which
could lead to an unbounded queue size and OOM.
Therefore the xenbus queue limit must apply to all connections, Dom0 is not
exempt from it, although if everything works correctly it will eventually
catch up.
This prevents a malicious guest from sending more commands while it has
outstanding watch events or command replies in its input ring. However if it
can cause the generation of watch events by other means (e.g. by Dom0, or
another cooperative guest) and stop reading its own ring then watch events
would've queued up without limit.
The xenstore protocol doesn't have a back-pressure mechanism, and doesn't
allow dropping watch events. In fact, dropping watch events is known to break
some pieces of normal functionality. This leaves little choice to safely
implement the xenstore protocol without exposing the xenstore daemon to
out-of-memory attacks.
Implement the fix as pipes with bounded buffers:
* Use a bounded buffer for watch events
* The watch structure will have a bounded receiving pipe of watch events
* The source will have an "overflow" pipe of pending watch events it couldn't
deliver
Items are queued up on one end and are sent as far along the pipe as possible:
source domain -> watch -> xenbus of target -> xenstore ring/socket of target
If the pipe is "full" at any point then back-pressure is applied and we prevent
more items from being queued up. For the source domain this means that we'll
stop accepting new commands as long as its pipe buffer is not empty.
Before we try to enqueue an item we first check whether it is possible to send
it further down the pipe, by attempting to recursively flush the pipes. This
ensures that we retain the order of events as much as possible.
We might break causality of watch events if the target domain's queue is full
and we need to start using the watch's queue. This is a breaking change in
the xenstore protocol, but only for domains which are not processing their
incoming ring as expected.
When a watch is deleted its entire pending queue is dropped (no code is needed
for that, because it is part of the 'watch' type).
There is a cache of watches that have pending events that we attempt to flush
at every cycle if possible.
Introduce 3 limits here:
* quota-maxwatchevents on watch event destination: when this is hit the
source will not be allowed to queue up more watch events.
* quota-maxoustanding which is the number of responses not read from the ring:
once exceeded, no more inputs are processed until all outstanding replies
are consumed by the client.
* overflow queue on the watch event source: all watches that cannot be stored
on destination are queued up here, a single command can trigger multiple
watches (e.g. due to recursion).
The overflow queue currently doesn't have an upper bound, it is difficult to
accurately calculate one as it depends on whether you are Dom0 and how many
watches each path has registered and how many watch events you can trigger
with a single command (e.g. a commit). However these events were already
using memory, this just moves them elsewhere, and as long as we correctly
block a domain it shouldn't result in unbounded memory usage.
Note that Dom0 is not excluded from these checks, it is important that Dom0 is
especially not excluded when it is the source, since there are many ways in
which a guest could trigger Dom0 to send it watch events.
This should protect against malicious frontends as long as the backend follows
the PV xenstore protocol and only exposes paths needed by the frontend, and
changes those paths at most once as a reaction to guest events, or protocol
state.
The queue limits are per watch, and per domain-pair, so even if one
communication channel would be "blocked", others would keep working, and the
domain itself won't get blocked as long as it doesn't overflow the queue of
watch events.
Similarly a malicious backend could cause the frontend to get blocked, but
this watch queue protects the frontend as well as long as it follows the PV
protocol. (Although note that protection against malicious backends is only a
best effort at the moment)
This is part of XSA-326 / CVE-2022-42318.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
The queue here would only ever hold at most one element. This will simplify
follow-up patches.
This is part of XSA-326.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
By default the OCaml garbage collector would return memory to the OS only
after unused memory is 5x live memory. Tweak this to 120% instead, which
would match the major GC speed.
This is part of XSA-326.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Previously we'd perform the operation, record the updated tree in the
transaction record, then try to insert a watchop path and the reply packet.
If we exceeded max requests we would've returned EQUOTA, but still:
* have performed the operation on the transaction's tree
* have recorded the watchop, making this queue effectively unbounded
It is better if we check whether we'd have room to store the operation before
performing the transaction, and raise EQUOTA there. Then the transaction
record won't grow.
This is part of XSA-326 / CVE-2022-42317.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
We currently have 2 different set of defaults in upstream Xen git tree:
* defined in the source code, only used if there is no config file
* defined in the oxenstored.conf.in upstream Xen
An oxenstored.conf file is not mandatory, and if missing, maxrequests in
particular has an unsafe default.
Resync the defaults from oxenstored.conf.in into the source code.
This is part of XSA-326 / CVE-2022-42316.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
During live update we will load the /tool/xenstored path from the previous binary,
and then try to mkdir /tool again which will fail with EEXIST.
Check for existence of the path before creating it.
The write call to /tool/xenstored should not need any changes
(and we do want to overwrite any previous path, in case it changed).
Prior to 7110192b1d live update would work only if the binary path was
specified, and with 7110192b1d and this live update also works when
no binary path is specified in `xenstore-control live-update`.
Fixes: 7110192b1d ("tools/oxenstored: Fix Oxenstored Live Update")
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Release-acked-by: Henry Wang <Henry.Wang@arm.com>
Hiding the type will make it easier to change the implementation
in the future without breaking code that relies on it.
No functional change.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Fix compiler warning about:
* unused value
* ambiguous documentation comment
* non-principal type inference (compiler version dependent)
No functional change.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
paths.ml contains various paths known to configure, and currently is generated
via a Makefile rule. Simplify this and generate it through configure, similar
to how oxenstored.conf is generated from oxenstored.conf.in.
This will allow to reuse the generated file more easily with Dune.
No functional change.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Due to how set_write_lowpath was used here it didn't detect create/delete
conflicts. When we create an entry we must mark our parent as modified
(this is what creating a new node via write does).
Otherwise we can have 2 transactions one creating, and another deleting a node
both succeeding depending on timing. Or one transaction reading an entry,
concluding it doesn't exist, do some other work based on that information and
successfully commit even if another transaction creates the node via mkdir
meanwhile.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Release-Acked-by: Ian Jackson <iwj@xenproject.org>
Watches on invalid paths were accepted, but they would never trigger. The
client also got no notification that its watch is bad and would never trigger.
Found again by the structured fuzzer, due to an error on live update reload:
the invalid watch paths would get rejected during live update and the list of
watches would be different pre/post live update.
The testcase is watch on `//`, which is an invalid path.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Release-Acked-by: Ian Jackson <iwj@xenproject.org>
We increment the domain's quota on mkdir even when the node already exists.
This results in a quota inconsistency after live update, where reconstructing
the tree from scratch results in a different quota.
Not a security issue because the domain uses up quota faster, so it will only
get a Quota error sooner than it should.
Found by the structured fuzzer.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Release-Acked-by: Ian Jackson <iwj@xenproject.org>
This changes the output of xenstore-ls to be sorted. Previously the keys were
listed in the order in which they were inserted in. docs/misc/xenstore.txt
doesn't specify in what order keys are listed.
Map.update is used to retain semantics with replace_child: only an existing
child is replaced, if it wasn't part of the original map we don't add it.
Similarly exception behaviour is retained for del_childname and related
functions.
Entries are stored in reverse sort order, so that upon Map.fold the
constructed list is sorted in ascending order and there is no need for a
List.rev.
This changes the semantics and is not suitable as is for a backport. It
reveals bugs in buggy clients that depend on xenstore entry order, however
those clients should be fixed.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
We are currently on OCaml 4.02 as minimum version. To make the followup
optimizations compile backport these functions from OCaml 4.06.
This implementation is less efficient than the one in the 4.06 standard
library which has access to the internals of the Map.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
The code here is attempting to reduce memory usage by sharing common
substrings in the tree: it replaces strings with ints, and keeps a string->int
map that gets manually garbage collected using a hand-rolled mark and sweep
algorithm.
This is unnecessary: OCaml already has a mark-and-sweep Garbage Collector
runtime, and sharing of common strings in tree nodes can be achieved through
Weak references: if the string hasn't been seen yet it gets added to the Weak
reference table, and if it has we use the entry from the table instead, thus
storing a string only once. When the string is no longer referenced OCaml's
GC will drop it from the weak table: there is no need to manually do a
mark-and-sweep, or to tell OCaml when to drop it.
Signed-off-by: Edwin Török <edvin.torok@citrix.com>
Acked-by: Christian Lindig <christian.lindig@citrix.com>
Andrii Sultanov