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