1 #include <linux/slab.h> 2 #include <linux/gfp.h> 3 #include <linux/string.h> 4 #include <linux/spinlock.h> 5 #include <linux/ceph/string_table.h> 6 7 static DEFINE_SPINLOCK(string_tree_lock); 8 static struct rb_root string_tree = RB_ROOT; 9 10 struct ceph_string *ceph_find_or_create_string(const char* str, size_t len) 11 { 12 struct ceph_string *cs, *exist; 13 struct rb_node **p, *parent; 14 int ret; 15 16 exist = NULL; 17 spin_lock(&string_tree_lock); 18 p = &string_tree.rb_node; 19 while (*p) { 20 exist = rb_entry(*p, struct ceph_string, node); 21 ret = ceph_compare_string(exist, str, len); 22 if (ret > 0) 23 p = &(*p)->rb_left; 24 else if (ret < 0) 25 p = &(*p)->rb_right; 26 else 27 break; 28 exist = NULL; 29 } 30 if (exist && !kref_get_unless_zero(&exist->kref)) { 31 rb_erase(&exist->node, &string_tree); 32 RB_CLEAR_NODE(&exist->node); 33 exist = NULL; 34 } 35 spin_unlock(&string_tree_lock); 36 if (exist) 37 return exist; 38 39 cs = kmalloc(sizeof(*cs) + len + 1, GFP_NOFS); 40 if (!cs) 41 return NULL; 42 43 kref_init(&cs->kref); 44 cs->len = len; 45 memcpy(cs->str, str, len); 46 cs->str[len] = 0; 47 48 retry: 49 exist = NULL; 50 parent = NULL; 51 p = &string_tree.rb_node; 52 spin_lock(&string_tree_lock); 53 while (*p) { 54 parent = *p; 55 exist = rb_entry(*p, struct ceph_string, node); 56 ret = ceph_compare_string(exist, str, len); 57 if (ret > 0) 58 p = &(*p)->rb_left; 59 else if (ret < 0) 60 p = &(*p)->rb_right; 61 else 62 break; 63 exist = NULL; 64 } 65 ret = 0; 66 if (!exist) { 67 rb_link_node(&cs->node, parent, p); 68 rb_insert_color(&cs->node, &string_tree); 69 } else if (!kref_get_unless_zero(&exist->kref)) { 70 rb_erase(&exist->node, &string_tree); 71 RB_CLEAR_NODE(&exist->node); 72 ret = -EAGAIN; 73 } 74 spin_unlock(&string_tree_lock); 75 if (ret == -EAGAIN) 76 goto retry; 77 78 if (exist) { 79 kfree(cs); 80 cs = exist; 81 } 82 83 return cs; 84 } 85 EXPORT_SYMBOL(ceph_find_or_create_string); 86 87 void ceph_release_string(struct kref *ref) 88 { 89 struct ceph_string *cs = container_of(ref, struct ceph_string, kref); 90 91 spin_lock(&string_tree_lock); 92 if (!RB_EMPTY_NODE(&cs->node)) { 93 rb_erase(&cs->node, &string_tree); 94 RB_CLEAR_NODE(&cs->node); 95 } 96 spin_unlock(&string_tree_lock); 97 98 kfree_rcu(cs, rcu); 99 } 100 EXPORT_SYMBOL(ceph_release_string); 101 102 bool ceph_strings_empty(void) 103 { 104 return RB_EMPTY_ROOT(&string_tree); 105 } 106