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}