1/* 2 * Copyright 2016, NICTA 3 * 4 * This software may be distributed and modified according to the terms of 5 * the GNU General Public License version 2. Note that NO WARRANTY is provided. 6 * See "LICENSE_GPLv2.txt" for details. 7 * 8 * @TAG(NICTA_GPL) 9 */ 10 11#include <bilbyfs.h> 12 13#define IDX_HASH_SIZE 2048 14 15int idx_init(struct bilbyfs_info *bi) 16{ 17 int i; 18 19 bi->idx_hash = vmalloc(sizeof(*(bi->idx_hash)) * IDX_HASH_SIZE); 20 if (!bi->idx_hash) 21 return -ENOMEM; 22 for (i = 0; i < IDX_HASH_SIZE; i++) { 23 bi->idx_hash[i] = RBT_ROOT; 24 } 25 return 0; 26} 27 28void idx_clean(struct bilbyfs_info *bi) 29{ 30 struct rbt_root *idx_tree; 31 struct rbt_node *node; 32 int i; 33 34 for (i = 0; i < IDX_HASH_SIZE; i++) { 35 idx_tree = &bi->idx_hash[i]; 36 for (node = rbt_first(idx_tree); 37 node; 38 node = rbt_first(idx_tree)) { 39 rbt_erase(node, idx_tree); 40 kfree(node); 41 } 42 } 43 vfree(bi->idx_hash); 44 bi->idx_hash = NULL; 45} 46 47/* Rb search from Linux Documentation */ 48static struct idx_node *idx_index_search(struct rbt_root *root, obj_id id) 49{ 50 struct rbt_node *node = root->rbt_node; 51 struct idx_node *xnode; 52 /* 53 struct timeval st, stp; 54 55 do_gettimeofday(&st); 56 */ 57 while (node) { 58 xnode = container_of(node, struct idx_node, node); 59 60 if (id < xnode->id) 61 node = node->rbt_left; 62 else if (id > xnode->id) 63 node = node->rbt_right; 64 else { 65 /* 66 do_gettimeofday(&stp); 67 pr_err("timed index search : %ld sec %ld usec\n", stp.tv_sec - st.tv_sec, stp. tv_usec - st.tv_usec); 68 */ 69 return xnode; 70 } 71 } 72 /* 73 do_gettimeofday(&stp); 74 pr_err("timed index search : %ld sec %ld usec\n", stp.tv_sec - st.tv_sec, stp. tv_usec - st.tv_usec); 75 */ 76 return NULL; 77} 78 79static u32 idx_hash_inum(u32 inum) 80{ 81 return inum % IDX_HASH_SIZE; 82} 83 84int idx_get_obj_addr(struct bilbyfs_info *bi, obj_id id, struct obj_addr *addr) 85{ 86 struct idx_node *xnode; 87 u32 inum = inum_from_id(id); 88 u32 hash = idx_hash_inum(inum); 89 90 xnode = idx_index_search(&bi->idx_hash[hash], id); 91 92 if (!xnode) 93 return -ENOENT; 94 *addr = xnode->addr; 95 return 0; 96} 97 98/* Rb insert from Linux Documentation */ 99static struct idx_node *index_insert_or_replace(struct bilbyfs_info *bi, struct rbt_root *root, obj_id id, struct idx_node *allocated_node) 100{ 101 struct rbt_node **new = &(root->rbt_node), *parent = NULL; 102 struct idx_node *xnode; 103 104 /* Figure out where to put new node */ 105 while (*new) { 106 xnode = container_of(*new, struct idx_node, node); 107 108 parent = *new; 109 if (id < xnode->id) 110 new = &((*new)->rbt_left); 111 else if (id > xnode->id) 112 new = &((*new)->rbt_right); 113 else { 114 kfree(allocated_node); 115 return xnode; 116 } 117 } 118 119 xnode = allocated_node ? allocated_node : allocpool_pop(&bi->node_pool); 120 memset(xnode, 0, sizeof(*xnode)); 121 xnode->id = id; 122 /* Add new node and rebalance tree. */ 123 rbt_link_node(&xnode->node, parent, new); 124 rbt_insert_color(&xnode->node, root); 125 return xnode; 126} 127 128int idx_set_obj_addr(struct bilbyfs_info *bi, obj_id id, struct obj_addr *addr, struct idx_node *allocated_node) 129{ 130 struct idx_node *xnode; 131 u32 inum = inum_from_id(id); 132 u32 hash = idx_hash_inum(inum); 133 134 xnode = index_insert_or_replace(bi, &bi->idx_hash[hash], id, allocated_node); 135 xnode->addr = *addr; 136 return 0; 137} 138 139struct idx_node *idx_get_or_create_obj_addr_node(struct bilbyfs_info *bi, obj_id id) 140{ 141 u32 inum = inum_from_id(id); 142 u32 hash = idx_hash_inum(inum); 143 144 return index_insert_or_replace(bi, &bi->idx_hash[hash], id, NULL); 145} 146 147obj_id idx_next_obj_id(struct bilbyfs_info *bi, obj_id id) 148{ 149 struct rbt_node *node; 150 struct idx_node *xnode; 151 struct idx_node *xnode_greater = NULL; 152 u32 inum = inum_from_id(id); 153 u32 hash = idx_hash_inum(inum); 154 155 node = bi->idx_hash[hash].rbt_node; 156 157 158 /* Find a elem greater than @id then follow only left branches 159 * to find a lower id closer to @id. 160 */ 161 while (node) { 162 xnode = container_of(node, struct idx_node, node); 163 164 if (id < xnode->id) { 165 xnode_greater = xnode; 166 node = node->rbt_left; 167 } else if (id >= xnode->id) { 168 node = node->rbt_right; 169 } 170 } 171 if (!xnode_greater) 172 return NIL_ID; 173 if (inum != inum_from_id(xnode_greater->id)) 174 return NIL_ID; 175 return xnode_greater->id; 176} 177 178void *idx_del_obj_addr(struct bilbyfs_info *bi, obj_id id) 179{ 180 struct idx_node *xnode; 181 u32 inum = inum_from_id(id); 182 u32 hash = idx_hash_inum(inum); 183 184 xnode = idx_index_search(&bi->idx_hash[hash], id); 185 bilbyfs_assert(xnode); 186 rbt_erase(&xnode->node, &bi->idx_hash[hash]); 187 return xnode; 188} 189