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