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 GIM_HASH_SIZE 2048
14
15int gim_init(struct bilbyfs_info *bi)
16{
17        int i;
18
19        bi->gim_hash = vmalloc(sizeof(*(bi->gim_hash)) * GIM_HASH_SIZE);
20        if (!bi->gim_hash)
21                return -ENOMEM;
22        for (i = 0; i < GIM_HASH_SIZE; i++) {
23                bi->gim_hash[i] = RBT_ROOT;
24        }
25        return 0;
26}
27
28void gim_clean(struct bilbyfs_info *bi)
29{
30      struct rbt_root *gim_tree;
31      struct rbt_node *node;
32      int i;
33
34      for (i = 0; i < GIM_HASH_SIZE; i++) {
35              gim_tree = &bi->gim_hash[i];
36              for (node = rbt_first(gim_tree);
37                   node;
38                   node = rbt_first(gim_tree)) {
39                      rbt_erase(node, gim_tree);
40                      allocpool_free_single(node);
41              }
42      }
43      vfree(bi->gim_hash);
44      bi->gim_hash = NULL;
45}
46
47static u32 gim_hash_inum(u32 inum)
48{
49        return inum % GIM_HASH_SIZE;
50}
51
52/* Rb search from Linux Documentation */
53static struct gim_node *gim_index_search(struct bilbyfs_info *bi, obj_id id)
54{
55        u32 hash = gim_hash_inum(inum_from_id(id));
56        struct rbt_root *root = &bi->gim_hash[hash];
57      struct rbt_node *node = root->rbt_node;
58      struct gim_node *gnode;
59      /*
60      struct timeval st, stp;
61
62      do_gettimeofday(&st);
63      */
64      while (node) {
65              gnode = container_of(node, struct gim_node, node);
66
67              if (id < gnode->id)
68                      node = node->rbt_left;
69              else if (id > gnode->id)
70                      node = node->rbt_right;
71              else {
72                      /*
73                      do_gettimeofday(&stp);
74                      pr_err("timed gim search : %ld sec %ld usec\n", stp.tv_sec - st.tv_sec, stp. tv_usec - st.tv_usec);
75                      */
76                      return gnode;
77              }
78      }
79      /*
80      do_gettimeofday(&stp);
81      pr_err("timed gim search : %ld sec %ld usec\n", stp.tv_sec - st.tv_sec, stp. tv_usec - st.tv_usec);
82                      */
83      return NULL;
84}
85
86static struct gim_node *gim_insert_or_replace(struct bilbyfs_info *bi, obj_id id, struct gim_node *allocated_node)
87{
88        u32 hash = gim_hash_inum(inum_from_id(id));
89        struct rbt_root *root = &bi->gim_hash[hash];
90        struct rbt_node **new = &(root->rbt_node), *parent = NULL;
91        struct gim_node *xnode;
92
93        /* Figure out where to put new node */
94        while (*new) {
95                xnode = container_of(*new, struct gim_node, node);
96
97                parent = *new;
98                if (id < xnode->id)
99                        new = &((*new)->rbt_left);
100                else if (id > xnode->id)
101                        new = &((*new)->rbt_right);
102                else {
103                        kfree(allocated_node);
104                        return xnode;
105                }
106        }
107
108        xnode = allocated_node ? allocated_node : allocpool_pop(&bi->node_pool);
109        memset(xnode, 0, sizeof(*xnode));
110        xnode->id = id;
111        /* Add new node and rebalance tree. */
112        rbt_link_node(&xnode->node, parent, new);
113        rbt_insert_color(&xnode->node, root);
114        return xnode;
115}
116
117int gim_mark_garbage_cnt(struct bilbyfs_info *bi, obj_id id, struct obj_addr *addr, u32 count, struct gim_node *allocated_node)
118{
119        struct gim_node *gnode = gim_insert_or_replace(bi, id, allocated_node);
120
121        if (gnode->sqnum < addr->sqnum)
122                gnode->sqnum = addr->sqnum;
123        gnode->count += count;
124        return 0;
125}
126
127int gim_mark_garbage(struct bilbyfs_info *bi, obj_id id, struct obj_addr *addr, struct gim_node *allocated_node)
128{
129        return gim_mark_garbage_cnt(bi, id, addr, 1, allocated_node);
130}
131
132struct gim_node *gim_next_node(struct bilbyfs_info *bi, struct gim_node *curr_gnode)
133{
134        struct rbt_node *node;
135        struct gim_node *gnode;
136        struct gim_node *gnode_greater = NULL;
137        obj_id id = curr_gnode->id;
138        u32  inum = inum_from_id(id);
139        u32 hash = gim_hash_inum(inum);
140
141        node = bi->gim_hash[hash].rbt_node;
142
143      /* Find a elem greater than @id then follow only left branches
144       * to find a lower id closer to @id.
145       */
146      while (node) {
147              gnode = container_of(node, struct gim_node, node);
148
149              if (id < gnode->id) {
150                      gnode_greater = gnode;
151                      node = node->rbt_left;
152              } else if (id >= gnode->id) {
153                      node = node->rbt_right;
154              }
155      }
156      return gnode_greater;
157}
158
159int gim_is_removable(struct bilbyfs_info *bi, struct obj_ch *obj)
160{
161        obj_id id;
162        u64 sqnum = le64_to_cpu(obj->sqnum);
163        u32 id_type;
164        struct gim_node *gnode, *pre_gnode = NULL;
165
166        // Padding object can be always garbage collected
167        if (obj->type == BILBYFS_PAD_OBJ || obj->type == BILBYFS_SUM_OBJ)
168                return BILBYFS_TRUE;
169
170        // Object not found in garbage list
171        id = get_obj_id(obj);
172        gnode = gim_index_search(bi, id);
173        if (!gnode)
174                return BILBYFS_FALSE;
175
176        // Object version is newer
177        if (sqnum > gnode->sqnum) /*  Is this possible? In which circumstances? */
178                return BILBYFS_FALSE;
179
180        // Deletion object
181        if (obj->type == BILBYFS_DEL_OBJ) {
182                id_type = type_from_id(id);
183                switch (id_type) {
184                case BILBYFS_DENTARR_OBJ:
185                        return BILBYFS_TRUE;
186                case BILBYFS_INODE_OBJ:
187                case BILBYFS_DATA_OBJ:
188                        while (gnode != NULL && (pre_gnode == NULL ||
189                               inum_from_id(gnode->id) == inum_from_id(pre_gnode->id))) {
190                                if (sqnum >= gnode->sqnum && gnode->count > 1)
191                                        return BILBYFS_FALSE;
192
193                                pre_gnode = gnode;
194                                gnode = gim_next_node(bi, gnode);
195                        }
196                        return BILBYFS_TRUE;
197                default:
198                        bilbyfs_assert(0);
199                }
200        }
201
202        // Other objects in the garbage list
203        return BILBYFS_TRUE;
204}
205
206int gim_garbage_collected(struct bilbyfs_info *bi, struct obj_ch *obj)
207{
208        struct gim_node *gnode;
209        obj_id id;
210        u32 hash;
211
212        if (obj->type == BILBYFS_PAD_OBJ || obj->type == BILBYFS_SUM_OBJ)
213                return 0;
214
215        id = get_obj_id(obj);
216        hash = gim_hash_inum(inum_from_id(id));
217        gnode = gim_index_search(bi, id);
218        if (gnode) {
219                gnode->count--;
220                if (gnode->count <= 0) {
221                        rbt_erase(&gnode->node, &bi->gim_hash[hash]);
222                        allocpool_free_single(gnode);
223                }
224                return 0;
225        }
226
227        return -ENOENT;
228}
229
230