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