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