LXR linux/net/ceph/string

   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
   8static DEFINE_SPINLOCK(string_tree_lock);
   9static struct rb_root string_tree = RB_ROOT;
  10
  11struct 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
  49retry:
  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}
  86EXPORT_SYMBOL(ceph_find_or_create_string);
  87
  88void 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}
 101EXPORT_SYMBOL(ceph_release_string);
 102
 103bool ceph_strings_empty(void)
 104{
 105        return RB_EMPTY_ROOT(&string_tree);
 106}
 107