ipc/kdbus/match.c

   1 /*
   2  * Copyright (C) 2013-2015 Kay Sievers
   3  * Copyright (C) 2013-2015 Greg Kroah-Hartman <gregkh@linuxfoundation.org>
   4  * Copyright (C) 2013-2015 Daniel Mack <daniel@zonque.org>
   5  * Copyright (C) 2013-2015 David Herrmann <dh.herrmann@gmail.com>
   6  * Copyright (C) 2013-2015 Linux Foundation
   7  * Copyright (C) 2014-2015 Djalal Harouni <tixxdz@opendz.org>
   8  *
   9  * kdbus is free software; you can redistribute it and/or modify it under
  10  * the terms of the GNU Lesser General Public License as published by the
  11  * Free Software Foundation; either version 2.1 of the License, or (at
  12  * your option) any later version.
  13  */
  14
  15 #include <linux/fs.h>
  16 #include <linux/hash.h>
  17 #include <linux/init.h>
  18 #include <linux/mutex.h>
  19 #include <linux/sched.h>
  20 #include <linux/sizes.h>
  21 #include <linux/slab.h>
  22 #include <linux/uaccess.h>
  23
  24 #include "bus.h"
  25 #include "connection.h"
  26 #include "endpoint.h"
  27 #include "handle.h"
  28 #include "item.h"
  29 #include "match.h"
  30 #include "message.h"
  31 #include "names.h"
  32
  33 /**
  34  * struct kdbus_match_db - message filters
  35  * @entries_list:       List of matches
  36  * @mdb_rwlock:         Match data lock
  37  * @entries_count:      Number of entries in database
  38  */
  39 struct kdbus_match_db {
  40         struct list_head entries_list;
  41         struct rw_semaphore mdb_rwlock;
  42         unsigned int entries_count;
  43 };
  44
  45 /**
  46  * struct kdbus_match_entry - a match database entry
  47  * @cookie:             User-supplied cookie to lookup the entry
  48  * @list_entry:         The list entry element for the db list
  49  * @rules_list:         The list head for tracking rules of this entry
  50  */
  51 struct kdbus_match_entry {
  52         u64 cookie;
  53         struct list_head list_entry;
  54         struct list_head rules_list;
  55 };
  56
  57 /**
  58  * struct kdbus_bloom_mask - mask to match against filter
  59  * @generations:        Number of generations carried
  60  * @data:               Array of bloom bit fields
  61  */
  62 struct kdbus_bloom_mask {
  63         u64 generations;
  64         u64 *data;
  65 };
  66
  67 /**
  68  * struct kdbus_match_rule - a rule appended to a match entry
  69  * @type:               An item type to match against
  70  * @bloom_mask:         Bloom mask to match a message's filter against, used
  71  *                      with KDBUS_ITEM_BLOOM_MASK
  72  * @name:               Name to match against, used with KDBUS_ITEM_NAME,
  73  *                      KDBUS_ITEM_NAME_{ADD,REMOVE,CHANGE}
  74  * @old_id:             ID to match against, used with
  75  *                      KDBUS_ITEM_NAME_{ADD,REMOVE,CHANGE},
  76  *                      KDBUS_ITEM_ID_REMOVE
  77  * @new_id:             ID to match against, used with
  78  *                      KDBUS_ITEM_NAME_{ADD,REMOVE,CHANGE},
  79  *                      KDBUS_ITEM_ID_REMOVE
  80  * @src_id:             ID to match against, used with KDBUS_ITEM_ID
  81  * @dst_id:             Message destination ID, used with KDBUS_ITEM_DST_ID
  82  * @rules_entry:        Entry in the entry's rules list
  83  */
  84 struct kdbus_match_rule {
  85         u64 type;
  86         union {
  87                 struct kdbus_bloom_mask bloom_mask;
  88                 struct {
  89                         char *name;
  90                         u64 old_id;
  91                         u64 new_id;
  92                 };
  93                 u64 src_id;
  94                 u64 dst_id;
  95         };
  96         struct list_head rules_entry;
  97 };
  98
  99 static void kdbus_match_rule_free(struct kdbus_match_rule *rule)
 100 {
 101         if (!rule)
 102                 return;
 103
 104         switch (rule->type) {
 105         case KDBUS_ITEM_BLOOM_MASK:
 106                 kfree(rule->bloom_mask.data);
 107                 break;
 108
 109         case KDBUS_ITEM_NAME:
 110         case KDBUS_ITEM_NAME_ADD:
 111         case KDBUS_ITEM_NAME_REMOVE:
 112         case KDBUS_ITEM_NAME_CHANGE:
 113                 kfree(rule->name);
 114                 break;
 115
 116         case KDBUS_ITEM_ID:
 117         case KDBUS_ITEM_DST_ID:
 118         case KDBUS_ITEM_ID_ADD:
 119         case KDBUS_ITEM_ID_REMOVE:
 120                 break;
 121
 122         default:
 123                 BUG();
 124         }
 125
 126         list_del(&rule->rules_entry);
 127         kfree(rule);
 128 }
 129
 130 static void kdbus_match_entry_free(struct kdbus_match_entry *entry)
 131 {
 132         struct kdbus_match_rule *r, *tmp;
 133
 134         if (!entry)
 135                 return;
 136
 137         list_for_each_entry_safe(r, tmp, &entry->rules_list, rules_entry)
 138                 kdbus_match_rule_free(r);
 139
 140         list_del(&entry->list_entry);
 141         kfree(entry);
 142 }
 143
 144 /**
 145  * kdbus_match_db_free() - free match db resources
 146  * @mdb:                The match database
 147  */
 148 void kdbus_match_db_free(struct kdbus_match_db *mdb)
 149 {
 150         struct kdbus_match_entry *entry, *tmp;
 151
 152         if (!mdb)
 153                 return;
 154
 155         list_for_each_entry_safe(entry, tmp, &mdb->entries_list, list_entry)
 156                 kdbus_match_entry_free(entry);
 157
 158         kfree(mdb);
 159 }
 160
 161 /**
 162  * kdbus_match_db_new() - create a new match database
 163  *
 164  * Return: a new kdbus_match_db on success, ERR_PTR on failure.
 165  */
 166 struct kdbus_match_db *kdbus_match_db_new(void)
 167 {
 168         struct kdbus_match_db *d;
 169
 170         d = kzalloc(sizeof(*d), GFP_KERNEL);
 171         if (!d)
 172                 return ERR_PTR(-ENOMEM);
 173
 174         init_rwsem(&d->mdb_rwlock);
 175         INIT_LIST_HEAD(&d->entries_list);
 176
 177         return d;
 178 }
 179
 180 static bool kdbus_match_bloom(const struct kdbus_bloom_filter *filter,
 181                               const struct kdbus_bloom_mask *mask,
 182                               const struct kdbus_conn *conn)
 183 {
 184         size_t n = conn->ep->bus->bloom.size / sizeof(u64);
 185         const u64 *m;
 186         size_t i;
 187
 188         /*
 189          * The message's filter carries a generation identifier, the
 190          * match's mask possibly carries an array of multiple generations
 191          * of the mask. Select the mask with the closest match of the
 192          * filter's generation.
 193          */
 194         m = mask->data + (min(filter->generation, mask->generations - 1) * n);
 195
 196         /*
 197          * The message's filter contains the messages properties,
 198          * the match's mask contains the properties to look for in the
 199          * message. Check the mask bit field against the filter bit field,
 200          * if the message possibly carries the properties the connection
 201          * has subscribed to.
 202          */
 203         for (i = 0; i < n; i++)
 204                 if ((filter->data[i] & m[i]) != m[i])
 205                         return false;
 206
 207         return true;
 208 }
 209
 210 static bool kdbus_match_rule_conn(const struct kdbus_match_rule *r,
 211                                   struct kdbus_conn *c,
 212                                   const struct kdbus_staging *s)
 213 {
 214         lockdep_assert_held(&c->ep->bus->name_registry->rwlock);
 215
 216         switch (r->type) {
 217         case KDBUS_ITEM_BLOOM_MASK:
 218                 return kdbus_match_bloom(s->bloom_filter, &r->bloom_mask, c);
 219         case KDBUS_ITEM_ID:
 220                 return r->src_id == c->id || r->src_id == KDBUS_MATCH_ID_ANY;
 221         case KDBUS_ITEM_DST_ID:
 222                 return r->dst_id == s->msg->dst_id ||
 223                        r->dst_id == KDBUS_MATCH_ID_ANY;
 224         case KDBUS_ITEM_NAME:
 225                 return kdbus_conn_has_name(c, r->name);
 226         default:
 227                 return false;
 228         }
 229 }
 230
 231 static bool kdbus_match_rule_kernel(const struct kdbus_match_rule *r,
 232                                     const struct kdbus_staging *s)
 233 {
 234         struct kdbus_item *n = s->notify;
 235
 236         if (WARN_ON(!n) || n->type != r->type)
 237                 return false;
 238
 239         switch (r->type) {
 240         case KDBUS_ITEM_ID_ADD:
 241                 return r->new_id == KDBUS_MATCH_ID_ANY ||
 242                        r->new_id == n->id_change.id;
 243         case KDBUS_ITEM_ID_REMOVE:
 244                 return r->old_id == KDBUS_MATCH_ID_ANY ||
 245                        r->old_id == n->id_change.id;
 246         case KDBUS_ITEM_NAME_ADD:
 247         case KDBUS_ITEM_NAME_CHANGE:
 248         case KDBUS_ITEM_NAME_REMOVE:
 249                 return (r->old_id == KDBUS_MATCH_ID_ANY ||
 250                         r->old_id == n->name_change.old_id.id) &&
 251                        (r->new_id == KDBUS_MATCH_ID_ANY ||
 252                         r->new_id == n->name_change.new_id.id) &&
 253                        (!r->name || !strcmp(r->name, n->name_change.name));
 254         default:
 255                 return false;
 256         }
 257 }
 258
 259 static bool kdbus_match_rules(const struct kdbus_match_entry *entry,
 260                               struct kdbus_conn *c,
 261                               const struct kdbus_staging *s)
 262 {
 263         struct kdbus_match_rule *r;
 264
 265         list_for_each_entry(r, &entry->rules_list, rules_entry)
 266                 if ((c && !kdbus_match_rule_conn(r, c, s)) ||
 267                     (!c && !kdbus_match_rule_kernel(r, s)))
 268                         return false;
 269
 270         return true;
 271 }
 272
 273 /**
 274  * kdbus_match_db_match_msg() - match a msg object agains the database entries
 275  * @mdb:                The match database
 276  * @conn_src:           The connection object originating the message
 277  * @staging:            Staging object containing the message to match against
 278  *
 279  * This function will walk through all the database entries previously uploaded
 280  * with kdbus_match_db_add(). As soon as any of them has an all-satisfied rule
 281  * set, this function will return true.
 282  *
 283  * The caller must hold the registry lock of conn_src->ep->bus, in case conn_src
 284  * is non-NULL.
 285  *
 286  * Return: true if there was a matching database entry, false otherwise.
 287  */
 288 bool kdbus_match_db_match_msg(struct kdbus_match_db *mdb,
 289                               struct kdbus_conn *conn_src,
 290                               const struct kdbus_staging *staging)
 291 {
 292         struct kdbus_match_entry *entry;
 293         bool matched = false;
 294
 295         down_read(&mdb->mdb_rwlock);
 296         list_for_each_entry(entry, &mdb->entries_list, list_entry) {
 297                 matched = kdbus_match_rules(entry, conn_src, staging);
 298                 if (matched)
 299                         break;
 300         }
 301         up_read(&mdb->mdb_rwlock);
 302
 303         return matched;
 304 }
 305
 306 static int kdbus_match_db_remove_unlocked(struct kdbus_match_db *mdb,
 307                                           u64 cookie)
 308 {
 309         struct kdbus_match_entry *entry, *tmp;
 310         bool found = false;
 311
 312         list_for_each_entry_safe(entry, tmp, &mdb->entries_list, list_entry)
 313                 if (entry->cookie == cookie) {
 314                         kdbus_match_entry_free(entry);
 315                         --mdb->entries_count;
 316                         found = true;
 317                 }
 318
 319         return found ? 0 : -EBADSLT;
 320 }
 321
 322 /**
 323  * kdbus_cmd_match_add() - handle KDBUS_CMD_MATCH_ADD
 324  * @conn:               connection to operate on
 325  * @argp:               command payload
 326  *
 327  * One call to this function (or one ioctl(KDBUS_CMD_MATCH_ADD), respectively,
 328  * adds one new database entry with n rules attached to it. Each rule is
 329  * described with an kdbus_item, and an entry is considered matching if all
 330  * its rules are satisfied.
 331  *
 332  * The items attached to a kdbus_cmd_match struct have the following mapping:
 333  *
 334  * KDBUS_ITEM_BLOOM_MASK:       A bloom mask
 335  * KDBUS_ITEM_NAME:             A connection's source name
 336  * KDBUS_ITEM_ID:               A connection ID
 337  * KDBUS_ITEM_DST_ID:           A connection ID
 338  * KDBUS_ITEM_NAME_ADD:
 339  * KDBUS_ITEM_NAME_REMOVE:
 340  * KDBUS_ITEM_NAME_CHANGE:      Well-known name changes, carry
 341  *                              kdbus_notify_name_change
 342  * KDBUS_ITEM_ID_ADD:
 343  * KDBUS_ITEM_ID_REMOVE:        Connection ID changes, carry
 344  *                              kdbus_notify_id_change
 345  *
 346  * For kdbus_notify_{id,name}_change structs, only the ID and name fields
 347  * are looked at when adding an entry. The flags are unused.
 348  *
 349  * Also note that KDBUS_ITEM_BLOOM_MASK, KDBUS_ITEM_NAME, KDBUS_ITEM_ID,
 350  * and KDBUS_ITEM_DST_ID are used to match messages from userspace, while the
 351  * others apply to kernel-generated notifications.
 352  *
 353  * Return: >=0 on success, negative error code on failure.
 354  */
 355 int kdbus_cmd_match_add(struct kdbus_conn *conn, void __user *argp)
 356 {
 357         struct kdbus_match_db *mdb = conn->match_db;
 358         struct kdbus_match_entry *entry = NULL;
 359         struct kdbus_cmd_match *cmd;
 360         struct kdbus_item *item;
 361         int ret;
 362
 363         struct kdbus_arg argv[] = {
 364                 { .type = KDBUS_ITEM_NEGOTIATE },
 365                 { .type = KDBUS_ITEM_BLOOM_MASK, .multiple = true },
 366                 { .type = KDBUS_ITEM_NAME, .multiple = true },
 367                 { .type = KDBUS_ITEM_ID, .multiple = true },
 368                 { .type = KDBUS_ITEM_DST_ID, .multiple = true },
 369                 { .type = KDBUS_ITEM_NAME_ADD, .multiple = true },
 370                 { .type = KDBUS_ITEM_NAME_REMOVE, .multiple = true },
 371                 { .type = KDBUS_ITEM_NAME_CHANGE, .multiple = true },
 372                 { .type = KDBUS_ITEM_ID_ADD, .multiple = true },
 373                 { .type = KDBUS_ITEM_ID_REMOVE, .multiple = true },
 374         };
 375         struct kdbus_args args = {
 376                 .allowed_flags = KDBUS_FLAG_NEGOTIATE |
 377                                  KDBUS_MATCH_REPLACE,
 378                 .argv = argv,
 379                 .argc = ARRAY_SIZE(argv),
 380         };
 381
 382         if (!kdbus_conn_is_ordinary(conn))
 383                 return -EOPNOTSUPP;
 384
 385         ret = kdbus_args_parse(&args, argp, &cmd);
 386         if (ret != 0)
 387                 return ret;
 388
 389         entry = kzalloc(sizeof(*entry), GFP_KERNEL);
 390         if (!entry) {
 391                 ret = -ENOMEM;
 392                 goto exit;
 393         }
 394
 395         entry->cookie = cmd->cookie;
 396         INIT_LIST_HEAD(&entry->list_entry);
 397         INIT_LIST_HEAD(&entry->rules_list);
 398
 399         KDBUS_ITEMS_FOREACH(item, cmd->items, KDBUS_ITEMS_SIZE(cmd, items)) {
 400                 struct kdbus_match_rule *rule;
 401                 size_t size = item->size - offsetof(struct kdbus_item, data);
 402
 403                 rule = kzalloc(sizeof(*rule), GFP_KERNEL);
 404                 if (!rule) {
 405                         ret = -ENOMEM;
 406                         goto exit;
 407                 }
 408
 409                 rule->type = item->type;
 410                 INIT_LIST_HEAD(&rule->rules_entry);
 411
 412                 switch (item->type) {
 413                 case KDBUS_ITEM_BLOOM_MASK: {
 414                         u64 bsize = conn->ep->bus->bloom.size;
 415                         u64 generations;
 416                         u64 remainder;
 417
 418                         generations = div64_u64_rem(size, bsize, &remainder);
 419                         if (size < bsize || remainder > 0) {
 420                                 ret = -EDOM;
 421                                 break;
 422                         }
 423
 424                         rule->bloom_mask.data = kmemdup(item->data,
 425                                                         size, GFP_KERNEL);
 426                         if (!rule->bloom_mask.data) {
 427                                 ret = -ENOMEM;
 428                                 break;
 429                         }
 430
 431                         rule->bloom_mask.generations = generations;
 432                         break;
 433                 }
 434
 435                 case KDBUS_ITEM_NAME:
 436                         if (!kdbus_name_is_valid(item->str, false)) {
 437                                 ret = -EINVAL;
 438                                 break;
 439                         }
 440
 441                         rule->name = kstrdup(item->str, GFP_KERNEL);
 442                         if (!rule->name)
 443                                 ret = -ENOMEM;
 444
 445                         break;
 446
 447                 case KDBUS_ITEM_ID:
 448                         rule->src_id = item->id;
 449                         break;
 450
 451                 case KDBUS_ITEM_DST_ID:
 452                         rule->dst_id = item->id;
 453                         break;
 454
 455                 case KDBUS_ITEM_NAME_ADD:
 456                 case KDBUS_ITEM_NAME_REMOVE:
 457                 case KDBUS_ITEM_NAME_CHANGE:
 458                         rule->old_id = item->name_change.old_id.id;
 459                         rule->new_id = item->name_change.new_id.id;
 460
 461                         if (size > sizeof(struct kdbus_notify_name_change)) {
 462                                 rule->name = kstrdup(item->name_change.name,
 463                                                      GFP_KERNEL);
 464                                 if (!rule->name)
 465                                         ret = -ENOMEM;
 466                         }
 467
 468                         break;
 469
 470                 case KDBUS_ITEM_ID_ADD:
 471                 case KDBUS_ITEM_ID_REMOVE:
 472                         if (item->type == KDBUS_ITEM_ID_ADD)
 473                                 rule->new_id = item->id_change.id;
 474                         else
 475                                 rule->old_id = item->id_change.id;
 476
 477                         break;
 478                 }
 479
 480                 if (ret < 0) {
 481                         kdbus_match_rule_free(rule);
 482                         goto exit;
 483                 }
 484
 485                 list_add_tail(&rule->rules_entry, &entry->rules_list);
 486         }
 487
 488         down_write(&mdb->mdb_rwlock);
 489
 490         /* Remove any entry that has the same cookie as the current one. */
 491         if (cmd->flags & KDBUS_MATCH_REPLACE)
 492                 kdbus_match_db_remove_unlocked(mdb, entry->cookie);
 493
 494         /*
 495          * If the above removal caught any entry, there will be room for the
 496          * new one.
 497          */
 498         if (++mdb->entries_count > KDBUS_MATCH_MAX) {
 499                 --mdb->entries_count;
 500                 ret = -EMFILE;
 501         } else {
 502                 list_add_tail(&entry->list_entry, &mdb->entries_list);
 503                 entry = NULL;
 504         }
 505
 506         up_write(&mdb->mdb_rwlock);
 507
 508 exit:
 509         kdbus_match_entry_free(entry);
 510         return kdbus_args_clear(&args, ret);
 511 }
 512
 513 /**
 514  * kdbus_cmd_match_remove() - handle KDBUS_CMD_MATCH_REMOVE
 515  * @conn:               connection to operate on
 516  * @argp:               command payload
 517  *
 518  * Return: >=0 on success, negative error code on failure.
 519  */
 520 int kdbus_cmd_match_remove(struct kdbus_conn *conn, void __user *argp)
 521 {
 522         struct kdbus_cmd_match *cmd;
 523         int ret;
 524
 525         struct kdbus_arg argv[] = {
 526                 { .type = KDBUS_ITEM_NEGOTIATE },
 527         };
 528         struct kdbus_args args = {
 529                 .allowed_flags = KDBUS_FLAG_NEGOTIATE,
 530                 .argv = argv,
 531                 .argc = ARRAY_SIZE(argv),
 532         };
 533
 534         if (!kdbus_conn_is_ordinary(conn))
 535                 return -EOPNOTSUPP;
 536
 537         ret = kdbus_args_parse(&args, argp, &cmd);
 538         if (ret != 0)
 539                 return ret;
 540
 541         down_write(&conn->match_db->mdb_rwlock);
 542         ret = kdbus_match_db_remove_unlocked(conn->match_db, cmd->cookie);
 543         up_write(&conn->match_db->mdb_rwlock);
 544
 545         return kdbus_args_clear(&args, ret);
 546 }