[CRIU] [PATCH 28/28] rst: replace binary tree for files with hash table

[Kinsbursky Stanislav]

From: Stanislav Kinsbursky <skinsbursky at openvz.org>

Signed-off-by: Stanislav Kinsbursky <skinsbursky at openvz.org>
---
 file-ids.c         |   78 +---------------------------------------------------
 files.c            |   75 ++++++++++++++++++++++++++++++++++++++++++++++++++
 include/file-ids.h |   11 -------
 include/files.h    |   12 ++++++++
 4 files changed, 88 insertions(+), 88 deletions(-)
-------------- next part --------------
diff --git a/file-ids.c b/file-ids.c
index 0ba9797..e155931 100644
--- a/file-ids.c
+++ b/file-ids.c
@@ -16,6 +16,7 @@
 #include "compiler.h"
 #include "syscall.h"
 #include "util.h"
+#include "files.h"
 
 /*
  * We track shared files by global rbtree, where each node might
@@ -76,8 +77,6 @@ struct file_node {
 
 static struct rb_root dump_file_forest[FD_INFO_MAX];
 
-static struct rb_root *restore_file_forest;
-
 static int compare_map_files(pid_t pid1, pid_t pid2, u8 fd1, u8 fd2)
 {
 	return 0;
@@ -200,78 +199,3 @@ long file_collect(pid_t pid, int fd, const struct file_entry *p, u8 *new_entry)
 	return e->u.id;
 }
 
-static struct file_node *file_search_tree(struct rb_root *root, u64 id)
-{
-	struct rb_node *node = root->rb_node;
-
-	while (node) {
-		struct file_node *this = rb_entry(node, struct file_node, node);
-
-		if (id < this->u.id)
-			node = node->rb_left;
-		else if (id > this->u.id)
-			node = node->rb_right;
-		else
-			return this;
-	}
-	return NULL;
-}
-
-struct file_info *file_search(u8 type, u64 id)
-{
-	struct file_node *node;
-
-	BUG_ON(restore_file_forest == NULL);
-	node = file_search_tree(&restore_file_forest[type], id);
-	if (node)
-		return &node->info;
-	return NULL;
-}
-
-int file_add(const struct file_entry *rfe)
-{
-	struct rb_node *node;
-	struct rb_node **new;
-	struct rb_node *parent = NULL;
-	struct rb_root *fd_root;
-	struct file_node *e;
-
-	if (rfe->type >= FD_INFO_MAX)
-		return -ENOTSUP;
-
-	if (restore_file_forest == NULL) {
-		restore_file_forest = xmalloc_shm(sizeof(struct rb_root) * FD_INFO_MAX);
-		if (restore_file_forest == NULL)
-			return -ENOMEM;
-	}
-
-	fd_root = &restore_file_forest[rfe->type];
-	node = fd_root->rb_node;
-	new = &fd_root->rb_node;
-
-	while (node) {
-		struct file_node *this = rb_entry(node, struct file_node, node);
-
-		parent = *new;
-		if (rfe->id < this->u.id)
-			node = node->rb_left, new = &((*new)->rb_left);
-		else if (rfe->id > this->u.id)
-			node = node->rb_right, new = &((*new)->rb_right);
-		else
-			return -EEXIST;
-	}
-
-	e = xmalloc_shm(sizeof(*e));
-	if (!e)
-		return -ENOMEM;
-
-	e->u.id		= rfe->id;
-	e->info.rfe	= rfe;
-	e->info.fd	= FD_ID_INVALID;
-	e->info.pid	= 0;
-	INIT_LIST_HEAD(&e->info.recipients);
-
-	rb_init_node(&e->node);
-	rb_link_and_balance(fd_root, &e->node, parent, new);
-	return 0;
-}
diff --git a/files.c b/files.c
index 2d882cf..f1434b8 100644
--- a/files.c
+++ b/files.c
@@ -20,6 +20,81 @@
 #include "util-net.h"
 #include "lock.h"
 #include "file-ids.h"
+#include "image.h"
+
+#define HASH_TABLE_SIZE		32
+
+struct file_hash_entry {
+	struct list_head	list;
+	u64			id;
+	struct file_info	info;
+};
+
+struct files_hash {
+	struct list_head lists[HASH_TABLE_SIZE];
+};
+
+struct files_hash *files_hash_array;
+
+struct file_info *file_search(u8 type, u64 id)
+{
+	struct files_hash *hash;
+	struct list_head *hash_list;
+	struct file_hash_entry *e;
+
+	if (type >= FD_INFO_MAX)
+		return NULL;
+
+	hash = &files_hash_array[type];
+	hash_list = &hash->lists[id & (HASH_TABLE_SIZE - 1)];
+
+	list_for_each_entry(e, hash_list, list) {
+		if (e->id == id)
+			return &e->info;
+	}
+	return NULL;
+}
+
+static int file_add(const struct file_entry *rfe)
+{
+	struct files_hash *hash;
+	struct list_head *hash_list;
+	struct file_hash_entry *e;
+
+	if (rfe->type >= FD_INFO_MAX)
+		return -ENOTSUP;
+
+	if (files_hash_array == NULL) {
+		int i, j;
+
+		files_hash_array = xmalloc_shm(sizeof(struct files_hash) * FD_INFO_MAX);
+		if (files_hash_array == NULL)
+			return -ENOMEM;
+		for (i = 0; i < FD_INFO_MAX; i++) {
+			hash = &files_hash_array[i];
+			for (j = 0; j < HASH_TABLE_SIZE; j++)
+				INIT_LIST_HEAD(&hash->lists[j]);
+		}
+	}
+
+	if (file_search(rfe->type, rfe->id))
+		return -EEXIST;
+
+	e = xmalloc_shm(sizeof(*e));
+	if (!e)
+		return -ENOMEM;
+
+	e->id		= rfe->id;
+	e->info.rfe	= rfe;
+	e->info.fd	= FD_ID_INVALID;
+	e->info.pid	= 0;
+	INIT_LIST_HEAD(&e->info.recipients);
+
+	hash = &files_hash_array[rfe->type];
+	hash_list = &hash->lists[rfe->id & (HASH_TABLE_SIZE - 1)];
+	list_add_tail(&e->list, hash_list);
+	return 0;
+}
 
 struct file_recipient {
 	struct list_head	list;
diff --git a/include/file-ids.h b/include/file-ids.h
index c9d49be..25b1e82 100644
--- a/include/file-ids.h
+++ b/include/file-ids.h
@@ -5,7 +5,6 @@
 #include "types.h"
 #include "rbtree.h"
 #include "image.h"
-#include "list.h"
 
 #define FD_ID_INVALID		(-1U)
 #define FD_PID_INVALID		((int)-2UL)
@@ -13,16 +12,6 @@
 #define MAKE_FD_GENID(dev, ino, pos) \
 	(((u32)(dev) ^ (u32)(ino) ^ (u32)(pos)))
 
-struct file_info {
-	int			fd;
-	int			pid;
-	const struct file_entry	*rfe;
-	struct list_head	recipients;
-};
-
 extern long file_collect(pid_t pid, int fd, const struct file_entry *p, u8 *new_entry);
 
-extern struct file_info *file_search(u8 type, u64 id);
-extern int file_add(const struct file_entry *rfe);
-
 #endif /* FILE_IDS_H__ */
diff --git a/include/files.h b/include/files.h
index 1bfa020..9eef25c 100644
--- a/include/files.h
+++ b/include/files.h
@@ -5,6 +5,7 @@
 #include "types.h"
 #include "list.h"
 #include "image.h"
+#include "list.h"
 
 enum fdinfo_states {
 	FD_STATE_PREP,		/* Create unix sockets */
@@ -43,4 +44,15 @@ extern int prepare_fd_pid(int pid);
 extern int prepare_files(void);
 extern int get_filemap_fd(int pid, struct vma_entry *vma_entry);
 
+struct file_entry;
+
+struct file_info {
+	int			fd;
+	int			pid;
+	const struct file_entry	*rfe;
+	struct list_head	recipients;
+};
+
+extern struct file_info *file_search(u8 type, u64 id);
+
 #endif /* FILES_H_ */