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