src/libsystemd-bus/bus-match.c

   1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
   2
   3 /***
   4   This file is part of systemd.
   5
   6   Copyright 2013 Lennart Poettering
   7
   8   systemd is free software; you can redistribute it and/or modify it
   9   under the terms of the GNU Lesser General Public License as published by
  10   the Free Software Foundation; either version 2.1 of the License, or
  11   (at your option) any later version.
  12
  13   systemd is distributed in the hope that it will be useful, but
  14   WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16   Lesser General Public License for more details.
  17
  18   You should have received a copy of the GNU Lesser General Public License
  19   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  20 ***/
  21
  22 #include "bus-internal.h"
  23 #include "bus-message.h"
  24 #include "bus-match.h"
  25 #include "bus-error.h"
  26 #include "bus-util.h"
  27
  28 /* Example:
  29  *
  30  *  A: type=signal,sender=foo,interface=bar
  31  *  B: type=signal,sender=quux,interface=fips
  32  *  C: type=signal,sender=quux,interface=waldo
  33  *  D: type=signal,member=test
  34  *  E: sender=miau
  35  *  F: type=signal
  36  *  G: type=signal
  37  *
  38  *  results in this tree:
  39  *
  40  *  BUS_MATCH_ROOT
  41  *  + BUS_MATCH_MESSAGE_TYPE
  42  *  | ` BUS_MATCH_VALUE: value == signal
  43  *  |   + DBUS_MATCH_SENDER
  44  *  |   | + BUS_MATCH_VALUE: value == foo
  45  *  |   | | ` DBUS_MATCH_INTERFACE
  46  *  |   | |   ` BUS_MATCH_VALUE: value == bar
  47  *  |   | |     ` BUS_MATCH_LEAF: A
  48  *  |   | ` BUS_MATCH_VALUE: value == quux
  49  *  |   |   ` DBUS_MATCH_INTERFACE
  50  *  |   |     | BUS_MATCH_VALUE: value == fips
  51  *  |   |     | ` BUS_MATCH_LEAF: B
  52  *  |   |     ` BUS_MATCH_VALUE: value == waldo
  53  *  |   |       ` BUS_MATCH_LEAF: C
  54  *  |   + DBUS_MATCH_MEMBER
  55  *  |   | ` BUS_MATCH_VALUE: value == test
  56  *  |   |   ` BUS_MATCH_LEAF: D
  57  *  |   + BUS_MATCH_LEAF: F
  58  *  |   ` BUS_MATCH_LEAF: G
  59  *  ` BUS_MATCH_SENDER
  60  *    ` BUS_MATCH_VALUE: value == miau
  61  *      ` BUS_MATCH_LEAF: E
  62  */
  63
  64 static inline bool BUS_MATCH_IS_COMPARE(enum bus_match_node_type t) {
  65         return t >= BUS_MATCH_SENDER && t <= BUS_MATCH_ARG_NAMESPACE_LAST;
  66 }
  67
  68 static inline bool BUS_MATCH_CAN_HASH(enum bus_match_node_type t) {
  69         return (t >= BUS_MATCH_MESSAGE_TYPE && t <= BUS_MATCH_PATH) ||
  70                 (t >= BUS_MATCH_ARG && t <= BUS_MATCH_ARG_LAST);
  71 }
  72
  73 static void bus_match_node_free(struct bus_match_node *node) {
  74         assert(node);
  75         assert(node->parent);
  76         assert(!node->child);
  77         assert(node->type != BUS_MATCH_ROOT);
  78         assert(node->type < _BUS_MATCH_NODE_TYPE_MAX);
  79
  80         if (node->parent->child) {
  81                 /* We are apparently linked into the parent's child
  82                  * list. Let's remove us from there. */
  83                 if (node->prev) {
  84                         assert(node->prev->next == node);
  85                         node->prev->next = node->next;
  86                 } else {
  87                         assert(node->parent->child == node);
  88                         node->parent->child = node->next;
  89                 }
  90
  91                 if (node->next)
  92                         node->next->prev = node->prev;
  93         }
  94
  95         if (node->type == BUS_MATCH_VALUE) {
  96                 /* We might be in the parent's hash table, so clean
  97                  * this up */
  98
  99                 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
 100                         hashmap_remove(node->parent->compare.children, UINT_TO_PTR(node->value.u8));
 101                 else if (BUS_MATCH_CAN_HASH(node->parent->type) && node->value.str)
 102                         hashmap_remove(node->parent->compare.children, node->value.str);
 103
 104                 free(node->value.str);
 105         }
 106
 107         if (BUS_MATCH_IS_COMPARE(node->type)) {
 108                 assert(hashmap_isempty(node->compare.children));
 109                 hashmap_free(node->compare.children);
 110         }
 111
 112         free(node);
 113 }
 114
 115 static bool bus_match_node_maybe_free(struct bus_match_node *node) {
 116         assert(node);
 117
 118         if (node->child)
 119                 return false;
 120
 121         if (BUS_MATCH_IS_COMPARE(node->type) && !hashmap_isempty(node->compare.children))
 122                 return true;
 123
 124         bus_match_node_free(node);
 125         return true;
 126 }
 127
 128 static bool value_node_test(
 129                 struct bus_match_node *node,
 130                 enum bus_match_node_type parent_type,
 131                 uint8_t value_u8,
 132                 const char *value_str) {
 133
 134         assert(node);
 135         assert(node->type == BUS_MATCH_VALUE);
 136
 137         /* Tests parameters against this value node, doing prefix
 138          * magic and stuff. */
 139
 140         switch (parent_type) {
 141
 142         case BUS_MATCH_MESSAGE_TYPE:
 143                 return node->value.u8 == value_u8;
 144
 145         case BUS_MATCH_SENDER:
 146         case BUS_MATCH_DESTINATION:
 147                 if (streq_ptr(node->value.str, value_str))
 148                         return true;
 149
 150                 /* FIXME: So here's an ugliness: if the match is for a
 151                  * well-known name then we cannot actually check this
 152                  * correctly here. This doesn't matter much for dbus1
 153                  * where no false positives exist, hence we just
 154                  * ignore this case here. For kdbus the messages
 155                  * should contain all well-known names of the sender,
 156                  * hence we can fix things there correctly. */
 157
 158                 if (node->value.str[0] != ':' && value_str && value_str[0] == ':')
 159                         return true;
 160
 161                 return false;
 162
 163         case BUS_MATCH_INTERFACE:
 164         case BUS_MATCH_MEMBER:
 165         case BUS_MATCH_PATH:
 166         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 167                 return streq_ptr(node->value.str, value_str);
 168
 169         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
 170                 return namespace_simple_pattern(node->value.str, value_str);
 171
 172         case BUS_MATCH_PATH_NAMESPACE:
 173                 return path_simple_pattern(node->value.str, value_str);
 174
 175         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
 176                 return path_complex_pattern(node->value.str, value_str);
 177
 178         default:
 179                 assert_not_reached("Invalid node type");
 180         }
 181 }
 182
 183 static bool value_node_same(
 184                 struct bus_match_node *node,
 185                 enum bus_match_node_type parent_type,
 186                 uint8_t value_u8,
 187                 const char *value_str) {
 188
 189         /* Tests parameters against this value node, not doing prefix
 190          * magic and stuff, i.e. this one actually compares the match
 191          * itself.*/
 192
 193         assert(node);
 194         assert(node->type == BUS_MATCH_VALUE);
 195
 196         switch (parent_type) {
 197
 198         case BUS_MATCH_MESSAGE_TYPE:
 199                 return node->value.u8 == value_u8;
 200
 201         case BUS_MATCH_SENDER:
 202         case BUS_MATCH_DESTINATION:
 203         case BUS_MATCH_INTERFACE:
 204         case BUS_MATCH_MEMBER:
 205         case BUS_MATCH_PATH:
 206         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 207         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
 208         case BUS_MATCH_PATH_NAMESPACE:
 209         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
 210                 return streq(node->value.str, value_str);
 211
 212         default:
 213                 assert_not_reached("Invalid node type");
 214         }
 215 }
 216
 217 int bus_match_run(
 218                 sd_bus *bus,
 219                 struct bus_match_node *node,
 220                 sd_bus_message *m) {
 221
 222
 223         const char *test_str = NULL;
 224         uint8_t test_u8 = 0;
 225         int r;
 226
 227         assert(m);
 228
 229         if (!node)
 230                 return 0;
 231
 232         if (bus && bus->match_callbacks_modified)
 233                 return 0;
 234
 235         /* Not these special semantics: when traversing the tree we
 236          * usually let bus_match_run() when called for a node
 237          * recursively invoke bus_match_run(). There's are two
 238          * exceptions here though, which are BUS_NODE_ROOT (which
 239          * cannot have a sibling), and BUS_NODE_VALUE (whose siblings
 240          * are invoked anyway by its parent. */
 241
 242         switch (node->type) {
 243
 244         case BUS_MATCH_ROOT:
 245
 246                 /* Run all children. Since we cannot have any siblings
 247                  * we won't call any. The children of the root node
 248                  * are compares or leaves, they will automatically
 249                  * call their siblings. */
 250                 return bus_match_run(bus, node->child, m);
 251
 252         case BUS_MATCH_VALUE:
 253
 254                 /* Run all children. We don't execute any siblings, we
 255                  * assume our caller does that. The children of value
 256                  * nodes are compares or leaves, they will
 257                  * automatically call their siblings */
 258
 259                 assert(node->child);
 260                 return bus_match_run(bus, node->child, m);
 261
 262         case BUS_MATCH_LEAF:
 263
 264                 if (bus) {
 265                         if (node->leaf.last_iteration == bus->iteration_counter)
 266                                 return 0;
 267
 268                         node->leaf.last_iteration = bus->iteration_counter;
 269                 }
 270
 271                 r = sd_bus_message_rewind(m, true);
 272                 if (r < 0)
 273                         return r;
 274
 275                 /* Run the callback. And then invoke siblings. */
 276                 if (node->leaf.callback) {
 277                         _cleanup_bus_error_free_ sd_bus_error error_buffer = SD_BUS_ERROR_NULL;
 278
 279                         r = node->leaf.callback(bus, m, node->leaf.userdata, &error_buffer);
 280                         r = bus_maybe_reply_error(m, r, &error_buffer);
 281                         if (r != 0)
 282                                 return r;
 283                 }
 284
 285                 return bus_match_run(bus, node->next, m);
 286
 287         case BUS_MATCH_MESSAGE_TYPE:
 288                 test_u8 = m->header->type;
 289                 break;
 290
 291         case BUS_MATCH_SENDER:
 292                 test_str = m->sender;
 293                 /* FIXME: resolve test_str from a well-known to a unique name first */
 294                 break;
 295
 296         case BUS_MATCH_DESTINATION:
 297                 test_str = m->destination;
 298                 break;
 299
 300         case BUS_MATCH_INTERFACE:
 301                 test_str = m->interface;
 302                 break;
 303
 304         case BUS_MATCH_MEMBER:
 305                 test_str = m->member;
 306                 break;
 307
 308         case BUS_MATCH_PATH:
 309         case BUS_MATCH_PATH_NAMESPACE:
 310                 test_str = m->path;
 311                 break;
 312
 313         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 314                 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG);
 315                 break;
 316
 317         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
 318                 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_PATH);
 319                 break;
 320
 321         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
 322                 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_NAMESPACE);
 323                 break;
 324
 325         default:
 326                 assert_not_reached("Unknown match type.");
 327         }
 328
 329         if (BUS_MATCH_CAN_HASH(node->type)) {
 330                 struct bus_match_node *found;
 331
 332                 /* Lookup via hash table, nice! So let's jump directly. */
 333
 334                 if (test_str)
 335                         found = hashmap_get(node->compare.children, test_str);
 336                 else if (node->type == BUS_MATCH_MESSAGE_TYPE)
 337                         found = hashmap_get(node->compare.children, UINT_TO_PTR(test_u8));
 338                 else
 339                         found = NULL;
 340
 341                 if (found) {
 342                         r = bus_match_run(bus, found, m);
 343                         if (r != 0)
 344                                 return r;
 345                 }
 346         } else {
 347                 struct bus_match_node *c;
 348
 349                 /* No hash table, so let's iterate manually... */
 350
 351                 for (c = node->child; c; c = c->next) {
 352                         if (!value_node_test(c, node->type, test_u8, test_str))
 353                                 continue;
 354
 355                         r = bus_match_run(bus, c, m);
 356                         if (r != 0)
 357                                 return r;
 358                 }
 359         }
 360
 361         if (bus && bus->match_callbacks_modified)
 362                 return 0;
 363
 364         /* And now, let's invoke our siblings */
 365         return bus_match_run(bus, node->next, m);
 366 }
 367
 368 static int bus_match_add_compare_value(
 369                 struct bus_match_node *where,
 370                 enum bus_match_node_type t,
 371                 uint8_t value_u8,
 372                 const char *value_str,
 373                 struct bus_match_node **ret) {
 374
 375         struct bus_match_node *c = NULL, *n = NULL;
 376         int r;
 377
 378         assert(where);
 379         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 380         assert(BUS_MATCH_IS_COMPARE(t));
 381         assert(ret);
 382
 383         for (c = where->child; c && c->type != t; c = c->next)
 384                 ;
 385
 386         if (c) {
 387                 /* Comparison node already exists? Then let's see if
 388                  * the value node exists too. */
 389
 390                 if (t == BUS_MATCH_MESSAGE_TYPE)
 391                         n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
 392                 else if (BUS_MATCH_CAN_HASH(t))
 393                         n = hashmap_get(c->compare.children, value_str);
 394                 else {
 395                         for (n = c->child; n && !value_node_same(n, t, value_u8, value_str); n = n->next)
 396                                 ;
 397                 }
 398
 399                 if (n) {
 400                         *ret = n;
 401                         return 0;
 402                 }
 403         } else {
 404                 /* Comparison node, doesn't exist yet? Then let's
 405                  * create it. */
 406
 407                 c = new0(struct bus_match_node, 1);
 408                 if (!c) {
 409                         r = -ENOMEM;
 410                         goto fail;
 411                 }
 412
 413                 c->type = t;
 414                 c->parent = where;
 415                 c->next = where->child;
 416                 if (c->next)
 417                         c->next->prev = c;
 418                 where->child = c;
 419
 420                 if (t == BUS_MATCH_MESSAGE_TYPE) {
 421                         c->compare.children = hashmap_new(trivial_hash_func, trivial_compare_func);
 422                         if (!c->compare.children) {
 423                                 r = -ENOMEM;
 424                                 goto fail;
 425                         }
 426                 } else if (BUS_MATCH_CAN_HASH(t)) {
 427                         c->compare.children = hashmap_new(string_hash_func, string_compare_func);
 428                         if (!c->compare.children) {
 429                                 r = -ENOMEM;
 430                                 goto fail;
 431                         }
 432                 }
 433         }
 434
 435         n = new0(struct bus_match_node, 1);
 436         if (!n) {
 437                 r = -ENOMEM;
 438                 goto fail;
 439         }
 440
 441         n->type = BUS_MATCH_VALUE;
 442         n->value.u8 = value_u8;
 443         if (value_str) {
 444                 n->value.str = strdup(value_str);
 445                 if (!n->value.str) {
 446                         r = -ENOMEM;
 447                         goto fail;
 448                 }
 449         }
 450
 451         n->parent = c;
 452         if (c->compare.children) {
 453
 454                 if (t == BUS_MATCH_MESSAGE_TYPE)
 455                         r = hashmap_put(c->compare.children, UINT_TO_PTR(value_u8), n);
 456                 else
 457                         r = hashmap_put(c->compare.children, n->value.str, n);
 458
 459                 if (r < 0)
 460                         goto fail;
 461         } else {
 462                 n->next = c->child;
 463                 if (n->next)
 464                         n->next->prev = n;
 465                 c->child = n;
 466         }
 467
 468         *ret = n;
 469         return 1;
 470
 471 fail:
 472         if (c)
 473                 bus_match_node_maybe_free(c);
 474
 475         if (n) {
 476                 free(n->value.str);
 477                 free(n);
 478         }
 479
 480         return r;
 481 }
 482
 483 static int bus_match_find_compare_value(
 484                 struct bus_match_node *where,
 485                 enum bus_match_node_type t,
 486                 uint8_t value_u8,
 487                 const char *value_str,
 488                 struct bus_match_node **ret) {
 489
 490         struct bus_match_node *c, *n;
 491
 492         assert(where);
 493         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 494         assert(BUS_MATCH_IS_COMPARE(t));
 495         assert(ret);
 496
 497         for (c = where->child; c && c->type != t; c = c->next)
 498                 ;
 499
 500         if (!c)
 501                 return 0;
 502
 503         if (t == BUS_MATCH_MESSAGE_TYPE)
 504                 n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
 505         else if (BUS_MATCH_CAN_HASH(t))
 506                 n = hashmap_get(c->compare.children, value_str);
 507         else {
 508                 for (n = c->child; !value_node_same(n, t, value_u8, value_str); n = n->next)
 509                         ;
 510         }
 511
 512         if (n) {
 513                 *ret = n;
 514                 return 1;
 515         }
 516
 517         return 0;
 518 }
 519
 520 static int bus_match_add_leaf(
 521                 struct bus_match_node *where,
 522                 sd_bus_message_handler_t callback,
 523                 void *userdata,
 524                 uint64_t cookie,
 525                 struct bus_match_node **ret) {
 526
 527         struct bus_match_node *n;
 528
 529         assert(where);
 530         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 531         assert(ret);
 532
 533         n = new0(struct bus_match_node, 1);
 534         if (!n)
 535                 return -ENOMEM;
 536
 537         n->type = BUS_MATCH_LEAF;
 538         n->parent = where;
 539         n->next = where->child;
 540         if (n->next)
 541                 n->next->prev = n;
 542         n->leaf.callback = callback;
 543         n->leaf.userdata = userdata;
 544         n->leaf.cookie = cookie;
 545
 546         where->child = n;
 547
 548         *ret = n;
 549         return 1;
 550 }
 551
 552 static int bus_match_find_leaf(
 553                 struct bus_match_node *where,
 554                 sd_bus_message_handler_t callback,
 555                 void *userdata,
 556                 struct bus_match_node **ret) {
 557
 558         struct bus_match_node *c;
 559
 560         assert(where);
 561         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 562         assert(ret);
 563
 564         for (c = where->child; c; c = c->next) {
 565                 if (c->type == BUS_MATCH_LEAF &&
 566                     c->leaf.callback == callback &&
 567                     c->leaf.userdata == userdata) {
 568                         *ret = c;
 569                         return 1;
 570                 }
 571         }
 572
 573         return 0;
 574 }
 575
 576 enum bus_match_node_type bus_match_node_type_from_string(const char *k, size_t n) {
 577         assert(k);
 578
 579         if (n == 4 && startswith(k, "type"))
 580                 return BUS_MATCH_MESSAGE_TYPE;
 581         if (n == 6 && startswith(k, "sender"))
 582                 return BUS_MATCH_SENDER;
 583         if (n == 11 && startswith(k, "destination"))
 584                 return BUS_MATCH_DESTINATION;
 585         if (n == 9 && startswith(k, "interface"))
 586                 return BUS_MATCH_INTERFACE;
 587         if (n == 6 && startswith(k, "member"))
 588                 return BUS_MATCH_MEMBER;
 589         if (n == 4 && startswith(k, "path"))
 590                 return BUS_MATCH_PATH;
 591         if (n == 14 && startswith(k, "path_namespace"))
 592                 return BUS_MATCH_PATH_NAMESPACE;
 593
 594         if (n == 4 && startswith(k, "arg")) {
 595                 int j;
 596
 597                 j = undecchar(k[3]);
 598                 if (j < 0)
 599                         return -EINVAL;
 600
 601                 return BUS_MATCH_ARG + j;
 602         }
 603
 604         if (n == 5 && startswith(k, "arg")) {
 605                 int a, b;
 606                 enum bus_match_node_type t;
 607
 608                 a = undecchar(k[3]);
 609                 b = undecchar(k[4]);
 610                 if (a <= 0 || b < 0)
 611                         return -EINVAL;
 612
 613                 t = BUS_MATCH_ARG + a * 10 + b;
 614                 if (t > BUS_MATCH_ARG_LAST)
 615                         return -EINVAL;
 616
 617                 return t;
 618         }
 619
 620         if (n == 8 && startswith(k, "arg") && startswith(k + 4, "path")) {
 621                 int j;
 622
 623                 j = undecchar(k[3]);
 624                 if (j < 0)
 625                         return -EINVAL;
 626
 627                 return BUS_MATCH_ARG_PATH + j;
 628         }
 629
 630         if (n == 9 && startswith(k, "arg") && startswith(k + 5, "path")) {
 631                 enum bus_match_node_type t;
 632                 int a, b;
 633
 634                 a = undecchar(k[3]);
 635                 b = undecchar(k[4]);
 636                 if (a <= 0 || b < 0)
 637                         return -EINVAL;
 638
 639                 t = BUS_MATCH_ARG_PATH + a * 10 + b;
 640                 if (t > BUS_MATCH_ARG_PATH_LAST)
 641                         return -EINVAL;
 642
 643                 return t;
 644         }
 645
 646         if (n == 13 && startswith(k, "arg") && startswith(k + 4, "namespace")) {
 647                 int j;
 648
 649                 j = undecchar(k[3]);
 650                 if (j < 0)
 651                         return -EINVAL;
 652
 653                 return BUS_MATCH_ARG_NAMESPACE + j;
 654         }
 655
 656         if (n == 14 && startswith(k, "arg") && startswith(k + 5, "namespace")) {
 657                 enum bus_match_node_type t;
 658                 int a, b;
 659
 660                 a = undecchar(k[3]);
 661                 b = undecchar(k[4]);
 662                 if (a <= 0 || b < 0)
 663                         return -EINVAL;
 664
 665                 t = BUS_MATCH_ARG_NAMESPACE + a * 10 + b;
 666                 if (t > BUS_MATCH_ARG_NAMESPACE_LAST)
 667                         return -EINVAL;
 668
 669                 return t;
 670         }
 671
 672         return -EINVAL;
 673 }
 674
 675 static int match_component_compare(const void *a, const void *b) {
 676         const struct bus_match_component *x = a, *y = b;
 677
 678         if (x->type < y->type)
 679                 return -1;
 680         if (x->type > y->type)
 681                 return 1;
 682
 683         return 0;
 684 }
 685
 686 void bus_match_parse_free(struct bus_match_component *components, unsigned n_components) {
 687         unsigned i;
 688
 689         for (i = 0; i < n_components; i++)
 690                 free(components[i].value_str);
 691
 692         free(components);
 693 }
 694
 695 int bus_match_parse(
 696                 const char *match,
 697                 struct bus_match_component **_components,
 698                 unsigned *_n_components) {
 699
 700         const char *p = match;
 701         struct bus_match_component *components = NULL;
 702         size_t components_allocated = 0;
 703         unsigned n_components = 0, i;
 704         _cleanup_free_ char *value = NULL;
 705         int r;
 706
 707         assert(match);
 708         assert(_components);
 709         assert(_n_components);
 710
 711         while (*p != 0) {
 712                 const char *eq, *q;
 713                 enum bus_match_node_type t;
 714                 unsigned j = 0;
 715                 size_t value_allocated = 0;
 716                 bool escaped = false;
 717                 uint8_t u;
 718
 719                 eq = strchr(p, '=');
 720                 if (!eq)
 721                         return -EINVAL;
 722
 723                 if (eq[1] != '\'')
 724                         return -EINVAL;
 725
 726                 t = bus_match_node_type_from_string(p, eq - p);
 727                 if (t < 0)
 728                         return -EINVAL;
 729
 730                 for (q = eq + 2;; q++) {
 731
 732                         if (*q == 0) {
 733                                 r = -EINVAL;
 734                                 goto fail;
 735                         }
 736
 737                         if (!escaped) {
 738                                 if (*q == '\\') {
 739                                         escaped = true;
 740                                         continue;
 741                                 }
 742                                 if (*q == '\'') {
 743                                         if (value)
 744                                                 value[j] = 0;
 745                                         break;
 746                                 }
 747                         }
 748
 749                         if (!GREEDY_REALLOC(value, value_allocated, j + 2)) {
 750                                 r = -ENOMEM;
 751                                 goto fail;
 752                         }
 753
 754                         value[j++] = *q;
 755                         escaped = false;
 756                 }
 757
 758                 if (t == BUS_MATCH_MESSAGE_TYPE) {
 759                         r = bus_message_type_from_string(value, &u);
 760                         if (r < 0)
 761                                 goto fail;
 762
 763                         free(value);
 764                         value = NULL;
 765                 } else
 766                         u = 0;
 767
 768                 if (!GREEDY_REALLOC(components, components_allocated, n_components + 1)) {
 769                         r = -ENOMEM;
 770                         goto fail;
 771                 }
 772
 773                 components[n_components].type = t;
 774                 components[n_components].value_str = value;
 775                 components[n_components].value_u8 = u;
 776                 n_components++;
 777
 778                 value = NULL;
 779
 780                 if (q[1] == 0)
 781                         break;
 782
 783                 if (q[1] != ',') {
 784                         r = -EINVAL;
 785                         goto fail;
 786                 }
 787
 788                 p = q + 2;
 789         }
 790
 791         /* Order the whole thing, so that we always generate the same tree */
 792         qsort_safe(components, n_components, sizeof(struct bus_match_component), match_component_compare);
 793
 794         /* Check for duplicates */
 795         for (i = 0; i+1 < n_components; i++)
 796                 if (components[i].type == components[i+1].type) {
 797                         r = -EINVAL;
 798                         goto fail;
 799                 }
 800
 801         *_components = components;
 802         *_n_components = n_components;
 803
 804         return 0;
 805
 806 fail:
 807         bus_match_parse_free(components, n_components);
 808         return r;
 809 }
 810
 811 int bus_match_add(
 812                 struct bus_match_node *root,
 813                 struct bus_match_component *components,
 814                 unsigned n_components,
 815                 sd_bus_message_handler_t callback,
 816                 void *userdata,
 817                 uint64_t cookie,
 818                 struct bus_match_node **ret) {
 819
 820         unsigned i;
 821         struct bus_match_node *n;
 822         int r;
 823
 824         assert(root);
 825
 826         n = root;
 827         for (i = 0; i < n_components; i++) {
 828                 r = bus_match_add_compare_value(
 829                                 n, components[i].type,
 830                                 components[i].value_u8, components[i].value_str, &n);
 831                 if (r < 0)
 832                         return r;
 833         }
 834
 835         r = bus_match_add_leaf(n, callback, userdata, cookie, &n);
 836         if (r < 0)
 837                 return r;
 838
 839         if (ret)
 840                 *ret = n;
 841
 842         return 0;
 843 }
 844
 845 int bus_match_remove(
 846                 struct bus_match_node *root,
 847                 struct bus_match_component *components,
 848                 unsigned n_components,
 849                 sd_bus_message_handler_t callback,
 850                 void *userdata,
 851                 uint64_t *cookie) {
 852
 853         unsigned i;
 854         struct bus_match_node *n, **gc;
 855         int r;
 856
 857         assert(root);
 858
 859         gc = newa(struct bus_match_node*, n_components);
 860
 861         n = root;
 862         for (i = 0; i < n_components; i++) {
 863                 r = bus_match_find_compare_value(
 864                                 n, components[i].type,
 865                                 components[i].value_u8, components[i].value_str,
 866                                 &n);
 867                 if (r <= 0)
 868                         return r;
 869
 870                 gc[i] = n;
 871         }
 872
 873         r = bus_match_find_leaf(n, callback, userdata, &n);
 874         if (r <= 0)
 875                 return r;
 876
 877         if (cookie)
 878                 *cookie = n->leaf.cookie;
 879
 880         /* Free the leaf */
 881         bus_match_node_free(n);
 882
 883         /* Prune the tree above */
 884         for (i = n_components; i > 0; i --) {
 885                 struct bus_match_node *p = gc[i-1]->parent;
 886
 887                 if (!bus_match_node_maybe_free(gc[i-1]))
 888                         break;
 889
 890                 if (!bus_match_node_maybe_free(p))
 891                         break;
 892         }
 893
 894         return r;
 895 }
 896
 897 void bus_match_free(struct bus_match_node *node) {
 898         struct bus_match_node *c;
 899
 900         if (!node)
 901                 return;
 902
 903         if (BUS_MATCH_CAN_HASH(node->type)) {
 904                 Iterator i;
 905
 906                 HASHMAP_FOREACH(c, node->compare.children, i)
 907                         bus_match_free(c);
 908
 909                 assert(hashmap_isempty(node->compare.children));
 910         }
 911
 912         while ((c = node->child))
 913                 bus_match_free(c);
 914
 915         if (node->type != BUS_MATCH_ROOT)
 916                 bus_match_node_free(node);
 917 }
 918
 919 const char* bus_match_node_type_to_string(enum bus_match_node_type t, char buf[], size_t l) {
 920         switch (t) {
 921
 922         case BUS_MATCH_ROOT:
 923                 return "root";
 924
 925         case BUS_MATCH_VALUE:
 926                 return "value";
 927
 928         case BUS_MATCH_LEAF:
 929                 return "leaf";
 930
 931         case BUS_MATCH_MESSAGE_TYPE:
 932                 return "type";
 933
 934         case BUS_MATCH_SENDER:
 935                 return "sender";
 936
 937         case BUS_MATCH_DESTINATION:
 938                 return "destination";
 939
 940         case BUS_MATCH_INTERFACE:
 941                 return "interface";
 942
 943         case BUS_MATCH_MEMBER:
 944                 return "member";
 945
 946         case BUS_MATCH_PATH:
 947                 return "path";
 948
 949         case BUS_MATCH_PATH_NAMESPACE:
 950                 return "path_namespace";
 951
 952         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 953                 snprintf(buf, l, "arg%i", t - BUS_MATCH_ARG);
 954                 return buf;
 955
 956         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
 957                 snprintf(buf, l, "arg%ipath", t - BUS_MATCH_ARG_PATH);
 958                 return buf;
 959
 960         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
 961                 snprintf(buf, l, "arg%inamespace", t - BUS_MATCH_ARG_NAMESPACE);
 962                 return buf;
 963
 964         default:
 965                 return NULL;
 966         }
 967 }
 968
 969 void bus_match_dump(struct bus_match_node *node, unsigned level) {
 970         struct bus_match_node *c;
 971         _cleanup_free_ char *pfx = NULL;
 972         char buf[32];
 973
 974         if (!node)
 975                 return;
 976
 977         pfx = strrep("  ", level);
 978         printf("%s[%s]", strempty(pfx), bus_match_node_type_to_string(node->type, buf, sizeof(buf)));
 979
 980         if (node->type == BUS_MATCH_VALUE) {
 981                 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
 982                         printf(" <%u>\n", node->value.u8);
 983                 else
 984                         printf(" <%s>\n", node->value.str);
 985         } else if (node->type == BUS_MATCH_ROOT)
 986                 puts(" root");
 987         else if (node->type == BUS_MATCH_LEAF)
 988                 printf(" %p/%p\n", node->leaf.callback, node->leaf.userdata);
 989         else
 990                 putchar('\n');
 991
 992         if (BUS_MATCH_CAN_HASH(node->type)) {
 993                 Iterator i;
 994
 995                 HASHMAP_FOREACH(c, node->compare.children, i)
 996                         bus_match_dump(c, level + 1);
 997         }
 998
 999         for (c = node->child; c; c = c->next)
1000                 bus_match_dump(c, level + 1);
1001 }