drivers/staging/rdma/hfi1/mmu_rb.c

   1 /*
   2  * Copyright(c) 2016 Intel Corporation.
   3  *
   4  * This file is provided under a dual BSD/GPLv2 license.  When using or
   5  * redistributing this file, you may do so under either license.
   6  *
   7  * GPL LICENSE SUMMARY
   8  *
   9  * This program is free software; you can redistribute it and/or modify
  10  * it under the terms of version 2 of the GNU General Public License as
  11  * published by the Free Software Foundation.
  12  *
  13  * This program 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  * General Public License for more details.
  17  *
  18  * BSD LICENSE
  19  *
  20  * Redistribution and use in source and binary forms, with or without
  21  * modification, are permitted provided that the following conditions
  22  * are met:
  23  *
  24  *  - Redistributions of source code must retain the above copyright
  25  *    notice, this list of conditions and the following disclaimer.
  26  *  - Redistributions in binary form must reproduce the above copyright
  27  *    notice, this list of conditions and the following disclaimer in
  28  *    the documentation and/or other materials provided with the
  29  *    distribution.
  30  *  - Neither the name of Intel Corporation nor the names of its
  31  *    contributors may be used to endorse or promote products derived
  32  *    from this software without specific prior written permission.
  33  *
  34  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  35  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  36  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  37  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  38  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  39  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  40  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  41  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  42  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  43  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  44  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  45  *
  46  */
  47 #include <linux/list.h>
  48 #include <linux/mmu_notifier.h>
  49 #include <linux/rbtree.h>
  50
  51 #include "mmu_rb.h"
  52 #include "trace.h"
  53
  54 struct mmu_rb_handler {
  55         struct list_head list;
  56         struct mmu_notifier mn;
  57         struct rb_root *root;
  58         spinlock_t lock;        /* protect the RB tree */
  59         struct mmu_rb_ops *ops;
  60 };
  61
  62 static LIST_HEAD(mmu_rb_handlers);
  63 static DEFINE_SPINLOCK(mmu_rb_lock); /* protect mmu_rb_handlers list */
  64
  65 static struct mmu_rb_handler *find_mmu_handler(struct rb_root *);
  66 static inline void mmu_notifier_page(struct mmu_notifier *, struct mm_struct *,
  67                                      unsigned long);
  68 static inline void mmu_notifier_range_start(struct mmu_notifier *,
  69                                             struct mm_struct *,
  70                                             unsigned long, unsigned long);
  71 static void mmu_notifier_mem_invalidate(struct mmu_notifier *,
  72                                         unsigned long, unsigned long);
  73 static struct mmu_rb_node *__mmu_rb_search(struct mmu_rb_handler *,
  74                                            unsigned long, unsigned long);
  75
  76 static struct mmu_notifier_ops mn_opts = {
  77         .invalidate_page = mmu_notifier_page,
  78         .invalidate_range_start = mmu_notifier_range_start,
  79 };
  80
  81 int hfi1_mmu_rb_register(struct rb_root *root, struct mmu_rb_ops *ops)
  82 {
  83         struct mmu_rb_handler *handlr;
  84
  85         if (!ops->compare || !ops->invalidate)
  86                 return -EINVAL;
  87
  88         handlr = kmalloc(sizeof(*handlr), GFP_KERNEL);
  89         if (!handlr)
  90                 return -ENOMEM;
  91
  92         handlr->root = root;
  93         handlr->ops = ops;
  94         INIT_HLIST_NODE(&handlr->mn.hlist);
  95         spin_lock_init(&handlr->lock);
  96         handlr->mn.ops = &mn_opts;
  97         spin_lock(&mmu_rb_lock);
  98         list_add_tail(&handlr->list, &mmu_rb_handlers);
  99         spin_unlock(&mmu_rb_lock);
 100
 101         return mmu_notifier_register(&handlr->mn, current->mm);
 102 }
 103
 104 void hfi1_mmu_rb_unregister(struct rb_root *root)
 105 {
 106         struct mmu_rb_handler *handler = find_mmu_handler(root);
 107
 108         spin_lock(&mmu_rb_lock);
 109         list_del(&handler->list);
 110         spin_unlock(&mmu_rb_lock);
 111
 112         if (!RB_EMPTY_ROOT(root)) {
 113                 struct rb_node *node;
 114                 struct mmu_rb_node *rbnode;
 115
 116                 while ((node = rb_first(root))) {
 117                         rbnode = rb_entry(node, struct mmu_rb_node, node);
 118                         if (handler->ops->remove)
 119                                 handler->ops->remove(root, rbnode);
 120                         rb_erase(node, root);
 121                         kfree(rbnode);
 122                 }
 123         }
 124
 125         if (current->mm)
 126                 mmu_notifier_unregister(&handler->mn, current->mm);
 127         kfree(handler);
 128 }
 129
 130 int hfi1_mmu_rb_insert(struct rb_root *root, struct mmu_rb_node *mnode)
 131 {
 132         struct rb_node **new, *parent = NULL;
 133         struct mmu_rb_handler *handler = find_mmu_handler(root);
 134         struct mmu_rb_node *this;
 135         int res, ret = 0;
 136
 137         if (!handler)
 138                 return -EINVAL;
 139
 140         new = &handler->root->rb_node;
 141         spin_lock(&handler->lock);
 142         while (*new) {
 143                 this = container_of(*new, struct mmu_rb_node, node);
 144                 res = handler->ops->compare(this, mnode->addr, mnode->len);
 145                 parent = *new;
 146
 147                 if (res < 0) {
 148                         new = &((*new)->rb_left);
 149                 } else if (res > 0) {
 150                         new = &((*new)->rb_right);
 151                 } else {
 152                         ret = 1;
 153                         goto unlock;
 154                 }
 155         }
 156
 157         if (handler->ops->insert) {
 158                 ret = handler->ops->insert(root, mnode);
 159                 if (ret)
 160                         goto unlock;
 161         }
 162
 163         rb_link_node(&mnode->node, parent, new);
 164         rb_insert_color(&mnode->node, root);
 165 unlock:
 166         spin_unlock(&handler->lock);
 167         return ret;
 168 }
 169
 170 /* Caller must host handler lock */
 171 static struct mmu_rb_node *__mmu_rb_search(struct mmu_rb_handler *handler,
 172                                            unsigned long addr,
 173                                            unsigned long len)
 174 {
 175         struct rb_node *node = handler->root->rb_node;
 176         struct mmu_rb_node *mnode;
 177         int res;
 178
 179         while (node) {
 180                 mnode = container_of(node, struct mmu_rb_node, node);
 181                 res = handler->ops->compare(mnode, addr, len);
 182
 183                 if (res < 0)
 184                         node = node->rb_left;
 185                 else if (res > 0)
 186                         node = node->rb_right;
 187                 else
 188                         return mnode;
 189         }
 190         return NULL;
 191 }
 192
 193 static void __mmu_rb_remove(struct mmu_rb_handler *handler,
 194                             struct mmu_rb_node *node)
 195 {
 196         /* Validity of handler and node pointers has been checked by caller. */
 197         if (handler->ops->remove)
 198                 handler->ops->remove(handler->root, node);
 199         rb_erase(&node->node, handler->root);
 200 }
 201
 202 struct mmu_rb_node *hfi1_mmu_rb_search(struct rb_root *root, unsigned long addr,
 203                                        unsigned long len)
 204 {
 205         struct mmu_rb_handler *handler = find_mmu_handler(root);
 206         struct mmu_rb_node *node;
 207
 208         if (!handler)
 209                 return ERR_PTR(-EINVAL);
 210
 211         spin_lock(&handler->lock);
 212         node = __mmu_rb_search(handler, addr, len);
 213         spin_unlock(&handler->lock);
 214
 215         return node;
 216 }
 217
 218 void hfi1_mmu_rb_remove(struct rb_root *root, struct mmu_rb_node *node)
 219 {
 220         struct mmu_rb_handler *handler = find_mmu_handler(root);
 221
 222         if (!handler || !node)
 223                 return;
 224
 225         spin_lock(&handler->lock);
 226         __mmu_rb_remove(handler, node);
 227         spin_unlock(&handler->lock);
 228 }
 229
 230 static struct mmu_rb_handler *find_mmu_handler(struct rb_root *root)
 231 {
 232         struct mmu_rb_handler *handler;
 233
 234         spin_lock(&mmu_rb_lock);
 235         list_for_each_entry(handler, &mmu_rb_handlers, list) {
 236                 if (handler->root == root)
 237                         goto unlock;
 238         }
 239         handler = NULL;
 240 unlock:
 241         spin_unlock(&mmu_rb_lock);
 242         return handler;
 243 }
 244
 245 static inline void mmu_notifier_page(struct mmu_notifier *mn,
 246                                      struct mm_struct *mm, unsigned long addr)
 247 {
 248         mmu_notifier_mem_invalidate(mn, addr, addr + PAGE_SIZE);
 249 }
 250
 251 static inline void mmu_notifier_range_start(struct mmu_notifier *mn,
 252                                             struct mm_struct *mm,
 253                                             unsigned long start,
 254                                             unsigned long end)
 255 {
 256         mmu_notifier_mem_invalidate(mn, start, end);
 257 }
 258
 259 static void mmu_notifier_mem_invalidate(struct mmu_notifier *mn,
 260                                         unsigned long start, unsigned long end)
 261 {
 262         struct mmu_rb_handler *handler =
 263                 container_of(mn, struct mmu_rb_handler, mn);
 264         struct rb_root *root = handler->root;
 265         struct mmu_rb_node *node;
 266         unsigned long addr = start;
 267
 268         spin_lock(&handler->lock);
 269         while (addr < end) {
 270                 /*
 271                  * There is no good way to provide a reasonable length to the
 272                  * search function at this point. Using the remaining length in
 273                  * the invalidation range is not the right thing to do.
 274                  * We have to rely on the fact that the insertion algorithm
 275                  * takes care of any overlap or length restrictions by using the
 276                  * actual size of each node. Therefore, we can use a page as an
 277                  * arbitrary, non-zero value.
 278                  */
 279                 node = __mmu_rb_search(handler, addr, PAGE_SIZE);
 280
 281                 if (!node) {
 282                         /*
 283                          * Didn't find a node at this address. However, the
 284                          * range could be bigger than what we have registered
 285                          * so we have to keep looking.
 286                          */
 287                         addr += PAGE_SIZE;
 288                         continue;
 289                 }
 290                 if (handler->ops->invalidate(root, node))
 291                         __mmu_rb_remove(handler, node);
 292
 293                 /*
 294                  * The next address to be looked up is computed based
 295                  * on the node's starting address. This is due to the
 296                  * fact that the range where we start might be in the
 297                  * middle of the node's buffer so simply incrementing
 298                  * the address by the node's size would result is a
 299                  * bad address.
 300                  */
 301                 addr = node->addr + node->len;
 302         }
 303         spin_unlock(&handler->lock);
 304 }