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