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(trivial_hash_func, trivial_compare_func);
 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_func, string_compare_func);
 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; !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                 eq = strchr(p, '=');
 752                 if (!eq)
 753                         return -EINVAL;
 754
 755                 t = bus_match_node_type_from_string(p, eq - p);
 756                 if (t < 0)
 757                         return -EINVAL;
 758
 759                 quoted = eq[1] == '\'';
 760
 761                 for (q = eq + 1 + quoted;; q++) {
 762
 763                         if (*q == 0) {
 764
 765                                 if (quoted) {
 766                                         r = -EINVAL;
 767                                         goto fail;
 768                                 } else {
 769                                         if (value)
 770                                                 value[j] = 0;
 771                                         break;
 772                                 }
 773                         }
 774
 775                         if (!escaped) {
 776                                 if (*q == '\\') {
 777                                         escaped = true;
 778                                         continue;
 779                                 }
 780
 781                                 if (quoted) {
 782                                         if (*q == '\'') {
 783                                                 if (value)
 784                                                         value[j] = 0;
 785                                                 break;
 786                                         }
 787                                 } else {
 788                                         if (*q == ',') {
 789                                                 if (value)
 790                                                         value[j] = 0;
 791
 792                                                 break;
 793                                         }
 794                                 }
 795                         }
 796
 797                         if (!GREEDY_REALLOC(value, value_allocated, j + 2)) {
 798                                 r = -ENOMEM;
 799                                 goto fail;
 800                         }
 801
 802                         value[j++] = *q;
 803                         escaped = false;
 804                 }
 805
 806                 if (!value) {
 807                         value = strdup("");
 808                         if (!value) {
 809                                 r = -ENOMEM;
 810                                 goto fail;
 811                         }
 812                 }
 813
 814                 if (t == BUS_MATCH_MESSAGE_TYPE) {
 815                         r = bus_message_type_from_string(value, &u);
 816                         if (r < 0)
 817                                 goto fail;
 818
 819                         free(value);
 820                         value = NULL;
 821                 } else
 822                         u = 0;
 823
 824                 if (!GREEDY_REALLOC(components, components_allocated, n_components + 1)) {
 825                         r = -ENOMEM;
 826                         goto fail;
 827                 }
 828
 829                 components[n_components].type = t;
 830                 components[n_components].value_str = value;
 831                 components[n_components].value_u8 = u;
 832                 n_components++;
 833
 834                 value = NULL;
 835
 836                 if (q[quoted] == 0)
 837                         break;
 838
 839                 if (q[quoted] != ',') {
 840                         r = -EINVAL;
 841                         goto fail;
 842                 }
 843
 844                 p = q + 1 + quoted;
 845         }
 846
 847         /* Order the whole thing, so that we always generate the same tree */
 848         qsort_safe(components, n_components, sizeof(struct bus_match_component), match_component_compare);
 849
 850         /* Check for duplicates */
 851         for (i = 0; i+1 < n_components; i++)
 852                 if (components[i].type == components[i+1].type) {
 853                         r = -EINVAL;
 854                         goto fail;
 855                 }
 856
 857         *_components = components;
 858         *_n_components = n_components;
 859
 860         return 0;
 861
 862 fail:
 863         bus_match_parse_free(components, n_components);
 864         return r;
 865 }
 866
 867 char *bus_match_to_string(struct bus_match_component *components, unsigned n_components) {
 868         _cleanup_free_ FILE *f = NULL;
 869         char *buffer = NULL;
 870         size_t size = 0;
 871         unsigned i;
 872
 873         if (n_components <= 0)
 874                 return strdup("");
 875
 876         assert(components);
 877
 878         f = open_memstream(&buffer, &size);
 879         if (!f)
 880                 return NULL;
 881
 882         for (i = 0; i < n_components; i++) {
 883                 char buf[32];
 884
 885                 if (i != 0)
 886                         fputc(',', f);
 887
 888                 fputs(bus_match_node_type_to_string(components[i].type, buf, sizeof(buf)), f);
 889                 fputc('=', f);
 890                 fputc('\'', f);
 891
 892                 if (components[i].type == BUS_MATCH_MESSAGE_TYPE)
 893                         fputs(bus_message_type_to_string(components[i].value_u8), f);
 894                 else
 895                         fputs(components[i].value_str, f);
 896
 897                 fputc('\'', f);
 898         }
 899
 900         fflush(f);
 901         if (ferror(f))
 902                 return NULL;
 903
 904         return buffer;
 905 }
 906
 907 int bus_match_add(
 908                 struct bus_match_node *root,
 909                 struct bus_match_component *components,
 910                 unsigned n_components,
 911                 struct match_callback *callback) {
 912
 913         unsigned i;
 914         struct bus_match_node *n;
 915         int r;
 916
 917         assert(root);
 918         assert(callback);
 919
 920         n = root;
 921         for (i = 0; i < n_components; i++) {
 922                 r = bus_match_add_compare_value(
 923                                 n, components[i].type,
 924                                 components[i].value_u8, components[i].value_str, &n);
 925                 if (r < 0)
 926                         return r;
 927         }
 928
 929         return bus_match_add_leaf(n, callback);
 930 }
 931
 932 int bus_match_remove(
 933                 struct bus_match_node *root,
 934                 struct match_callback *callback) {
 935
 936         struct bus_match_node *node, *pp;
 937
 938         assert(root);
 939         assert(callback);
 940
 941         node = callback->match_node;
 942         if (!node)
 943                 return 0;
 944
 945         assert(node->type == BUS_MATCH_LEAF);
 946
 947         callback->match_node = NULL;
 948
 949         /* Free the leaf */
 950         pp = node->parent;
 951         bus_match_node_free(node);
 952
 953         /* Prune the tree above */
 954         while (pp) {
 955                 node = pp;
 956                 pp = node->parent;
 957
 958                 if (!bus_match_node_maybe_free(node))
 959                         break;
 960         }
 961
 962         return 1;
 963 }
 964
 965 int bus_match_find(
 966                 struct bus_match_node *root,
 967                 struct bus_match_component *components,
 968                 unsigned n_components,
 969                 sd_bus_message_handler_t callback,
 970                 void *userdata,
 971                 struct match_callback **ret) {
 972
 973         struct bus_match_node *n, **gc;
 974         unsigned i;
 975         int r;
 976
 977         assert(root);
 978         assert(ret);
 979
 980         gc = newa(struct bus_match_node*, n_components);
 981
 982         n = root;
 983         for (i = 0; i < n_components; i++) {
 984                 r = bus_match_find_compare_value(
 985                                 n, components[i].type,
 986                                 components[i].value_u8, components[i].value_str,
 987                                 &n);
 988                 if (r <= 0)
 989                         return r;
 990
 991                 gc[i] = n;
 992         }
 993
 994         r = bus_match_find_leaf(n, callback, userdata, &n);
 995         if (r <= 0)
 996                 return r;
 997
 998         *ret = n->leaf.callback;
 999         return 1;
1000 }
1001
1002 void bus_match_free(struct bus_match_node *node) {
1003         struct bus_match_node *c;
1004
1005         if (!node)
1006                 return;
1007
1008         if (BUS_MATCH_CAN_HASH(node->type)) {
1009                 Iterator i;
1010
1011                 HASHMAP_FOREACH(c, node->compare.children, i)
1012                         bus_match_free(c);
1013
1014                 assert(hashmap_isempty(node->compare.children));
1015         }
1016
1017         while ((c = node->child))
1018                 bus_match_free(c);
1019
1020         if (node->type != BUS_MATCH_ROOT)
1021                 bus_match_node_free(node);
1022 }
1023
1024 const char* bus_match_node_type_to_string(enum bus_match_node_type t, char buf[], size_t l) {
1025         switch (t) {
1026
1027         case BUS_MATCH_ROOT:
1028                 return "root";
1029
1030         case BUS_MATCH_VALUE:
1031                 return "value";
1032
1033         case BUS_MATCH_LEAF:
1034                 return "leaf";
1035
1036         case BUS_MATCH_MESSAGE_TYPE:
1037                 return "type";
1038
1039         case BUS_MATCH_SENDER:
1040                 return "sender";
1041
1042         case BUS_MATCH_DESTINATION:
1043                 return "destination";
1044
1045         case BUS_MATCH_INTERFACE:
1046                 return "interface";
1047
1048         case BUS_MATCH_MEMBER:
1049                 return "member";
1050
1051         case BUS_MATCH_PATH:
1052                 return "path";
1053
1054         case BUS_MATCH_PATH_NAMESPACE:
1055                 return "path_namespace";
1056
1057         case BUS_MATCH_ARG ... BUS_MATCH_ARG_LAST:
1058                 snprintf(buf, l, "arg%i", t - BUS_MATCH_ARG);
1059                 return buf;
1060
1061         case BUS_MATCH_ARG_PATH ... BUS_MATCH_ARG_PATH_LAST:
1062                 snprintf(buf, l, "arg%ipath", t - BUS_MATCH_ARG_PATH);
1063                 return buf;
1064
1065         case BUS_MATCH_ARG_NAMESPACE ... BUS_MATCH_ARG_NAMESPACE_LAST:
1066                 snprintf(buf, l, "arg%inamespace", t - BUS_MATCH_ARG_NAMESPACE);
1067                 return buf;
1068
1069         default:
1070                 return NULL;
1071         }
1072 }
1073
1074 void bus_match_dump(struct bus_match_node *node, unsigned level) {
1075         struct bus_match_node *c;
1076         _cleanup_free_ char *pfx = NULL;
1077         char buf[32];
1078
1079         if (!node)
1080                 return;
1081
1082         pfx = strrep("  ", level);
1083         printf("%s[%s]", strempty(pfx), bus_match_node_type_to_string(node->type, buf, sizeof(buf)));
1084
1085         if (node->type == BUS_MATCH_VALUE) {
1086                 if (node->parent->type == BUS_MATCH_MESSAGE_TYPE)
1087                         printf(" <%u>\n", node->value.u8);
1088                 else
1089                         printf(" <%s>\n", node->value.str);
1090         } else if (node->type == BUS_MATCH_ROOT)
1091                 puts(" root");
1092         else if (node->type == BUS_MATCH_LEAF)
1093                 printf(" %p/%p\n", node->leaf.callback->callback, container_of(node->leaf.callback, sd_bus_slot, match_callback)->userdata);
1094         else
1095                 putchar('\n');
1096
1097         if (BUS_MATCH_CAN_HASH(node->type)) {
1098                 Iterator i;
1099
1100                 HASHMAP_FOREACH(c, node->compare.children, i)
1101                         bus_match_dump(c, level + 1);
1102         }
1103
1104         for (c = node->child; c; c = c->next)
1105                 bus_match_dump(c, level + 1);
1106 }