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
ceph_find_or_create_string(const char * str,size_t len)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
ceph_release_string(struct kref * ref)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
ceph_strings_empty(void)103 bool ceph_strings_empty(void)
104 {
105 return RB_EMPTY_ROOT(&string_tree);
106 }
107