hw/i386/kvm/xenstore_impl.c

   1 /*
   2  * QEMU Xen emulation: The actual implementation of XenStore
   3  *
   4  * Copyright © 2023 Amazon.com, Inc. or its affiliates. All Rights Reserved.
   5  *
   6  * Authors: David Woodhouse <dwmw2@infradead.org>, Paul Durrant <paul@xen.org>
   7  *
   8  * This work is licensed under the terms of the GNU GPL, version 2 or later.
   9  * See the COPYING file in the top-level directory.
  10  */
  11
  12 #include "qemu/osdep.h"
  13 #include "qom/object.h"
  14
  15 #include "xen_xenstore.h"
  16 #include "xenstore_impl.h"
  17
  18 #include "hw/xen/interface/io/xs_wire.h"
  19
  20 #define XS_MAX_WATCHES          128
  21 #define XS_MAX_DOMAIN_NODES     1000
  22 #define XS_MAX_NODE_SIZE        2048
  23 #define XS_MAX_TRANSACTIONS     10
  24 #define XS_MAX_PERMS_PER_NODE   5
  25
  26 #define XS_VALID_CHARS "abcdefghijklmnopqrstuvwxyz" \
  27                        "ABCDEFGHIJKLMNOPQRSTUVWXYZ" \
  28                        "0123456789-/_"
  29
  30 typedef struct XsNode {
  31     uint32_t ref;
  32     GByteArray *content;
  33     GHashTable *children;
  34     uint64_t gencnt;
  35     bool deleted_in_tx;
  36     bool modified_in_tx;
  37 #ifdef XS_NODE_UNIT_TEST
  38     gchar *name; /* debug only */
  39 #endif
  40 } XsNode;
  41
  42 typedef struct XsWatch {
  43     struct XsWatch *next;
  44     xs_impl_watch_fn *cb;
  45     void *cb_opaque;
  46     char *token;
  47     unsigned int dom_id;
  48     int rel_prefix;
  49 } XsWatch;
  50
  51 typedef struct XsTransaction {
  52     XsNode *root;
  53     unsigned int nr_nodes;
  54     unsigned int base_tx;
  55     unsigned int tx_id;
  56     unsigned int dom_id;
  57 } XsTransaction;
  58
  59 struct XenstoreImplState {
  60     XsNode *root;
  61     unsigned int nr_nodes;
  62     GHashTable *watches;
  63     unsigned int nr_domu_watches;
  64     GHashTable *transactions;
  65     unsigned int nr_domu_transactions;
  66     unsigned int root_tx;
  67     unsigned int last_tx;
  68 };
  69
  70
  71 static void nobble_tx(gpointer key, gpointer value, gpointer user_data)
  72 {
  73     unsigned int *new_tx_id = user_data;
  74     XsTransaction *tx = value;
  75
  76     if (tx->base_tx == *new_tx_id) {
  77         /* Transactions based on XBT_NULL will always fail */
  78         tx->base_tx = XBT_NULL;
  79     }
  80 }
  81
  82 static inline unsigned int next_tx(struct XenstoreImplState *s)
  83 {
  84     unsigned int tx_id;
  85
  86     /* Find the next TX id which isn't either XBT_NULL or in use. */
  87     do {
  88         tx_id = ++s->last_tx;
  89     } while (tx_id == XBT_NULL || tx_id == s->root_tx ||
  90              g_hash_table_lookup(s->transactions, GINT_TO_POINTER(tx_id)));
  91
  92     /*
  93      * It is vanishingly unlikely, but ensure that no outstanding transaction
  94      * is based on the (previous incarnation of the) newly-allocated TX id.
  95      */
  96     g_hash_table_foreach(s->transactions, nobble_tx, &tx_id);
  97
  98     return tx_id;
  99 }
 100
 101 static inline XsNode *xs_node_new(void)
 102 {
 103     XsNode *n = g_new0(XsNode, 1);
 104     n->ref = 1;
 105
 106 #ifdef XS_NODE_UNIT_TEST
 107     nr_xs_nodes++;
 108     xs_node_list = g_list_prepend(xs_node_list, n);
 109 #endif
 110     return n;
 111 }
 112
 113 static inline XsNode *xs_node_ref(XsNode *n)
 114 {
 115     /* With just 10 transactions, it can never get anywhere near this. */
 116     g_assert(n->ref < INT_MAX);
 117
 118     g_assert(n->ref);
 119     n->ref++;
 120     return n;
 121 }
 122
 123 static inline void xs_node_unref(XsNode *n)
 124 {
 125     if (!n) {
 126         return;
 127     }
 128     g_assert(n->ref);
 129     if (--n->ref) {
 130         return;
 131     }
 132
 133     if (n->content) {
 134         g_byte_array_unref(n->content);
 135     }
 136     if (n->children) {
 137         g_hash_table_unref(n->children);
 138     }
 139 #ifdef XS_NODE_UNIT_TEST
 140     g_free(n->name);
 141     nr_xs_nodes--;
 142     xs_node_list = g_list_remove(xs_node_list, n);
 143 #endif
 144     g_free(n);
 145 }
 146
 147 /* For copying from one hash table to another using g_hash_table_foreach() */
 148 static void do_insert(gpointer key, gpointer value, gpointer user_data)
 149 {
 150     g_hash_table_insert(user_data, g_strdup(key), xs_node_ref(value));
 151 }
 152
 153 static XsNode *xs_node_copy(XsNode *old)
 154 {
 155     XsNode *n = xs_node_new();
 156
 157     n->gencnt = old->gencnt;
 158
 159 #ifdef XS_NODE_UNIT_TEST
 160     if (n->name) {
 161         n->name = g_strdup(old->name);
 162     }
 163 #endif
 164
 165     if (old->children) {
 166         n->children = g_hash_table_new_full(g_str_hash, g_str_equal, g_free,
 167                                             (GDestroyNotify)xs_node_unref);
 168         g_hash_table_foreach(old->children, do_insert, n->children);
 169     }
 170     if (old && old->content) {
 171         n->content = g_byte_array_ref(old->content);
 172     }
 173     return n;
 174 }
 175
 176 /* Returns true if it made a change to the hash table */
 177 static bool xs_node_add_child(XsNode *n, const char *path_elem, XsNode *child)
 178 {
 179     assert(!strchr(path_elem, '/'));
 180
 181     if (!child) {
 182         assert(n->children);
 183         return g_hash_table_remove(n->children, path_elem);
 184     }
 185
 186 #ifdef XS_NODE_UNIT_TEST
 187     g_free(child->name);
 188     child->name = g_strdup(path_elem);
 189 #endif
 190     if (!n->children) {
 191         n->children = g_hash_table_new_full(g_str_hash, g_str_equal, g_free,
 192                                             (GDestroyNotify)xs_node_unref);
 193     }
 194
 195     /*
 196      * The documentation for g_hash_table_insert() says that it "returns a
 197      * boolean value to indicate whether the newly added value was already
 198      * in the hash table or not."
 199      *
 200      * It could perhaps be clearer that returning TRUE means it wasn't,
 201      */
 202     return g_hash_table_insert(n->children, g_strdup(path_elem), child);
 203 }
 204
 205 struct walk_op {
 206     struct XenstoreImplState *s;
 207     char path[XENSTORE_ABS_PATH_MAX + 2]; /* Two NUL terminators */
 208     int (*op_fn)(XsNode **n, struct walk_op *op);
 209     void *op_opaque;
 210     void *op_opaque2;
 211
 212     GList *watches;
 213     unsigned int dom_id;
 214     unsigned int tx_id;
 215
 216     /* The number of nodes which will exist in the tree if this op succeeds. */
 217     unsigned int new_nr_nodes;
 218
 219     /*
 220      * This is maintained on the way *down* the walk to indicate
 221      * whether nodes can be modified in place or whether COW is
 222      * required. It starts off being true, as we're always going to
 223      * replace the root node. If we walk into a shared subtree it
 224      * becomes false. If we start *creating* new nodes for a write,
 225      * it becomes true again.
 226      *
 227      * Do not use it on the way back up.
 228      */
 229     bool inplace;
 230     bool mutating;
 231     bool create_dirs;
 232     bool in_transaction;
 233
 234     /* Tracking during recursion so we know which is first. */
 235     bool deleted_in_tx;
 236 };
 237
 238 static void fire_watches(struct walk_op *op, bool parents)
 239 {
 240     GList *l = NULL;
 241     XsWatch *w;
 242
 243     if (!op->mutating || op->in_transaction) {
 244         return;
 245     }
 246
 247     if (parents) {
 248         l = op->watches;
 249     }
 250
 251     w = g_hash_table_lookup(op->s->watches, op->path);
 252     while (w || l) {
 253         if (!w) {
 254             /* Fire the parent nodes from 'op' if asked to */
 255             w = l->data;
 256             l = l->next;
 257             continue;
 258         }
 259
 260         assert(strlen(op->path) > w->rel_prefix);
 261         w->cb(w->cb_opaque, op->path + w->rel_prefix, w->token);
 262
 263         w = w->next;
 264     }
 265 }
 266
 267 static int xs_node_add_content(XsNode **n, struct walk_op *op)
 268 {
 269     GByteArray *data = op->op_opaque;
 270
 271     if (op->dom_id) {
 272         /*
 273          * The real XenStored includes permissions and names of child nodes
 274          * in the calculated datasize but life's too short. For a single
 275          * tenant internal XenStore, we don't have to be quite as pedantic.
 276          */
 277         if (data->len > XS_MAX_NODE_SIZE) {
 278             return E2BIG;
 279         }
 280     }
 281     /* We *are* the node to be written. Either this or a copy. */
 282     if (!op->inplace) {
 283         XsNode *old = *n;
 284         *n = xs_node_copy(old);
 285         xs_node_unref(old);
 286     }
 287
 288     if ((*n)->content) {
 289         g_byte_array_unref((*n)->content);
 290     }
 291     (*n)->content = g_byte_array_ref(data);
 292     if (op->tx_id != XBT_NULL) {
 293         (*n)->modified_in_tx = true;
 294     }
 295     return 0;
 296 }
 297
 298 static int xs_node_get_content(XsNode **n, struct walk_op *op)
 299 {
 300     GByteArray *data = op->op_opaque;
 301     GByteArray *node_data;
 302
 303     assert(op->inplace);
 304     assert(*n);
 305
 306     node_data = (*n)->content;
 307     if (node_data) {
 308         g_byte_array_append(data, node_data->data, node_data->len);
 309     }
 310
 311     return 0;
 312 }
 313
 314 static int node_rm_recurse(gpointer key, gpointer value, gpointer user_data)
 315 {
 316     struct walk_op *op = user_data;
 317     int path_len = strlen(op->path);
 318     int key_len = strlen(key);
 319     XsNode *n = value;
 320     bool this_inplace = op->inplace;
 321
 322     if (n->ref != 1) {
 323         op->inplace = 0;
 324     }
 325
 326     assert(key_len + path_len + 2 <= sizeof(op->path));
 327     op->path[path_len] = '/';
 328     memcpy(op->path + path_len + 1, key, key_len + 1);
 329
 330     if (n->children) {
 331         g_hash_table_foreach_remove(n->children, node_rm_recurse, op);
 332     }
 333     op->new_nr_nodes--;
 334
 335     /*
 336      * Fire watches on *this* node but not the parents because they are
 337      * going to be deleted too, so the watch will fire for them anyway.
 338      */
 339     fire_watches(op, false);
 340     op->path[path_len] = '\0';
 341
 342     /*
 343      * Actually deleting the child here is just an optimisation; if we
 344      * don't then the final unref on the topmost victim will just have
 345      * to cascade down again repeating all the g_hash_table_foreach()
 346      * calls.
 347      */
 348     return this_inplace;
 349 }
 350
 351 static XsNode *xs_node_copy_deleted(XsNode *old, struct walk_op *op);
 352 static void copy_deleted_recurse(gpointer key, gpointer value,
 353                                  gpointer user_data)
 354 {
 355     struct walk_op *op = user_data;
 356     GHashTable *siblings = op->op_opaque2;
 357     XsNode *n = xs_node_copy_deleted(value, op);
 358
 359     /*
 360      * Reinsert the deleted_in_tx copy of the node into the parent's
 361      * 'children' hash table. Having stashed it from op->op_opaque2
 362      * before the recursive call to xs_node_copy_deleted() scribbled
 363      * over it.
 364      */
 365     g_hash_table_insert(siblings, g_strdup(key), n);
 366 }
 367
 368 static XsNode *xs_node_copy_deleted(XsNode *old, struct walk_op *op)
 369 {
 370     XsNode *n = xs_node_new();
 371
 372     n->gencnt = old->gencnt;
 373
 374 #ifdef XS_NODE_UNIT_TEST
 375     if (old->name) {
 376         n->name = g_strdup(old->name);
 377     }
 378 #endif
 379
 380     if (old->children) {
 381         n->children = g_hash_table_new_full(g_str_hash, g_str_equal, g_free,
 382                                             (GDestroyNotify)xs_node_unref);
 383         op->op_opaque2 = n->children;
 384         g_hash_table_foreach(old->children, copy_deleted_recurse, op);
 385     }
 386     n->deleted_in_tx = true;
 387     /* If it gets resurrected we only fire a watch if it lost its content */
 388     if (old->content) {
 389         n->modified_in_tx = true;
 390     }
 391     op->new_nr_nodes--;
 392     return n;
 393 }
 394
 395 static int xs_node_rm(XsNode **n, struct walk_op *op)
 396 {
 397     bool this_inplace = op->inplace;
 398
 399     if (op->tx_id != XBT_NULL) {
 400         /* It's not trivial to do inplace handling for this one */
 401         XsNode *old = *n;
 402         *n = xs_node_copy_deleted(old, op);
 403         xs_node_unref(old);
 404         return 0;
 405     }
 406
 407     /* Fire watches for, and count, nodes in the subtree which get deleted */
 408     if ((*n)->children) {
 409         g_hash_table_foreach_remove((*n)->children, node_rm_recurse, op);
 410     }
 411     op->new_nr_nodes--;
 412
 413     if (this_inplace) {
 414         xs_node_unref(*n);
 415     }
 416     *n = NULL;
 417     return 0;
 418 }
 419
 420 /*
 421  * Passed a full reference in *n which it may free if it needs to COW.
 422  *
 423  * When changing the tree, the op->inplace flag indicates whether this
 424  * node may be modified in place (i.e. it and all its parents had a
 425  * refcount of one). If walking down the tree we find a node whose
 426  * refcount is higher, we must clear op->inplace and COW from there
 427  * down. Unless we are creating new nodes as scaffolding for a write
 428  * (which works like 'mkdir -p' does). In which case those newly
 429  * created nodes can (and must) be modified in place again.
 430  */
 431 static int xs_node_walk(XsNode **n, struct walk_op *op)
 432 {
 433     char *child_name = NULL;
 434     size_t namelen;
 435     XsNode *old = *n, *child = NULL;
 436     bool stole_child = false;
 437     bool this_inplace;
 438     XsWatch *watch;
 439     int err;
 440
 441     namelen = strlen(op->path);
 442     watch = g_hash_table_lookup(op->s->watches, op->path);
 443
 444     /* Is there a child, or do we hit the double-NUL termination? */
 445     if (op->path[namelen + 1]) {
 446         char *slash;
 447         child_name = op->path + namelen + 1;
 448         slash = strchr(child_name, '/');
 449         if (slash) {
 450             *slash = '\0';
 451         }
 452         op->path[namelen] = '/';
 453     }
 454
 455     /* If we walk into a subtree which is shared, we must COW */
 456     if (op->mutating && old->ref != 1) {
 457         op->inplace = false;
 458     }
 459
 460     if (!child_name) {
 461         /* This is the actual node on which the operation shall be performed */
 462         err = op->op_fn(n, op);
 463         if (!err) {
 464             fire_watches(op, true);
 465         }
 466         goto out;
 467     }
 468
 469     /* op->inplace will be further modified during the recursion */
 470     this_inplace = op->inplace;
 471
 472     if (old && old->children) {
 473         child = g_hash_table_lookup(old->children, child_name);
 474         /* This is a *weak* reference to 'child', owned by the hash table */
 475     }
 476
 477     if (child) {
 478         if (child->deleted_in_tx) {
 479             assert(child->ref == 1);
 480             /* Cannot actually set child->deleted_in_tx = false until later */
 481         }
 482         xs_node_ref(child);
 483         /*
 484          * Now we own it too. But if we can modify inplace, that's going to
 485          * foil the check and force it to COW. We want to be the *only* owner
 486          * so that it can be modified in place, so remove it from the hash
 487          * table in that case. We'll add it (or its replacement) back later.
 488          */
 489         if (op->mutating && this_inplace) {
 490             g_hash_table_remove(old->children, child_name);
 491             stole_child = true;
 492         }
 493     } else if (op->create_dirs) {
 494         if (op->dom_id && op->new_nr_nodes >= XS_MAX_DOMAIN_NODES) {
 495             err = ENOSPC;
 496             goto out;
 497         }
 498         op->new_nr_nodes++;
 499         child = xs_node_new();
 500
 501         /*
 502          * If we're creating a new child, we can clearly modify it (and its
 503          * children) in place from here on down.
 504          */
 505         op->inplace = true;
 506     } else {
 507         err = ENOENT;
 508         goto out;
 509     }
 510
 511     /*
 512      * If there's a watch on this node, add it to the list to be fired
 513      * (with the correct full pathname for the modified node) at the end.
 514      */
 515     if (watch) {
 516         op->watches = g_list_append(op->watches, watch);
 517     }
 518
 519     /*
 520      * Except for the temporary child-stealing as noted, our node has not
 521      * changed yet. We don't yet know the overall operation will complete.
 522      */
 523     err = xs_node_walk(&child, op);
 524
 525     if (watch) {
 526         op->watches = g_list_remove(op->watches, watch);
 527     }
 528
 529     if (err || !op->mutating) {
 530         if (stole_child) {
 531             /* Put it back as it was. */
 532             g_hash_table_replace(old->children, g_strdup(child_name), child);
 533         } else {
 534             xs_node_unref(child);
 535         }
 536         goto out;
 537     }
 538
 539     /*
 540      * Now we know the operation has completed successfully and we're on
 541      * the way back up. Make the change, substituting 'child' in the
 542      * node at our level.
 543      */
 544     if (!this_inplace) {
 545         *n = xs_node_copy(old);
 546         xs_node_unref(old);
 547     }
 548
 549     /*
 550      * If we resurrected a deleted_in_tx node, we can mark it as no longer
 551      * deleted now that we know the overall operation has succeeded.
 552      */
 553     if (op->create_dirs && child && child->deleted_in_tx) {
 554         op->new_nr_nodes++;
 555         child->deleted_in_tx = false;
 556     }
 557
 558     /*
 559      * The child may be NULL here, for a remove operation. Either way,
 560      * xs_node_add_child() will do the right thing and return a value
 561      * indicating whether it changed the parent's hash table or not.
 562      *
 563      * We bump the parent gencnt if it adds a child that we *didn't*
 564      * steal from it in the first place, or if child==NULL and was
 565      * thus removed (whether we stole it earlier and didn't put it
 566      * back, or xs_node_add_child() actually removed it now).
 567      */
 568     if ((xs_node_add_child(*n, child_name, child) && !stole_child) || !child) {
 569         (*n)->gencnt++;
 570     }
 571
 572  out:
 573     op->path[namelen] = '\0';
 574     if (!namelen) {
 575         assert(!op->watches);
 576         /*
 577          * On completing the recursion back up the path walk and reaching the
 578          * top, assign the new node count if the operation was successful. If
 579          * the main tree was changed, bump its tx ID so that outstanding
 580          * transactions correctly fail. But don't bump it every time; only
 581          * if it makes a difference.
 582          */
 583         if (!err && op->mutating) {
 584             if (!op->in_transaction) {
 585                 if (op->s->root_tx != op->s->last_tx) {
 586                     op->s->root_tx = next_tx(op->s);
 587                 }
 588                 op->s->nr_nodes = op->new_nr_nodes;
 589             } else {
 590                 XsTransaction *tx = g_hash_table_lookup(op->s->transactions,
 591                                                         GINT_TO_POINTER(op->tx_id));
 592                 assert(tx);
 593                 tx->nr_nodes = op->new_nr_nodes;
 594             }
 595         }
 596     }
 597     return err;
 598 }
 599
 600 static void append_directory_item(gpointer key, gpointer value,
 601                                   gpointer user_data)
 602 {
 603     GList **items = user_data;
 604
 605     *items = g_list_insert_sorted(*items, g_strdup(key), (GCompareFunc)strcmp);
 606 }
 607
 608 /* Populates items with char * names which caller must free. */
 609 static int xs_node_directory(XsNode **n, struct walk_op *op)
 610 {
 611     GList **items = op->op_opaque;
 612
 613     assert(op->inplace);
 614     assert(*n);
 615
 616     if ((*n)->children) {
 617         g_hash_table_foreach((*n)->children, append_directory_item, items);
 618     }
 619
 620     if (op->op_opaque2) {
 621         *(uint64_t *)op->op_opaque2 = (*n)->gencnt;
 622     }
 623
 624     return 0;
 625 }
 626
 627 static int validate_path(char *outpath, const char *userpath,
 628                          unsigned int dom_id)
 629 {
 630     size_t i, pathlen = strlen(userpath);
 631
 632     if (!pathlen || userpath[pathlen] == '/' || strstr(userpath, "//")) {
 633         return EINVAL;
 634     }
 635     for (i = 0; i < pathlen; i++) {
 636         if (!strchr(XS_VALID_CHARS, userpath[i])) {
 637             return EINVAL;
 638         }
 639     }
 640     if (userpath[0] == '/') {
 641         if (pathlen > XENSTORE_ABS_PATH_MAX) {
 642             return E2BIG;
 643         }
 644         memcpy(outpath, userpath, pathlen + 1);
 645     } else {
 646         if (pathlen > XENSTORE_REL_PATH_MAX) {
 647             return E2BIG;
 648         }
 649         snprintf(outpath, XENSTORE_ABS_PATH_MAX, "/local/domain/%u/%s", dom_id,
 650                  userpath);
 651     }
 652     return 0;
 653 }
 654
 655
 656 static int init_walk_op(XenstoreImplState *s, struct walk_op *op,
 657                         xs_transaction_t tx_id, unsigned int dom_id,
 658                         const char *path, XsNode ***rootp)
 659 {
 660     int ret = validate_path(op->path, path, dom_id);
 661     if (ret) {
 662         return ret;
 663     }
 664
 665     /*
 666      * We use *two* NUL terminators at the end of the path, as during the walk
 667      * we will temporarily turn each '/' into a NUL to allow us to use that
 668      * path element for the lookup.
 669      */
 670     op->path[strlen(op->path) + 1] = '\0';
 671     op->watches = NULL;
 672     op->path[0] = '\0';
 673     op->inplace = true;
 674     op->mutating = false;
 675     op->create_dirs = false;
 676     op->in_transaction = false;
 677     op->dom_id = dom_id;
 678     op->tx_id = tx_id;
 679     op->s = s;
 680
 681     if (tx_id == XBT_NULL) {
 682         *rootp = &s->root;
 683         op->new_nr_nodes = s->nr_nodes;
 684     } else {
 685         XsTransaction *tx = g_hash_table_lookup(s->transactions,
 686                                                 GINT_TO_POINTER(tx_id));
 687         if (!tx) {
 688             return ENOENT;
 689         }
 690         *rootp = &tx->root;
 691         op->new_nr_nodes = tx->nr_nodes;
 692         op->in_transaction = true;
 693     }
 694
 695     return 0;
 696 }
 697
 698 int xs_impl_read(XenstoreImplState *s, unsigned int dom_id,
 699                  xs_transaction_t tx_id, const char *path, GByteArray *data)
 700 {
 701     /*
 702      * The data GByteArray shall exist, and will be freed by caller.
 703      * Just g_byte_array_append() to it.
 704      */
 705     struct walk_op op;
 706     XsNode **n;
 707     int ret;
 708
 709     ret = init_walk_op(s, &op, tx_id, dom_id, path, &n);
 710     if (ret) {
 711         return ret;
 712     }
 713     op.op_fn = xs_node_get_content;
 714     op.op_opaque = data;
 715     return xs_node_walk(n, &op);
 716 }
 717
 718 int xs_impl_write(XenstoreImplState *s, unsigned int dom_id,
 719                   xs_transaction_t tx_id, const char *path, GByteArray *data)
 720 {
 721     /*
 722      * The data GByteArray shall exist, will be freed by caller. You are
 723      * free to use g_byte_array_steal() and keep the data. Or just ref it.
 724      */
 725     struct walk_op op;
 726     XsNode **n;
 727     int ret;
 728
 729     ret = init_walk_op(s, &op, tx_id, dom_id, path, &n);
 730     if (ret) {
 731         return ret;
 732     }
 733     op.op_fn = xs_node_add_content;
 734     op.op_opaque = data;
 735     op.mutating = true;
 736     op.create_dirs = true;
 737     return xs_node_walk(n, &op);
 738 }
 739
 740 int xs_impl_directory(XenstoreImplState *s, unsigned int dom_id,
 741                       xs_transaction_t tx_id, const char *path,
 742                       uint64_t *gencnt, GList **items)
 743 {
 744     /*
 745      * The items are (char *) to be freed by caller. Although it's consumed
 746      * immediately so if you want to change it to (const char *) and keep
 747      * them, go ahead and change the caller.
 748      */
 749     struct walk_op op;
 750     XsNode **n;
 751     int ret;
 752
 753     ret = init_walk_op(s, &op, tx_id, dom_id, path, &n);
 754     if (ret) {
 755         return ret;
 756     }
 757     op.op_fn = xs_node_directory;
 758     op.op_opaque = items;
 759     op.op_opaque2 = gencnt;
 760     return xs_node_walk(n, &op);
 761 }
 762
 763 int xs_impl_transaction_start(XenstoreImplState *s, unsigned int dom_id,
 764                               xs_transaction_t *tx_id)
 765 {
 766     XsTransaction *tx;
 767
 768     if (*tx_id != XBT_NULL) {
 769         return EINVAL;
 770     }
 771
 772     if (dom_id && s->nr_domu_transactions >= XS_MAX_TRANSACTIONS) {
 773         return ENOSPC;
 774     }
 775
 776     tx = g_new0(XsTransaction, 1);
 777
 778     tx->nr_nodes = s->nr_nodes;
 779     tx->tx_id = next_tx(s);
 780     tx->base_tx = s->root_tx;
 781     tx->root = xs_node_ref(s->root);
 782     tx->dom_id = dom_id;
 783
 784     g_hash_table_insert(s->transactions, GINT_TO_POINTER(tx->tx_id), tx);
 785     if (dom_id) {
 786         s->nr_domu_transactions++;
 787     }
 788     *tx_id = tx->tx_id;
 789     return 0;
 790 }
 791
 792 static gboolean tx_commit_walk(gpointer key, gpointer value,
 793                                gpointer user_data)
 794 {
 795     struct walk_op *op = user_data;
 796     int path_len = strlen(op->path);
 797     int key_len = strlen(key);
 798     bool fire_parents = true;
 799     XsWatch *watch;
 800     XsNode *n = value;
 801
 802     if (n->ref != 1) {
 803         return false;
 804     }
 805
 806     if (n->deleted_in_tx) {
 807         /*
 808          * We fire watches on our parents if we are the *first* node
 809          * to be deleted (the topmost one). This matches the behaviour
 810          * when deleting in the live tree.
 811          */
 812         fire_parents = !op->deleted_in_tx;
 813
 814         /* Only used on the way down so no need to clear it later */
 815         op->deleted_in_tx = true;
 816     }
 817
 818     assert(key_len + path_len + 2 <= sizeof(op->path));
 819     op->path[path_len] = '/';
 820     memcpy(op->path + path_len + 1, key, key_len + 1);
 821
 822     watch = g_hash_table_lookup(op->s->watches, op->path);
 823     if (watch) {
 824         op->watches = g_list_append(op->watches, watch);
 825     }
 826
 827     if (n->children) {
 828         g_hash_table_foreach_remove(n->children, tx_commit_walk, op);
 829     }
 830
 831     if (watch) {
 832         op->watches = g_list_remove(op->watches, watch);
 833     }
 834
 835     /*
 836      * Don't fire watches if this node was only copied because a
 837      * descendent was changed. The modified_in_tx flag indicates the
 838      * ones which were really changed.
 839      */
 840     if (n->modified_in_tx || n->deleted_in_tx) {
 841         fire_watches(op, fire_parents);
 842         n->modified_in_tx = false;
 843     }
 844     op->path[path_len] = '\0';
 845
 846     /* Deleted nodes really do get expunged when we commit */
 847     return n->deleted_in_tx;
 848 }
 849
 850 static int transaction_commit(XenstoreImplState *s, XsTransaction *tx)
 851 {
 852     struct walk_op op;
 853     XsNode **n;
 854
 855     if (s->root_tx != tx->base_tx) {
 856         return EAGAIN;
 857     }
 858     xs_node_unref(s->root);
 859     s->root = tx->root;
 860     tx->root = NULL;
 861     s->root_tx = tx->tx_id;
 862     s->nr_nodes = tx->nr_nodes;
 863
 864     init_walk_op(s, &op, XBT_NULL, tx->dom_id, "/", &n);
 865     op.deleted_in_tx = false;
 866     op.mutating = true;
 867
 868     /*
 869      * Walk the new root and fire watches on any node which has a
 870      * refcount of one (which is therefore unique to this transaction).
 871      */
 872     if (s->root->children) {
 873         g_hash_table_foreach_remove(s->root->children, tx_commit_walk, &op);
 874     }
 875
 876     return 0;
 877 }
 878
 879 int xs_impl_transaction_end(XenstoreImplState *s, unsigned int dom_id,
 880                             xs_transaction_t tx_id, bool commit)
 881 {
 882     int ret = 0;
 883     XsTransaction *tx = g_hash_table_lookup(s->transactions,
 884                                             GINT_TO_POINTER(tx_id));
 885
 886     if (!tx || tx->dom_id != dom_id) {
 887         return ENOENT;
 888     }
 889
 890     if (commit) {
 891         ret = transaction_commit(s, tx);
 892     }
 893
 894     g_hash_table_remove(s->transactions, GINT_TO_POINTER(tx_id));
 895     if (dom_id) {
 896         assert(s->nr_domu_transactions);
 897         s->nr_domu_transactions--;
 898     }
 899     return ret;
 900 }
 901
 902 int xs_impl_rm(XenstoreImplState *s, unsigned int dom_id,
 903                xs_transaction_t tx_id, const char *path)
 904 {
 905     struct walk_op op;
 906     XsNode **n;
 907     int ret;
 908
 909     ret = init_walk_op(s, &op, tx_id, dom_id, path, &n);
 910     if (ret) {
 911         return ret;
 912     }
 913     op.op_fn = xs_node_rm;
 914     op.mutating = true;
 915     return xs_node_walk(n, &op);
 916 }
 917
 918 int xs_impl_get_perms(XenstoreImplState *s, unsigned int dom_id,
 919                       xs_transaction_t tx_id, const char *path, GList **perms)
 920 {
 921     /*
 922      * The perms are (char *) in the <perm-as-string> wire format to be
 923      * freed by the caller.
 924      */
 925     return ENOSYS;
 926 }
 927
 928 int xs_impl_set_perms(XenstoreImplState *s, unsigned int dom_id,
 929                       xs_transaction_t tx_id, const char *path, GList *perms)
 930 {
 931     /*
 932      * The perms are (const char *) in the <perm-as-string> wire format.
 933      */
 934     return ENOSYS;
 935 }
 936
 937 int xs_impl_watch(XenstoreImplState *s, unsigned int dom_id, const char *path,
 938                   const char *token, xs_impl_watch_fn fn, void *opaque)
 939 {
 940     char abspath[XENSTORE_ABS_PATH_MAX + 1];
 941     XsWatch *w, *l;
 942     int ret;
 943
 944     ret = validate_path(abspath, path, dom_id);
 945     if (ret) {
 946         return ret;
 947     }
 948
 949     /* Check for duplicates */
 950     l = w = g_hash_table_lookup(s->watches, abspath);
 951     while (w) {
 952         if (!g_strcmp0(token, w->token) &&  opaque == w->cb_opaque &&
 953             fn == w->cb && dom_id == w->dom_id) {
 954             return EEXIST;
 955         }
 956         w = w->next;
 957     }
 958
 959     if (dom_id && s->nr_domu_watches >= XS_MAX_WATCHES) {
 960         return E2BIG;
 961     }
 962
 963     w = g_new0(XsWatch, 1);
 964     w->token = g_strdup(token);
 965     w->cb = fn;
 966     w->cb_opaque = opaque;
 967     w->dom_id = dom_id;
 968     w->rel_prefix = strlen(abspath) - strlen(path);
 969
 970     /* l was looked up above when checking for duplicates */
 971     if (l) {
 972         w->next = l->next;
 973         l->next = w;
 974     } else {
 975         g_hash_table_insert(s->watches, g_strdup(abspath), w);
 976     }
 977     if (dom_id) {
 978         s->nr_domu_watches++;
 979     }
 980
 981     /* A new watch should fire immediately */
 982     fn(opaque, path, token);
 983
 984     return 0;
 985 }
 986
 987 static XsWatch *free_watch(XenstoreImplState *s, XsWatch *w)
 988 {
 989     XsWatch *next = w->next;
 990
 991     if (w->dom_id) {
 992         assert(s->nr_domu_watches);
 993         s->nr_domu_watches--;
 994     }
 995
 996     g_free(w->token);
 997     g_free(w);
 998
 999     return next;
1000 }
1001
1002 int xs_impl_unwatch(XenstoreImplState *s, unsigned int dom_id,
1003                     const char *path, const char *token,
1004                     xs_impl_watch_fn fn, void *opaque)
1005 {
1006     char abspath[XENSTORE_ABS_PATH_MAX + 1];
1007     XsWatch *w, **l;
1008     int ret;
1009
1010     ret = validate_path(abspath, path, dom_id);
1011     if (ret) {
1012         return ret;
1013     }
1014
1015     w = g_hash_table_lookup(s->watches, abspath);
1016     if (!w) {
1017         return ENOENT;
1018     }
1019
1020     /*
1021      * The hash table contains the first element of a list of
1022      * watches. Removing the first element in the list is a
1023      * special case because we have to update the hash table to
1024      * point to the next (or remove it if there's nothing left).
1025      */
1026     if (!g_strcmp0(token, w->token) && fn == w->cb && opaque == w->cb_opaque &&
1027         dom_id == w->dom_id) {
1028         if (w->next) {
1029             /* Insert the previous 'next' into the hash table */
1030             g_hash_table_insert(s->watches, g_strdup(abspath), w->next);
1031         } else {
1032             /* Nothing left; remove from hash table */
1033             g_hash_table_remove(s->watches, abspath);
1034         }
1035         free_watch(s, w);
1036         return 0;
1037     }
1038
1039     /*
1040      * We're all done messing with the hash table because the element
1041      * it points to has survived the cull. Now it's just a simple
1042      * linked list removal operation.
1043      */
1044     for (l = &w->next; *l; l = &w->next) {
1045         w = *l;
1046
1047         if (!g_strcmp0(token, w->token) && fn == w->cb &&
1048             opaque != w->cb_opaque && dom_id == w->dom_id) {
1049             *l = free_watch(s, w);
1050             return 0;
1051         }
1052     }
1053
1054     return ENOENT;
1055 }
1056
1057 int xs_impl_reset_watches(XenstoreImplState *s, unsigned int dom_id)
1058 {
1059     char **watch_paths;
1060     guint nr_watch_paths;
1061     guint i;
1062
1063     watch_paths = (char **)g_hash_table_get_keys_as_array(s->watches,
1064                                                           &nr_watch_paths);
1065
1066     for (i = 0; i < nr_watch_paths; i++) {
1067         XsWatch *w1 = g_hash_table_lookup(s->watches, watch_paths[i]);
1068         XsWatch *w2, *w, **l;
1069
1070         /*
1071          * w1 is the original list. The hash table has this pointer.
1072          * w2 is the head of our newly-filtered list.
1073          * w and l are temporary for processing. w is somewhat redundant
1074          * with *l but makes my eyes bleed less.
1075          */
1076
1077         w = w2 = w1;
1078         l = &w;
1079         while (w) {
1080             if (w->dom_id == dom_id) {
1081                 /* If we're freeing the head of the list, bump w2 */
1082                 if (w2 == w) {
1083                     w2 = w->next;
1084                 }
1085                 *l = free_watch(s, w);
1086             } else {
1087                 l = &w->next;
1088             }
1089             w = *l;
1090         }
1091         /*
1092          * If the head of the list survived the cull, we don't need to
1093          * touch the hash table and we're done with this path. Else...
1094          */
1095         if (w1 != w2) {
1096             g_hash_table_steal(s->watches, watch_paths[i]);
1097
1098             /*
1099              * It was already freed. (Don't worry, this whole thing is
1100              * single-threaded and nobody saw it in the meantime). And
1101              * having *stolen* it, we now own the watch_paths[i] string
1102              * so if we don't give it back to the hash table, we need
1103              * to free it.
1104              */
1105             if (w2) {
1106                 g_hash_table_insert(s->watches, watch_paths[i], w2);
1107             } else {
1108                 g_free(watch_paths[i]);
1109             }
1110         }
1111     }
1112     g_free(watch_paths);
1113     return 0;
1114 }
1115
1116 static void xs_tx_free(void *_tx)
1117 {
1118     XsTransaction *tx = _tx;
1119     if (tx->root) {
1120         xs_node_unref(tx->root);
1121     }
1122     g_free(tx);
1123 }
1124
1125 XenstoreImplState *xs_impl_create(void)
1126 {
1127     XenstoreImplState *s = g_new0(XenstoreImplState, 1);
1128
1129     s->watches = g_hash_table_new_full(g_str_hash, g_str_equal, g_free, NULL);
1130     s->transactions = g_hash_table_new_full(g_direct_hash, g_direct_equal,
1131                                             NULL, xs_tx_free);
1132     s->nr_nodes = 1;
1133     s->root = xs_node_new();
1134 #ifdef XS_NODE_UNIT_TEST
1135     s->root->name = g_strdup("/");
1136 #endif
1137
1138     s->root_tx = s->last_tx = 1;
1139     return s;
1140 }