#include <linux/init.h>
#include <linux/wait.h>
#include <linux/slab.h>
+#include <linux/rbtree.h>
#include <linux/dm-ioctl.h>
#include <linux/hdreg.h>
#include <linux/compat.h>
* name or uuid.
*---------------------------------------------------------------*/
struct hash_cell {
- struct list_head name_list;
- struct list_head uuid_list;
+ struct rb_node name_node;
+ struct rb_node uuid_node;
+ bool name_set;
+ bool uuid_set;
char *name;
char *uuid;
};
-#define NUM_BUCKETS 64
-#define MASK_BUCKETS (NUM_BUCKETS - 1)
-static struct list_head _name_buckets[NUM_BUCKETS];
-static struct list_head _uuid_buckets[NUM_BUCKETS];
+static struct rb_root name_rb_tree = RB_ROOT;
+static struct rb_root uuid_rb_tree = RB_ROOT;
static void dm_hash_remove_all(bool keep_open_devices, bool mark_deferred, bool only_deferred);
*/
static DEFINE_MUTEX(dm_hash_cells_mutex);
-static void init_buckets(struct list_head *buckets)
-{
- unsigned int i;
-
- for (i = 0; i < NUM_BUCKETS; i++)
- INIT_LIST_HEAD(buckets + i);
-}
-
-static int dm_hash_init(void)
-{
- init_buckets(_name_buckets);
- init_buckets(_uuid_buckets);
- return 0;
-}
-
static void dm_hash_exit(void)
{
dm_hash_remove_all(false, false, false);
}
-/*-----------------------------------------------------------------
- * Hash function:
- * We're not really concerned with the str hash function being
- * fast since it's only used by the ioctl interface.
- *---------------------------------------------------------------*/
-static unsigned int hash_str(const char *str)
-{
- const unsigned int hash_mult = 2654435387U;
- unsigned int h = 0;
-
- while (*str)
- h = (h + (unsigned int) *str++) * hash_mult;
-
- return h & MASK_BUCKETS;
-}
-
/*-----------------------------------------------------------------
* Code for looking up a device by name
*---------------------------------------------------------------*/
static struct hash_cell *__get_name_cell(const char *str)
{
- struct hash_cell *hc;
- unsigned int h = hash_str(str);
+ struct rb_node *n = name_rb_tree.rb_node;
- list_for_each_entry (hc, _name_buckets + h, name_list)
- if (!strcmp(hc->name, str)) {
+ while (n) {
+ struct hash_cell *hc = container_of(n, struct hash_cell, name_node);
+ int c = strcmp(hc->name, str);
+ if (!c) {
dm_get(hc->md);
return hc;
}
+ n = c >= 0 ? n->rb_left : n->rb_right;
+ }
return NULL;
}
static struct hash_cell *__get_uuid_cell(const char *str)
{
- struct hash_cell *hc;
- unsigned int h = hash_str(str);
+ struct rb_node *n = uuid_rb_tree.rb_node;
- list_for_each_entry (hc, _uuid_buckets + h, uuid_list)
- if (!strcmp(hc->uuid, str)) {
+ while (n) {
+ struct hash_cell *hc = container_of(n, struct hash_cell, uuid_node);
+ int c = strcmp(hc->uuid, str);
+ if (!c) {
dm_get(hc->md);
return hc;
}
+ n = c >= 0 ? n->rb_left : n->rb_right;
+ }
return NULL;
}
+static void __unlink_name(struct hash_cell *hc)
+{
+ if (hc->name_set) {
+ hc->name_set = false;
+ rb_erase(&hc->name_node, &name_rb_tree);
+ }
+}
+
+static void __unlink_uuid(struct hash_cell *hc)
+{
+ if (hc->uuid_set) {
+ hc->uuid_set = false;
+ rb_erase(&hc->uuid_node, &uuid_rb_tree);
+ }
+}
+
+static void __link_name(struct hash_cell *new_hc)
+{
+ struct rb_node **n, *parent;
+
+ __unlink_name(new_hc);
+
+ new_hc->name_set = true;
+
+ n = &name_rb_tree.rb_node;
+ parent = NULL;
+
+ while (*n) {
+ struct hash_cell *hc = container_of(*n, struct hash_cell, name_node);
+ int c = strcmp(hc->name, new_hc->name);
+ BUG_ON(!c);
+ parent = *n;
+ n = c >= 0 ? &hc->name_node.rb_left : &hc->name_node.rb_right;
+ }
+
+ rb_link_node(&new_hc->name_node, parent, n);
+ rb_insert_color(&new_hc->name_node, &name_rb_tree);
+}
+
+static void __link_uuid(struct hash_cell *new_hc)
+{
+ struct rb_node **n, *parent;
+
+ __unlink_uuid(new_hc);
+
+ new_hc->uuid_set = true;
+
+ n = &uuid_rb_tree.rb_node;
+ parent = NULL;
+
+ while (*n) {
+ struct hash_cell *hc = container_of(*n, struct hash_cell, uuid_node);
+ int c = strcmp(hc->uuid, new_hc->uuid);
+ BUG_ON(!c);
+ parent = *n;
+ n = c > 0 ? &hc->uuid_node.rb_left : &hc->uuid_node.rb_right;
+ }
+
+ rb_link_node(&new_hc->uuid_node, parent, n);
+ rb_insert_color(&new_hc->uuid_node, &uuid_rb_tree);
+}
+
static struct hash_cell *__get_dev_cell(uint64_t dev)
{
struct mapped_device *md;
}
}
- INIT_LIST_HEAD(&hc->name_list);
- INIT_LIST_HEAD(&hc->uuid_list);
+ hc->name_set = hc->uuid_set = false;
hc->md = md;
hc->new_map = NULL;
return hc;
goto bad;
}
- list_add(&cell->name_list, _name_buckets + hash_str(name));
+ __link_name(cell);
if (uuid) {
hc = __get_uuid_cell(uuid);
if (hc) {
- list_del(&cell->name_list);
+ __unlink_name(cell);
dm_put(hc->md);
goto bad;
}
- list_add(&cell->uuid_list, _uuid_buckets + hash_str(uuid));
+ __link_uuid(cell);
}
dm_get(md);
mutex_lock(&dm_hash_cells_mutex);
struct dm_table *table;
int srcu_idx;
- /* remove from the dev hash */
- list_del(&hc->uuid_list);
- list_del(&hc->name_list);
+ /* remove from the dev trees */
+ __unlink_name(hc);
+ __unlink_uuid(hc);
mutex_lock(&dm_hash_cells_mutex);
dm_set_mdptr(hc->md, NULL);
mutex_unlock(&dm_hash_cells_mutex);
static void dm_hash_remove_all(bool keep_open_devices, bool mark_deferred, bool only_deferred)
{
- int i, dev_skipped;
+ int dev_skipped;
+ struct rb_node *n;
struct hash_cell *hc;
struct mapped_device *md;
struct dm_table *t;
down_write(&_hash_lock);
- for (i = 0; i < NUM_BUCKETS; i++) {
- list_for_each_entry(hc, _name_buckets + i, name_list) {
- md = hc->md;
- dm_get(md);
+ for (n = rb_first(&name_rb_tree); n; n = rb_next(n)) {
+ hc = container_of(n, struct hash_cell, name_node);
+ md = hc->md;
+ dm_get(md);
- if (keep_open_devices &&
- dm_lock_for_deletion(md, mark_deferred, only_deferred)) {
- dm_put(md);
- dev_skipped++;
- continue;
- }
+ if (keep_open_devices &&
+ dm_lock_for_deletion(md, mark_deferred, only_deferred)) {
+ dm_put(md);
+ dev_skipped++;
+ continue;
+ }
- t = __hash_remove(hc);
+ t = __hash_remove(hc);
- up_write(&_hash_lock);
+ up_write(&_hash_lock);
- if (t) {
- dm_sync_table(md);
- dm_table_destroy(t);
- }
- dm_put(md);
- if (likely(keep_open_devices))
- dm_destroy(md);
- else
- dm_destroy_immediate(md);
-
- /*
- * Some mapped devices may be using other mapped
- * devices, so repeat until we make no further
- * progress. If a new mapped device is created
- * here it will also get removed.
- */
- goto retry;
+ if (t) {
+ dm_sync_table(md);
+ dm_table_destroy(t);
}
+ dm_put(md);
+ if (likely(keep_open_devices))
+ dm_destroy(md);
+ else
+ dm_destroy_immediate(md);
+
+ /*
+ * Some mapped devices may be using other mapped
+ * devices, so repeat until we make no further
+ * progress. If a new mapped device is created
+ * here it will also get removed.
+ */
+ goto retry;
}
up_write(&_hash_lock);
hc->uuid = new_uuid;
mutex_unlock(&dm_hash_cells_mutex);
- list_add(&hc->uuid_list, _uuid_buckets + hash_str(new_uuid));
+ __link_uuid(hc);
}
/*
/*
* Rename and move the name cell.
*/
- list_del(&hc->name_list);
+ __unlink_name(hc);
old_name = hc->name;
mutex_lock(&dm_hash_cells_mutex);
hc->name = new_name;
mutex_unlock(&dm_hash_cells_mutex);
- list_add(&hc->name_list, _name_buckets + hash_str(new_name));
+ __link_name(hc);
return old_name;
}
return ((void *) param) + param->data_start;
}
+static bool filter_device(struct hash_cell *hc, const char *pfx_name, const char *pfx_uuid)
+{
+ const char *val;
+ size_t val_len, pfx_len;
+
+ val = hc->name;
+ val_len = strlen(val);
+ pfx_len = strnlen(pfx_name, DM_NAME_LEN);
+ if (pfx_len > val_len)
+ return false;
+ if (memcmp(val, pfx_name, pfx_len))
+ return false;
+
+ val = hc->uuid ? hc->uuid : "";
+ val_len = strlen(val);
+ pfx_len = strnlen(pfx_uuid, DM_UUID_LEN);
+ if (pfx_len > val_len)
+ return false;
+ if (memcmp(val, pfx_uuid, pfx_len))
+ return false;
+
+ return true;
+}
+
static int list_devices(struct file *filp, struct dm_ioctl *param, size_t param_size)
{
- unsigned int i;
+ struct rb_node *n;
struct hash_cell *hc;
size_t len, needed = 0;
struct gendisk *disk;
* Loop through all the devices working out how much
* space we need.
*/
- for (i = 0; i < NUM_BUCKETS; i++) {
- list_for_each_entry (hc, _name_buckets + i, name_list) {
- needed += align_val(offsetof(struct dm_name_list, name) + strlen(hc->name) + 1);
- needed += align_val(sizeof(uint32_t));
- }
+ for (n = rb_first(&name_rb_tree); n; n = rb_next(n)) {
+ hc = container_of(n, struct hash_cell, name_node);
+ if (!filter_device(hc, param->name, param->uuid))
+ continue;
+ needed += align_val(offsetof(struct dm_name_list, name) + strlen(hc->name) + 1);
+ needed += align_val(sizeof(uint32_t) * 2);
+ if (param->flags & DM_UUID_FLAG && hc->uuid)
+ needed += align_val(strlen(hc->uuid) + 1);
}
/*
/*
* Now loop through filling out the names.
*/
- for (i = 0; i < NUM_BUCKETS; i++) {
- list_for_each_entry (hc, _name_buckets + i, name_list) {
- if (old_nl)
- old_nl->next = (uint32_t) ((void *) nl -
- (void *) old_nl);
- disk = dm_disk(hc->md);
- nl->dev = huge_encode_dev(disk_devt(disk));
- nl->next = 0;
- strcpy(nl->name, hc->name);
-
- old_nl = nl;
- event_nr = align_ptr(nl->name + strlen(hc->name) + 1);
- *event_nr = dm_get_event_nr(hc->md);
- nl = align_ptr(event_nr + 1);
+ for (n = rb_first(&name_rb_tree); n; n = rb_next(n)) {
+ void *uuid_ptr;
+ hc = container_of(n, struct hash_cell, name_node);
+ if (!filter_device(hc, param->name, param->uuid))
+ continue;
+ if (old_nl)
+ old_nl->next = (uint32_t) ((void *) nl -
+ (void *) old_nl);
+ disk = dm_disk(hc->md);
+ nl->dev = huge_encode_dev(disk_devt(disk));
+ nl->next = 0;
+ strcpy(nl->name, hc->name);
+
+ old_nl = nl;
+ event_nr = align_ptr(nl->name + strlen(hc->name) + 1);
+ event_nr[0] = dm_get_event_nr(hc->md);
+ event_nr[1] = 0;
+ uuid_ptr = align_ptr(event_nr + 2);
+ if (param->flags & DM_UUID_FLAG) {
+ if (hc->uuid) {
+ event_nr[1] |= DM_NAME_LIST_FLAG_HAS_UUID;
+ strcpy(uuid_ptr, hc->uuid);
+ uuid_ptr = align_ptr(uuid_ptr + strlen(hc->uuid) + 1);
+ } else {
+ event_nr[1] |= DM_NAME_LIST_FLAG_DOESNT_HAVE_UUID;
+ }
}
+ nl = uuid_ptr;
}
/*
* If mismatch happens, security may be compromised due to buffer
{
int r;
- r = dm_hash_init();
- if (r)
- return r;
-
r = misc_register(&_dm_misc);
if (r) {
DMERR("misc_register failed for control device");
- dm_hash_exit();
return r;
}
projects / linux-2.6-microblaze.git / blobdiff