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