ipc/kdbus/queue.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/audit.h>
  16 #include <linux/file.h>
  17 #include <linux/fs.h>
  18 #include <linux/hashtable.h>
  19 #include <linux/idr.h>
  20 #include <linux/init.h>
  21 #include <linux/math64.h>
  22 #include <linux/mm.h>
  23 #include <linux/module.h>
  24 #include <linux/mutex.h>
  25 #include <linux/poll.h>
  26 #include <linux/sched.h>
  27 #include <linux/sizes.h>
  28 #include <linux/slab.h>
  29 #include <linux/syscalls.h>
  30 #include <linux/uio.h>
  31
  32 #include "util.h"
  33 #include "domain.h"
  34 #include "connection.h"
  35 #include "item.h"
  36 #include "message.h"
  37 #include "metadata.h"
  38 #include "queue.h"
  39 #include "reply.h"
  40
  41 /**
  42  * kdbus_queue_init() - initialize data structure related to a queue
  43  * @queue:      The queue to initialize
  44  */
  45 void kdbus_queue_init(struct kdbus_queue *queue)
  46 {
  47         INIT_LIST_HEAD(&queue->msg_list);
  48         queue->msg_prio_queue = RB_ROOT;
  49 }
  50
  51 /**
  52  * kdbus_queue_peek() - Retrieves an entry from a queue
  53  * @queue:              The queue
  54  * @priority:           The minimum priority of the entry to peek
  55  * @use_priority:       Boolean flag whether or not to peek by priority
  56  *
  57  * Look for a entry in a queue, either by priority, or the oldest one (FIFO).
  58  * The entry is not freed, put off the queue's lists or anything else.
  59  *
  60  * Return: the peeked queue entry on success, NULL if no suitable msg is found
  61  */
  62 struct kdbus_queue_entry *kdbus_queue_peek(struct kdbus_queue *queue,
  63                                            s64 priority, bool use_priority)
  64 {
  65         struct kdbus_queue_entry *e;
  66
  67         if (list_empty(&queue->msg_list))
  68                 return NULL;
  69
  70         if (use_priority) {
  71                 /* get next entry with highest priority */
  72                 e = rb_entry(queue->msg_prio_highest,
  73                              struct kdbus_queue_entry, prio_node);
  74
  75                 /* no entry with the requested priority */
  76                 if (e->priority > priority)
  77                         return NULL;
  78         } else {
  79                 /* ignore the priority, return the next entry in the entry */
  80                 e = list_first_entry(&queue->msg_list,
  81                                      struct kdbus_queue_entry, entry);
  82         }
  83
  84         return e;
  85 }
  86
  87 static void kdbus_queue_entry_link(struct kdbus_queue_entry *entry)
  88 {
  89         struct kdbus_queue *queue = &entry->conn->queue;
  90         struct rb_node **n, *pn = NULL;
  91         bool highest = true;
  92
  93         lockdep_assert_held(&entry->conn->lock);
  94         if (WARN_ON(!list_empty(&entry->entry)))
  95                 return;
  96
  97         /* sort into priority entry tree */
  98         n = &queue->msg_prio_queue.rb_node;
  99         while (*n) {
 100                 struct kdbus_queue_entry *e;
 101
 102                 pn = *n;
 103                 e = rb_entry(pn, struct kdbus_queue_entry, prio_node);
 104
 105                 /* existing node for this priority, add to its list */
 106                 if (likely(entry->priority == e->priority)) {
 107                         list_add_tail(&entry->prio_entry, &e->prio_entry);
 108                         goto prio_done;
 109                 }
 110
 111                 if (entry->priority < e->priority) {
 112                         n = &pn->rb_left;
 113                 } else {
 114                         n = &pn->rb_right;
 115                         highest = false;
 116                 }
 117         }
 118
 119         /* cache highest-priority entry */
 120         if (highest)
 121                 queue->msg_prio_highest = &entry->prio_node;
 122
 123         /* new node for this priority */
 124         rb_link_node(&entry->prio_node, pn, n);
 125         rb_insert_color(&entry->prio_node, &queue->msg_prio_queue);
 126         INIT_LIST_HEAD(&entry->prio_entry);
 127
 128 prio_done:
 129         /* add to unsorted fifo list */
 130         list_add_tail(&entry->entry, &queue->msg_list);
 131 }
 132
 133 static void kdbus_queue_entry_unlink(struct kdbus_queue_entry *entry)
 134 {
 135         struct kdbus_queue *queue = &entry->conn->queue;
 136
 137         lockdep_assert_held(&entry->conn->lock);
 138         if (list_empty(&entry->entry))
 139                 return;
 140
 141         list_del_init(&entry->entry);
 142
 143         if (list_empty(&entry->prio_entry)) {
 144                 /*
 145                  * Single entry for this priority, update cached
 146                  * highest-priority entry, remove the tree node.
 147                  */
 148                 if (queue->msg_prio_highest == &entry->prio_node)
 149                         queue->msg_prio_highest = rb_next(&entry->prio_node);
 150
 151                 rb_erase(&entry->prio_node, &queue->msg_prio_queue);
 152         } else {
 153                 struct kdbus_queue_entry *q;
 154
 155                 /*
 156                  * Multiple entries for this priority entry, get next one in
 157                  * the list. Update cached highest-priority entry, store the
 158                  * new one as the tree node.
 159                  */
 160                 q = list_first_entry(&entry->prio_entry,
 161                                      struct kdbus_queue_entry, prio_entry);
 162                 list_del(&entry->prio_entry);
 163
 164                 if (queue->msg_prio_highest == &entry->prio_node)
 165                         queue->msg_prio_highest = &q->prio_node;
 166
 167                 rb_replace_node(&entry->prio_node, &q->prio_node,
 168                                 &queue->msg_prio_queue);
 169         }
 170 }
 171
 172 /**
 173  * kdbus_queue_entry_new() - allocate a queue entry
 174  * @src:        source connection, or NULL
 175  * @dst:        destination connection
 176  * @s:          staging object carrying the message
 177  *
 178  * Allocates a queue entry based on a given msg and allocate space for
 179  * the message payload and the requested metadata in the connection's pool.
 180  * The entry is not actually added to the queue's lists at this point.
 181  *
 182  * Return: the allocated entry on success, or an ERR_PTR on failures.
 183  */
 184 struct kdbus_queue_entry *kdbus_queue_entry_new(struct kdbus_conn *src,
 185                                                 struct kdbus_conn *dst,
 186                                                 struct kdbus_staging *s)
 187 {
 188         struct kdbus_queue_entry *entry;
 189         int ret;
 190
 191         entry = kzalloc(sizeof(*entry), GFP_KERNEL);
 192         if (!entry)
 193                 return ERR_PTR(-ENOMEM);
 194
 195         INIT_LIST_HEAD(&entry->entry);
 196         entry->priority = s->msg->priority;
 197         entry->conn = kdbus_conn_ref(dst);
 198         entry->gaps = kdbus_gaps_ref(s->gaps);
 199
 200         entry->slice = kdbus_staging_emit(s, src, dst);
 201         if (IS_ERR(entry->slice)) {
 202                 ret = PTR_ERR(entry->slice);
 203                 entry->slice = NULL;
 204                 goto error;
 205         }
 206
 207         entry->user = src ? kdbus_user_ref(src->user) : NULL;
 208         return entry;
 209
 210 error:
 211         kdbus_queue_entry_free(entry);
 212         return ERR_PTR(ret);
 213 }
 214
 215 /**
 216  * kdbus_queue_entry_free() - free resources of an entry
 217  * @entry:      The entry to free
 218  *
 219  * Removes resources allocated by a queue entry, along with the entry itself.
 220  * Note that the entry's slice is not freed at this point.
 221  */
 222 void kdbus_queue_entry_free(struct kdbus_queue_entry *entry)
 223 {
 224         if (!entry)
 225                 return;
 226
 227         lockdep_assert_held(&entry->conn->lock);
 228
 229         kdbus_queue_entry_unlink(entry);
 230         kdbus_reply_unref(entry->reply);
 231
 232         if (entry->slice) {
 233                 kdbus_conn_quota_dec(entry->conn, entry->user,
 234                                      kdbus_pool_slice_size(entry->slice),
 235                                      entry->gaps ? entry->gaps->n_fds : 0);
 236                 kdbus_pool_slice_release(entry->slice);
 237         }
 238
 239         kdbus_user_unref(entry->user);
 240         kdbus_gaps_unref(entry->gaps);
 241         kdbus_conn_unref(entry->conn);
 242         kfree(entry);
 243 }
 244
 245 /**
 246  * kdbus_queue_entry_install() - install message components into the
 247  *                               receiver's process
 248  * @entry:              The queue entry to install
 249  * @return_flags:       Pointer to store the return flags for userspace
 250  * @install_fds:        Whether or not to install associated file descriptors
 251  *
 252  * Return: 0 on success.
 253  */
 254 int kdbus_queue_entry_install(struct kdbus_queue_entry *entry,
 255                               u64 *return_flags, bool install_fds)
 256 {
 257         bool incomplete_fds = false;
 258         int ret;
 259
 260         lockdep_assert_held(&entry->conn->lock);
 261
 262         ret = kdbus_gaps_install(entry->gaps, entry->slice, &incomplete_fds);
 263         if (ret < 0)
 264                 return ret;
 265
 266         if (incomplete_fds)
 267                 *return_flags |= KDBUS_RECV_RETURN_INCOMPLETE_FDS;
 268         return 0;
 269 }
 270
 271 /**
 272  * kdbus_queue_entry_enqueue() - enqueue an entry
 273  * @entry:              entry to enqueue
 274  * @reply:              reply to link to this entry (or NULL if none)
 275  *
 276  * This enqueues an unqueued entry into the message queue of the linked
 277  * connection. It also binds a reply object to the entry so we can remember it
 278  * when the message is moved.
 279  *
 280  * Once this call returns (and the connection lock is released), this entry can
 281  * be dequeued by the target connection. Note that the entry will not be removed
 282  * from the queue until it is destroyed.
 283  */
 284 void kdbus_queue_entry_enqueue(struct kdbus_queue_entry *entry,
 285                                struct kdbus_reply *reply)
 286 {
 287         lockdep_assert_held(&entry->conn->lock);
 288
 289         if (WARN_ON(entry->reply) || WARN_ON(!list_empty(&entry->entry)))
 290                 return;
 291
 292         entry->reply = kdbus_reply_ref(reply);
 293         kdbus_queue_entry_link(entry);
 294 }
 295
 296 /**
 297  * kdbus_queue_entry_move() - move queue entry
 298  * @e:          queue entry to move
 299  * @dst:        destination connection to queue the entry on
 300  *
 301  * This moves a queue entry onto a different connection. It allocates a new
 302  * slice on the target connection and copies the message over. If the copy
 303  * succeeded, we move the entry from @src to @dst.
 304  *
 305  * On failure, the entry is left untouched.
 306  *
 307  * The queue entry must be queued right now, and after the call succeeds it will
 308  * be queued on the destination, but no longer on the source.
 309  *
 310  * The caller must hold the connection lock of the source *and* destination.
 311  *
 312  * Return: 0 on success, negative error code on failure.
 313  */
 314 int kdbus_queue_entry_move(struct kdbus_queue_entry *e,
 315                            struct kdbus_conn *dst)
 316 {
 317         struct kdbus_pool_slice *slice = NULL;
 318         struct kdbus_conn *src = e->conn;
 319         size_t size, fds;
 320         int ret;
 321
 322         lockdep_assert_held(&src->lock);
 323         lockdep_assert_held(&dst->lock);
 324
 325         if (WARN_ON(list_empty(&e->entry)))
 326                 return -EINVAL;
 327         if (src == dst)
 328                 return 0;
 329
 330         size = kdbus_pool_slice_size(e->slice);
 331         fds = e->gaps ? e->gaps->n_fds : 0;
 332
 333         ret = kdbus_conn_quota_inc(dst, e->user, size, fds);
 334         if (ret < 0)
 335                 return ret;
 336
 337         slice = kdbus_pool_slice_alloc(dst->pool, size, true);
 338         if (IS_ERR(slice)) {
 339                 ret = PTR_ERR(slice);
 340                 slice = NULL;
 341                 goto error;
 342         }
 343
 344         ret = kdbus_pool_slice_copy(slice, e->slice);
 345         if (ret < 0)
 346                 goto error;
 347
 348         kdbus_queue_entry_unlink(e);
 349         kdbus_conn_quota_dec(src, e->user, size, fds);
 350         kdbus_pool_slice_release(e->slice);
 351         kdbus_conn_unref(e->conn);
 352
 353         e->slice = slice;
 354         e->conn = kdbus_conn_ref(dst);
 355         kdbus_queue_entry_link(e);
 356
 357         return 0;
 358
 359 error:
 360         kdbus_pool_slice_release(slice);
 361         kdbus_conn_quota_dec(dst, e->user, size, fds);
 362         return ret;
 363 }