[CRIU] [PATCH 28/28] rst: replace binary tree for files with
hash table
Andrew Vagin
avagin at parallels.com
Thu Mar 22 15:39:56 EDT 2012
Without an commit message I can not understand why you decided to do that.
The difficulty of searching in binary tree is log(n).
The difficulty of searching in hash table is n/HASH_TABLE_SIZE
For example if n=1024
log(n)=10, but n/n/HASH_TABLE_SIZE=32...
Pls, add more details.
On Thu, Mar 22, 2012 at 09:00:39PM +0300, Kinsbursky Stanislav wrote:
> 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(-)
> 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_ */
> _______________________________________________
> CRIU mailing list
> CRIU at openvz.org
> https://openvz.org/mailman/listinfo/criu
More information about the CRIU
mailing list