blob: ca53c8319209469a25011b15d26af951a09d392d [file] [log] [blame]
Yan, Zheng51e92732016-02-05 15:36:22 +08001#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
7static DEFINE_SPINLOCK(string_tree_lock);
8static struct rb_root string_tree = RB_ROOT;
9
10struct 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
48retry:
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}
85EXPORT_SYMBOL(ceph_find_or_create_string);
86
87static void ceph_free_string(struct rcu_head *head)
88{
89 struct ceph_string *cs = container_of(head, struct ceph_string, rcu);
90 kfree(cs);
91}
92
93void ceph_release_string(struct kref *ref)
94{
95 struct ceph_string *cs = container_of(ref, struct ceph_string, kref);
96
97 spin_lock(&string_tree_lock);
98 if (!RB_EMPTY_NODE(&cs->node)) {
99 rb_erase(&cs->node, &string_tree);
100 RB_CLEAR_NODE(&cs->node);
101 }
102 spin_unlock(&string_tree_lock);
103
104 call_rcu(&cs->rcu, ceph_free_string);
105}
106EXPORT_SYMBOL(ceph_release_string);
107
108bool ceph_strings_empty(void)
109{
110 return RB_EMPTY_ROOT(&string_tree);
111}