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) {
 293                         sd_bus_slot *slot;
 294
 295                         _cleanup_bus_error_free_ sd_bus_error error_buffer = SD_BUS_ERROR_NULL;
 296
 297                         slot = container_of(node->leaf.callback, sd_bus_slot, match_callback);
 298                         if (bus)
 299                                 bus->current_slot = slot;
 300                         r = node->leaf.callback->callback(bus, m, slot->userdata, &error_buffer);
 301                         if (bus)
 302                                 bus->current_slot = NULL;
 303
 304                         r = bus_maybe_reply_error(m, r, &error_buffer);
 305                         if (r != 0)
 306                                 return r;
 307
 308                         if (bus && bus->match_callbacks_modified)
 309                                 return 0;
 310                 }
 311
 312                 return bus_match_run(bus, node->next, m);
 313
 314         case BUS_MATCH_MESSAGE_TYPE:
 315                 test_u8 = m->header->type;
 316                 break;
 317
 318         case BUS_MATCH_SENDER:
 319                 test_str = m->sender;
 320                 /* FIXME: resolve test_str from a well-known to a unique name first */
 321                 break;
 322
 323         case BUS_MATCH_DESTINATION:
 324                 test_str = m->destination;
 325                 break;
 326
 327         case BUS_MATCH_INTERFACE:
 328                 test_str = m->interface;
 329                 break;
 330
 331         case BUS_MATCH_MEMBER:
 332                 test_str = m->member;
 333                 break;
 334
 335         case BUS_MATCH_PATH:
 336         case BUS_MATCH_PATH_NAMESPACE:
 337                 test_str = m->path;
 338                 break;
 339
 340         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
 341                 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG);
 342                 break;
 343
 344         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
 345                 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_PATH);
 346                 break;
 347
 348         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
 349                 test_str = bus_message_get_arg(m, node->type - BUS_MATCH_ARG_NAMESPACE);
 350                 break;
 351
 352         default:
 353                 assert_not_reached("Unknown match type.");
 354         }
 355
 356         if (BUS_MATCH_CAN_HASH(node->type)) {
 357                 struct bus_match_node *found;
 358
 359                 /* Lookup via hash table, nice! So let's jump directly. */
 360
 361                 if (test_str)
 362                         found = hashmap_get(node->compare.children, test_str);
 363                 else if (node->type == BUS_MATCH_MESSAGE_TYPE)
 364                         found = hashmap_get(node->compare.children, UINT_TO_PTR(test_u8));
 365                 else
 366                         found = NULL;
 367
 368                 if (found) {
 369                         r = bus_match_run(bus, found, m);
 370                         if (r != 0)
 371                                 return r;
 372                 }
 373         } else {
 374                 struct bus_match_node *c;
 375
 376                 /* No hash table, so let's iterate manually... */
 377
 378                 for (c = node->child; c; c = c->next) {
 379                         if (!value_node_test(c, node->type, test_u8, test_str, m))
 380                                 continue;
 381
 382                         r = bus_match_run(bus, c, m);
 383                         if (r != 0)
 384                                 return r;
 385                 }
 386         }
 387
 388         if (bus && bus->match_callbacks_modified)
 389                 return 0;
 390
 391         /* And now, let's invoke our siblings */
 392         return bus_match_run(bus, node->next, m);
 393 }
 394
 395 static int bus_match_add_compare_value(
 396                 struct bus_match_node *where,
 397                 enum bus_match_node_type t,
 398                 uint8_t value_u8,
 399                 const char *value_str,
 400                 struct bus_match_node **ret) {
 401
 402         struct bus_match_node *c = NULL, *n = NULL;
 403         int r;
 404
 405         assert(where);
 406         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 407         assert(BUS_MATCH_IS_COMPARE(t));
 408         assert(ret);
 409
 410         for (c = where->child; c && c->type != t; c = c->next)
 411                 ;
 412
 413         if (c) {
 414                 /* Comparison node already exists? Then let's see if
 415                  * the value node exists too. */
 416
 417                 if (t == BUS_MATCH_MESSAGE_TYPE)
 418                         n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
 419                 else if (BUS_MATCH_CAN_HASH(t))
 420                         n = hashmap_get(c->compare.children, value_str);
 421                 else {
 422                         for (n = c->child; n && !value_node_same(n, t, value_u8, value_str); n = n->next)
 423                                 ;
 424                 }
 425
 426                 if (n) {
 427                         *ret = n;
 428                         return 0;
 429                 }
 430         } else {
 431                 /* Comparison node, doesn't exist yet? Then let's
 432                  * create it. */
 433
 434                 c = new0(struct bus_match_node, 1);
 435                 if (!c) {
 436                         r = -ENOMEM;
 437                         goto fail;
 438                 }
 439
 440                 c->type = t;
 441                 c->parent = where;
 442                 c->next = where->child;
 443                 if (c->next)
 444                         c->next->prev = c;
 445                 where->child = c;
 446
 447                 if (t == BUS_MATCH_MESSAGE_TYPE) {
 448                         c->compare.children = hashmap_new(trivial_hash_func, trivial_compare_func);
 449                         if (!c->compare.children) {
 450                                 r = -ENOMEM;
 451                                 goto fail;
 452                         }
 453                 } else if (BUS_MATCH_CAN_HASH(t)) {
 454                         c->compare.children = hashmap_new(string_hash_func, string_compare_func);
 455                         if (!c->compare.children) {
 456                                 r = -ENOMEM;
 457                                 goto fail;
 458                         }
 459                 }
 460         }
 461
 462         n = new0(struct bus_match_node, 1);
 463         if (!n) {
 464                 r = -ENOMEM;
 465                 goto fail;
 466         }
 467
 468         n->type = BUS_MATCH_VALUE;
 469         n->value.u8 = value_u8;
 470         if (value_str) {
 471                 n->value.str = strdup(value_str);
 472                 if (!n->value.str) {
 473                         r = -ENOMEM;
 474                         goto fail;
 475                 }
 476         }
 477
 478         n->parent = c;
 479         if (c->compare.children) {
 480
 481                 if (t == BUS_MATCH_MESSAGE_TYPE)
 482                         r = hashmap_put(c->compare.children, UINT_TO_PTR(value_u8), n);
 483                 else
 484                         r = hashmap_put(c->compare.children, n->value.str, n);
 485
 486                 if (r < 0)
 487                         goto fail;
 488         } else {
 489                 n->next = c->child;
 490                 if (n->next)
 491                         n->next->prev = n;
 492                 c->child = n;
 493         }
 494
 495         *ret = n;
 496         return 1;
 497
 498 fail:
 499         if (c)
 500                 bus_match_node_maybe_free(c);
 501
 502         if (n) {
 503                 free(n->value.str);
 504                 free(n);
 505         }
 506
 507         return r;
 508 }
 509
 510 static int bus_match_find_compare_value(
 511                 struct bus_match_node *where,
 512                 enum bus_match_node_type t,
 513                 uint8_t value_u8,
 514                 const char *value_str,
 515                 struct bus_match_node **ret) {
 516
 517         struct bus_match_node *c, *n;
 518
 519         assert(where);
 520         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 521         assert(BUS_MATCH_IS_COMPARE(t));
 522         assert(ret);
 523
 524         for (c = where->child; c && c->type != t; c = c->next)
 525                 ;
 526
 527         if (!c)
 528                 return 0;
 529
 530         if (t == BUS_MATCH_MESSAGE_TYPE)
 531                 n = hashmap_get(c->compare.children, UINT_TO_PTR(value_u8));
 532         else if (BUS_MATCH_CAN_HASH(t))
 533                 n = hashmap_get(c->compare.children, value_str);
 534         else {
 535                 for (n = c->child; !value_node_same(n, t, value_u8, value_str); n = n->next)
 536                         ;
 537         }
 538
 539         if (n) {
 540                 *ret = n;
 541                 return 1;
 542         }
 543
 544         return 0;
 545 }
 546
 547 static int bus_match_add_leaf(
 548                 struct bus_match_node *where,
 549                 struct match_callback *callback) {
 550
 551         struct bus_match_node *n;
 552
 553         assert(where);
 554         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 555         assert(callback);
 556
 557         n = new0(struct bus_match_node, 1);
 558         if (!n)
 559                 return -ENOMEM;
 560
 561         n->type = BUS_MATCH_LEAF;
 562         n->parent = where;
 563         n->next = where->child;
 564         if (n->next)
 565                 n->next->prev = n;
 566
 567         n->leaf.callback = callback;
 568         callback->match_node = n;
 569
 570         where->child = n;
 571
 572         return 1;
 573 }
 574
 575 static int bus_match_find_leaf(
 576                 struct bus_match_node *where,
 577                 sd_bus_message_handler_t callback,
 578                 void *userdata,
 579                 struct bus_match_node **ret) {
 580
 581         struct bus_match_node *c;
 582
 583         assert(where);
 584         assert(where->type == BUS_MATCH_ROOT || where->type == BUS_MATCH_VALUE);
 585         assert(ret);
 586
 587         for (c = where->child; c; c = c->next) {
 588                 sd_bus_slot *s;
 589
 590                 s = container_of(c->leaf.callback, sd_bus_slot, match_callback);
 591
 592                 if (c->type == BUS_MATCH_LEAF &&
 593                     c->leaf.callback->callback == callback &&
 594                     s->userdata == userdata) {
 595                         *ret = c;
 596                         return 1;
 597                 }
 598         }
 599
 600         return 0;
 601 }
 602
 603 enum bus_match_node_type bus_match_node_type_from_string(const char *k, size_t n) {
 604         assert(k);
 605
 606         if (n == 4 && startswith(k, "type"))
 607                 return BUS_MATCH_MESSAGE_TYPE;
 608         if (n == 6 && startswith(k, "sender"))
 609                 return BUS_MATCH_SENDER;
 610         if (n == 11 && startswith(k, "destination"))
 611                 return BUS_MATCH_DESTINATION;
 612         if (n == 9 && startswith(k, "interface"))
 613                 return BUS_MATCH_INTERFACE;
 614         if (n == 6 && startswith(k, "member"))
 615                 return BUS_MATCH_MEMBER;
 616         if (n == 4 && startswith(k, "path"))
 617                 return BUS_MATCH_PATH;
 618         if (n == 14 && startswith(k, "path_namespace"))
 619                 return BUS_MATCH_PATH_NAMESPACE;
 620
 621         if (n == 4 && startswith(k, "arg")) {
 622                 int j;
 623
 624                 j = undecchar(k[3]);
 625                 if (j < 0)
 626                         return -EINVAL;
 627
 628                 return BUS_MATCH_ARG + j;
 629         }
 630
 631         if (n == 5 && startswith(k, "arg")) {
 632                 int a, b;
 633                 enum bus_match_node_type t;
 634
 635                 a = undecchar(k[3]);
 636                 b = undecchar(k[4]);
 637                 if (a <= 0 || b < 0)
 638                         return -EINVAL;
 639
 640                 t = BUS_MATCH_ARG + a * 10 + b;
 641                 if (t > BUS_MATCH_ARG_LAST)
 642                         return -EINVAL;
 643
 644                 return t;
 645         }
 646
 647         if (n == 8 && startswith(k, "arg") && startswith(k + 4, "path")) {
 648                 int j;
 649
 650                 j = undecchar(k[3]);
 651                 if (j < 0)
 652                         return -EINVAL;
 653
 654                 return BUS_MATCH_ARG_PATH + j;
 655         }
 656
 657         if (n == 9 && startswith(k, "arg") && startswith(k + 5, "path")) {
 658                 enum bus_match_node_type t;
 659                 int a, b;
 660
 661                 a = undecchar(k[3]);
 662                 b = undecchar(k[4]);
 663                 if (a <= 0 || b < 0)
 664                         return -EINVAL;
 665
 666                 t = BUS_MATCH_ARG_PATH + a * 10 + b;
 667                 if (t > BUS_MATCH_ARG_PATH_LAST)
 668                         return -EINVAL;
 669
 670                 return t;
 671         }
 672
 673         if (n == 13 && startswith(k, "arg") && startswith(k + 4, "namespace")) {
 674                 int j;
 675
 676                 j = undecchar(k[3]);
 677                 if (j < 0)
 678                         return -EINVAL;
 679
 680                 return BUS_MATCH_ARG_NAMESPACE + j;
 681         }
 682
 683         if (n == 14 && startswith(k, "arg") && startswith(k + 5, "namespace")) {
 684                 enum bus_match_node_type t;
 685                 int a, b;
 686
 687                 a = undecchar(k[3]);
 688                 b = undecchar(k[4]);
 689                 if (a <= 0 || b < 0)
 690                         return -EINVAL;
 691
 692                 t = BUS_MATCH_ARG_NAMESPACE + a * 10 + b;
 693                 if (t > BUS_MATCH_ARG_NAMESPACE_LAST)
 694                         return -EINVAL;
 695
 696                 return t;
 697         }
 698
 699         return -EINVAL;
 700 }
 701
 702 static int match_component_compare(const void *a, const void *b) {
 703         const struct bus_match_component *x = a, *y = b;
 704
 705         if (x->type < y->type)
 706                 return -1;
 707         if (x->type > y->type)
 708                 return 1;
 709
 710         return 0;
 711 }
 712
 713 void bus_match_parse_free(struct bus_match_component *components, unsigned n_components) {
 714         unsigned i;
 715
 716         for (i = 0; i < n_components; i++)
 717                 free(components[i].value_str);
 718
 719         free(components);
 720 }
 721
 722 int bus_match_parse(
 723                 const char *match,
 724                 struct bus_match_component **_components,
 725                 unsigned *_n_components) {
 726
 727         const char *p = match;
 728         struct bus_match_component *components = NULL;
 729         size_t components_allocated = 0;
 730         unsigned n_components = 0, i;
 731         _cleanup_free_ char *value = NULL;
 732         int r;
 733
 734         assert(match);
 735         assert(_components);
 736         assert(_n_components);
 737
 738         while (*p != 0) {
 739                 const char *eq, *q;
 740                 enum bus_match_node_type t;
 741                 unsigned j = 0;
 742                 size_t value_allocated = 0;
 743                 bool escaped = false, quoted;
 744                 uint8_t u;
 745
 746                 eq = strchr(p, '=');
 747                 if (!eq)
 748                         return -EINVAL;
 749
 750                 t = bus_match_node_type_from_string(p, eq - p);
 751                 if (t < 0)
 752                         return -EINVAL;
 753
 754                 quoted = eq[1] == '\'';
 755
 756                 for (q = eq + 1 + quoted;; q++) {
 757
 758                         if (*q == 0) {
 759
 760                                 if (quoted) {
 761                                         r = -EINVAL;
 762                                         goto fail;
 763                                 } else {
 764                                         if (value)
 765                                                 value[j] = 0;
 766                                         break;
 767                                 }
 768                         }
 769
 770                         if (!escaped) {
 771                                 if (*q == '\\') {
 772                                         escaped = true;
 773                                         continue;
 774                                 }
 775
 776                                 if (quoted) {
 777                                         if (*q == '\'') {
 778                                                 if (value)
 779                                                         value[j] = 0;
 780                                                 break;
 781                                         }
 782                                 } else {
 783                                         if (*q == ',') {
 784                                                 if (value)
 785                                                         value[j] = 0;
 786
 787                                                 break;
 788                                         }
 789                                 }
 790                         }
 791
 792                         if (!GREEDY_REALLOC(value, value_allocated, j + 2)) {
 793                                 r = -ENOMEM;
 794                                 goto fail;
 795                         }
 796
 797                         value[j++] = *q;
 798                         escaped = false;
 799                 }
 800
 801                 if (!value) {
 802                         value = strdup("");
 803                         if (!value) {
 804                                 r = -ENOMEM;
 805                                 goto fail;
 806                         }
 807                 }
 808
 809                 if (t == BUS_MATCH_MESSAGE_TYPE) {
 810                         r = bus_message_type_from_string(value, &u);
 811                         if (r < 0)
 812                                 goto fail;
 813
 814                         free(value);
 815                         value = NULL;
 816                 } else
 817                         u = 0;
 818
 819                 if (!GREEDY_REALLOC(components, components_allocated, n_components + 1)) {
 820                         r = -ENOMEM;
 821                         goto fail;
 822                 }
 823
 824                 components[n_components].type = t;
 825                 components[n_components].value_str = value;
 826                 components[n_components].value_u8 = u;
 827                 n_components++;
 828
 829                 value = NULL;
 830
 831                 if (q[quoted] == 0)
 832                         break;
 833
 834                 if (q[quoted] != ',') {
 835                         r = -EINVAL;
 836                         goto fail;
 837                 }
 838
 839                 p = q + 1 + quoted;
 840         }
 841
 842         /* Order the whole thing, so that we always generate the same tree */
 843         qsort_safe(components, n_components, sizeof(struct bus_match_component), match_component_compare);
 844
 845         /* Check for duplicates */
 846         for (i = 0; i+1 < n_components; i++)
 847                 if (components[i].type == components[i+1].type) {
 848                         r = -EINVAL;
 849                         goto fail;
 850                 }
 851
 852         *_components = components;
 853         *_n_components = n_components;
 854
 855         return 0;
 856
 857 fail:
 858         bus_match_parse_free(components, n_components);
 859         return r;
 860 }
 861
 862 char *bus_match_to_string(struct bus_match_component *components, unsigned n_components) {
 863         _cleanup_free_ FILE *f = NULL;
 864         char *buffer = NULL;
 865         size_t size = 0;
 866         unsigned i;
 867
 868         if (n_components <= 0)
 869                 return strdup("");
 870
 871         assert(components);
 872
 873         f = open_memstream(&buffer, &size);
 874         if (!f)
 875                 return NULL;
 876
 877         for (i = 0; i < n_components; i++) {
 878                 char buf[32];
 879
 880                 if (i != 0)
 881                         fputc(',', f);
 882
 883                 fputs(bus_match_node_type_to_string(components[i].type, buf, sizeof(buf)), f);
 884                 fputc('=', f);
 885                 fputc('\'', f);
 886
 887                 if (components[i].type == BUS_MATCH_MESSAGE_TYPE)
 888                         fputs(bus_message_type_to_string(components[i].value_u8), f);
 889                 else
 890                         fputs(components[i].value_str, f);
 891
 892                 fputc('\'', f);
 893         }
 894
 895         fflush(f);
 896         if (ferror(f))
 897                 return NULL;
 898
 899         return buffer;
 900 }
 901
 902 int bus_match_add(
 903                 struct bus_match_node *root,
 904                 struct bus_match_component *components,
 905                 unsigned n_components,
 906                 struct match_callback *callback) {
 907
 908         unsigned i;
 909         struct bus_match_node *n;
 910         int r;
 911
 912         assert(root);
 913         assert(callback);
 914
 915         n = root;
 916         for (i = 0; i < n_components; i++) {
 917                 r = bus_match_add_compare_value(
 918                                 n, components[i].type,
 919                                 components[i].value_u8, components[i].value_str, &n);
 920                 if (r < 0)
 921                         return r;
 922         }
 923
 924         return bus_match_add_leaf(n, callback);
 925 }
 926
 927 int bus_match_remove(
 928                 struct bus_match_node *root,
 929                 struct match_callback *callback) {
 930
 931         struct bus_match_node *node, *pp;
 932
 933         assert(root);
 934         assert(callback);
 935
 936         node = callback->match_node;
 937         if (!node)
 938                 return 0;
 939
 940         assert(node->type == BUS_MATCH_LEAF);
 941
 942         callback->match_node = NULL;
 943
 944         /* Free the leaf */
 945         pp = node->parent;
 946         bus_match_node_free(node);
 947
 948         /* Prune the tree above */
 949         while (pp) {
 950                 node = pp;
 951                 pp = node->parent;
 952
 953                 if (!bus_match_node_maybe_free(node))
 954                         break;
 955         }
 956
 957         return 1;
 958 }
 959
 960 int bus_match_find(
 961                 struct bus_match_node *root,
 962                 struct bus_match_component *components,
 963                 unsigned n_components,
 964                 sd_bus_message_handler_t callback,
 965                 void *userdata,
 966                 struct match_callback **ret) {
 967
 968         struct bus_match_node *n, **gc;
 969         unsigned i;
 970         int r;
 971
 972         assert(root);
 973         assert(ret);
 974
 975         gc = newa(struct bus_match_node*, n_components);
 976
 977         n = root;
 978         for (i = 0; i < n_components; i++) {
 979                 r = bus_match_find_compare_value(
 980                                 n, components[i].type,
 981                                 components[i].value_u8, components[i].value_str,
 982                                 &n);
 983                 if (r <= 0)
 984                         return r;
 985
 986                 gc[i] = n;
 987         }
 988
 989         r = bus_match_find_leaf(n, callback, userdata, &n);
 990         if (r <= 0)
 991                 return r;
 992
 993         *ret = n->leaf.callback;
 994         return 1;
 995 }
 996
 997 void bus_match_free(struct bus_match_node *node) {
 998         struct bus_match_node *c;
 999
1000         if (!node)
1001                 return;
1002
1003         if (BUS_MATCH_CAN_HASH(node->type)) {
1004                 Iterator i;
1005
1006                 HASHMAP_FOREACH(c, node->compare.children, i)
1007                         bus_match_free(c);
1008
1009                 assert(hashmap_isempty(node->compare.children));
1010         }
1011
1012         while ((c = node->child))
1013                 bus_match_free(c);
1014
1015         if (node->type != BUS_MATCH_ROOT)
1016                 bus_match_node_free(node);
1017 }
1018
1019 const char* bus_match_node_type_to_string(enum bus_match_node_type t, char buf[], size_t l) {
1020         switch (t) {
1021
1022         case BUS_MATCH_ROOT:
1023                 return "root";
1024
1025         case BUS_MATCH_VALUE:
1026                 return "value";
1027
1028         case BUS_MATCH_LEAF:
1029                 return "leaf";
1030
1031         case BUS_MATCH_MESSAGE_TYPE:
1032                 return "type";
1033
1034         case BUS_MATCH_SENDER:
1035                 return "sender";
1036
1037         case BUS_MATCH_DESTINATION:
1038                 return "destination";
1039
1040         case BUS_MATCH_INTERFACE:
1041                 return "interface";
1042
1043         case BUS_MATCH_MEMBER:
1044                 return "member";
1045
1046         case BUS_MATCH_PATH:
1047                 return "path";
1048
1049         case BUS_MATCH_PATH_NAMESPACE:
1050                 return "path_namespace";
1051
1052         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
1053                 snprintf(buf, l, "arg%i", t - BUS_MATCH_ARG);
1054                 return buf;
1055
1056         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
1057                 snprintf(buf, l, "arg%ipath", t - BUS_MATCH_ARG_PATH);
1058                 return buf;
1059
1060         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
1061                 snprintf(buf, l, "arg%inamespace", t - BUS_MATCH_ARG_NAMESPACE);
1062                 return buf;
1063
1064         default:
1065                 return NULL;
1066         }
1067 }
1068
1069 void bus_match_dump(struct bus_match_node *node, unsigned level) {
1070         struct bus_match_node *c;
1071         _cleanup_free_ char *pfx = NULL;
1072         char buf[32];
1073
1074         if (!node)
1075                 return;
1076
1077         pfx = strrep("  ", level);
1078         printf("%s[%s]", strempty(pfx), bus_match_node_type_to_string(node->type, buf, sizeof(buf)));
1079
1080         if (node->type == BUS_MATCH_VALUE) {
1081                 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
1082                         printf(" <%u>\n", node->value.u8);
1083                 else
1084                         printf(" <%s>\n", node->value.str);
1085         } else if (node->type == BUS_MATCH_ROOT)
1086                 puts(" root");
1087         else if (node->type == BUS_MATCH_LEAF)
1088                 printf(" %p/%p\n", node->leaf.callback->callback, container_of(node->leaf.callback, sd_bus_slot, match_callback)->userdata);
1089         else
1090                 putchar('\n');
1091
1092         if (BUS_MATCH_CAN_HASH(node->type)) {
1093                 Iterator i;
1094
1095                 HASHMAP_FOREACH(c, node->compare.children, i)
1096                         bus_match_dump(c, level + 1);
1097         }
1098
1099         for (c = node->child; c; c = c->next)
1100                 bus_match_dump(c, level + 1);
1101 }