net/ceph/string_table.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 #include <linux/slab.h>
0003 #include <linux/gfp.h>
0004 #include <linux/string.h>
0005 #include <linux/spinlock.h>
0006 #include <linux/ceph/string_table.h>
0007
0008 static DEFINE_SPINLOCK(string_tree_lock);
0009 static struct rb_root string_tree = RB_ROOT;
0010
0011 struct ceph_string *ceph_find_or_create_string(const char* str, size_t len)
0012 {
0013     struct ceph_string *cs, *exist;
0014     struct rb_node **p, *parent;
0015     int ret;
0016
0017     exist = NULL;
0018     spin_lock(&string_tree_lock);
0019     p = &string_tree.rb_node;
0020     while (*p) {
0021         exist = rb_entry(*p, struct ceph_string, node);
0022         ret = ceph_compare_string(exist, str, len);
0023         if (ret > 0)
0024             p = &(*p)->rb_left;
0025         else if (ret < 0)
0026             p = &(*p)->rb_right;
0027         else
0028             break;
0029         exist = NULL;
0030     }
0031     if (exist && !kref_get_unless_zero(&exist->kref)) {
0032         rb_erase(&exist->node, &string_tree);
0033         RB_CLEAR_NODE(&exist->node);
0034         exist = NULL;
0035     }
0036     spin_unlock(&string_tree_lock);
0037     if (exist)
0038         return exist;
0039
0040     cs = kmalloc(sizeof(*cs) + len + 1, GFP_NOFS);
0041     if (!cs)
0042         return NULL;
0043
0044     kref_init(&cs->kref);
0045     cs->len = len;
0046     memcpy(cs->str, str, len);
0047     cs->str[len] = 0;
0048
0049 retry:
0050     exist = NULL;
0051     parent = NULL;
0052     p = &string_tree.rb_node;
0053     spin_lock(&string_tree_lock);
0054     while (*p) {
0055         parent = *p;
0056         exist = rb_entry(*p, struct ceph_string, node);
0057         ret = ceph_compare_string(exist, str, len);
0058         if (ret > 0)
0059             p = &(*p)->rb_left;
0060         else if (ret < 0)
0061             p = &(*p)->rb_right;
0062         else
0063             break;
0064         exist = NULL;
0065     }
0066     ret = 0;
0067     if (!exist) {
0068         rb_link_node(&cs->node, parent, p);
0069         rb_insert_color(&cs->node, &string_tree);
0070     } else if (!kref_get_unless_zero(&exist->kref)) {
0071         rb_erase(&exist->node, &string_tree);
0072         RB_CLEAR_NODE(&exist->node);
0073         ret = -EAGAIN;
0074     }
0075     spin_unlock(&string_tree_lock);
0076     if (ret == -EAGAIN)
0077         goto retry;
0078
0079     if (exist) {
0080         kfree(cs);
0081         cs = exist;
0082     }
0083
0084     return cs;
0085 }
0086 EXPORT_SYMBOL(ceph_find_or_create_string);
0087
0088 void ceph_release_string(struct kref *ref)
0089 {
0090     struct ceph_string *cs = container_of(ref, struct ceph_string, kref);
0091
0092     spin_lock(&string_tree_lock);
0093     if (!RB_EMPTY_NODE(&cs->node)) {
0094         rb_erase(&cs->node, &string_tree);
0095         RB_CLEAR_NODE(&cs->node);
0096     }
0097     spin_unlock(&string_tree_lock);
0098
0099     kfree_rcu(cs, rcu);
0100 }
0101 EXPORT_SYMBOL(ceph_release_string);
0102
0103 bool ceph_strings_empty(void)
0104 {
0105     return RB_EMPTY_ROOT(&string_tree);
0106 }