ib_umem_rbtree.c revision 331769
1169695Skan/* 2169695Skan * Copyright (c) 2014 Mellanox Technologies. All rights reserved. 3169695Skan * 4169695Skan * This software is available to you under a choice of one of two 5169695Skan * licenses. You may choose to be licensed under the terms of the GNU 6169695Skan * General Public License (GPL) Version 2, available from the file 7169695Skan * COPYING in the main directory of this source tree, or the 8169695Skan * OpenIB.org BSD license below: 9169695Skan * 10169695Skan * Redistribution and use in source and binary forms, with or 11169695Skan * without modification, are permitted provided that the following 12169695Skan * conditions are met: 13169695Skan * 14169695Skan * - Redistributions of source code must retain the above 15169695Skan * copyright notice, this list of conditions and the following 16169695Skan * disclaimer. 17169695Skan * 18169695Skan * - Redistributions in binary form must reproduce the above 19169695Skan * copyright notice, this list of conditions and the following 20169695Skan * disclaimer in the documentation and/or other materials 21169695Skan * provided with the distribution. 22169695Skan * 23169695Skan * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 24169695Skan * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 25169695Skan * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 26169695Skan * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 27169695Skan * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 28169695Skan * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 29169695Skan * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 30169695Skan * SOFTWARE. 31169695Skan */ 32169695Skan 33169695Skan#include <linux/kernel.h> 34169695Skan#include <linux/module.h> 35169695Skan#include <linux/sched.h> 36169695Skan#include <linux/gfp.h> 37169695Skan#include <rdma/ib_umem_odp.h> 38169695Skan 39169695Skan/* 40169695Skan * The ib_umem list keeps track of memory regions for which the HW 41169695Skan * device request to receive notification when the related memory 42169695Skan * mapping is changed. 43169695Skan * 44169695Skan * ib_umem_lock protects the list. 45169695Skan */ 46169695Skan 47169695Skanstatic inline u64 node_start(struct umem_odp_node *n) 48169695Skan{ 49169695Skan struct ib_umem_odp *umem_odp = 50169695Skan container_of(n, struct ib_umem_odp, interval_tree); 51169695Skan 52169695Skan return ib_umem_start(umem_odp->umem); 53169695Skan} 54169695Skan 55169695Skan/* Note that the representation of the intervals in the interval tree 56169695Skan * considers the ending point as contained in the interval, while the 57169695Skan * function ib_umem_end returns the first address which is not contained 58169695Skan * in the umem. 59169695Skan */ 60169695Skanstatic inline u64 node_last(struct umem_odp_node *n) 61169695Skan{ 62169695Skan struct ib_umem_odp *umem_odp = 63169695Skan container_of(n, struct ib_umem_odp, interval_tree); 64169695Skan 65169695Skan return ib_umem_end(umem_odp->umem) - 1; 66169695Skan} 67169695Skan 68169695SkanINTERVAL_TREE_DEFINE(struct umem_odp_node, rb, u64, __subtree_last, 69169695Skan node_start, node_last, , rbt_ib_umem) 70169695Skan 71169695Skan/* @last is not a part of the interval. See comment for function 72169695Skan * node_last. 73169695Skan */ 74169695Skanint rbt_ib_umem_for_each_in_range(struct rb_root *root, 75169695Skan u64 start, u64 last, 76169695Skan umem_call_back cb, 77169695Skan void *cookie) 78169695Skan{ 79169695Skan int ret_val = 0; 80169695Skan struct umem_odp_node *node; 81169695Skan struct ib_umem_odp *umem; 82169695Skan 83169695Skan if (unlikely(start == last)) 84169695Skan return ret_val; 85169695Skan 86169695Skan for (node = rbt_ib_umem_iter_first(root, start, last - 1); node; 87169695Skan node = rbt_ib_umem_iter_next(node, start, last - 1)) { 88169695Skan umem = container_of(node, struct ib_umem_odp, interval_tree); 89169695Skan ret_val = cb(umem->umem, start, last, cookie) || ret_val; 90169695Skan } 91169695Skan 92169695Skan return ret_val; 93169695Skan} 94169695Skan