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}

 
  1#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
 87void ceph_release_string(struct kref *ref)
 88{
 89	struct ceph_string *cs = container_of(ref, struct ceph_string, kref);
 90
 91	spin_lock(&string_tree_lock);
 92	if (!RB_EMPTY_NODE(&cs->node)) {
 93		rb_erase(&cs->node, &string_tree);
 94		RB_CLEAR_NODE(&cs->node);
 95	}
 96	spin_unlock(&string_tree_lock);
 97
 98	kfree_rcu(cs, rcu);
 99}
100EXPORT_SYMBOL(ceph_release_string);
101
102bool ceph_strings_empty(void)
103{
104	return RB_EMPTY_ROOT(&string_tree);
105}