net/ceph/string_table.c

   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 }