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