From de418f0f6bc0c5d272c5e0bb1428e1e212d356d5 Mon Sep 17 00:00:00 2001 From: Vasiliy Ulyanov Date: Mon, 28 Apr 2014 16:20:30 +0400 Subject: [PATCH] [FEATURE] File analysis: add ks_map Change-Id: I59db28c70ac364d6278ff4ebe7608243bc878762 Signed-off-by: Vasiliy Ulyanov --- ks_features/Kbuild | 3 +- ks_features/ks_map.c | 203 +++++++++++++++++++++++++++++++++++++++++++++++++++ ks_features/ks_map.h | 36 +++++++++ 3 files changed, 241 insertions(+), 1 deletion(-) create mode 100644 ks_features/ks_map.c create mode 100644 ks_features/ks_map.h diff --git a/ks_features/Kbuild b/ks_features/Kbuild index 4cf3445..6e09efa 100644 --- a/ks_features/Kbuild +++ b/ks_features/Kbuild @@ -3,4 +3,5 @@ KBUILD_EXTRA_SYMBOLS = $(src)/../kprobe/Module.symvers \ $(src)/../writer/Module.symvers obj-m := swap_ks_features.o -swap_ks_features-y := ks_features.o +swap_ks_features-y := ks_features.o \ + ks_map.o diff --git a/ks_features/ks_map.c b/ks_features/ks_map.c new file mode 100644 index 0000000..5590277 --- /dev/null +++ b/ks_features/ks_map.c @@ -0,0 +1,203 @@ +#include +#include +#include +#include "ks_map.h" + +struct entry { + struct rb_node node; + void *data; +}; + +static inline void *entry_data(struct entry *entry) +{ + return entry->data; +} + +static struct entry *alloc_entry(struct map *map, void *data) +{ + struct entry *entry = kmalloc(sizeof(*entry), GFP_ATOMIC); + + if (entry) { + entry->data = data; + RB_CLEAR_NODE(&entry->node); + } + + return entry; +} + +static void *free_entry(struct map *map, struct entry *entry) +{ + void *data = entry_data(entry); + + kfree(entry); + + return data; +} + +static struct entry *__search(struct map *map, void *key) +{ + struct rb_root *root = &map->root; + struct rb_node *node = root->rb_node; + key_func_t key_f = map->key_f; + cmp_func_t cmp_f = map->cmp_f; + + while (node) { + struct entry *entry = rb_entry(node, struct entry, node); + int result = cmp_f(key_f(entry_data(entry)), key); + + if (result < 0) + node = node->rb_left; + else if (result > 0) + node = node->rb_right; + else + return entry; + } + + return NULL; +} + +void *search(struct map *map, void *key) +{ + struct entry *entry = __search(map, key); + + return (entry ? entry_data(entry): NULL); +} + +static void *__remove(struct map *map, struct entry *entry) +{ + struct rb_root *root = &map->root; + + rb_erase(&entry->node, root); + RB_CLEAR_NODE(&entry->node); + map->size--; + + return free_entry(map, entry); +} + +void *remove(struct map *map, void *key) +{ + struct entry *entry = __search(map, key); + + /* Removes entry from the tree but does not free the data */ + return (entry ? __remove(map, entry): NULL); +} + +static void *__replace(struct map *map, struct entry *old, struct entry *new) +{ + struct rb_root *root = &map->root; + + rb_replace_node(&old->node, &new->node, root); + + return free_entry(map, old); +} + +void *replace(struct map *map, void *data) +{ + struct entry *old, *new; + + old = __search(map, map->key_f(data)); + if (old) { + new = alloc_entry(map, data); + if (!new) + return ERR_PTR(-ENOMEM); + + return __replace(map, old, new); + } + + return ERR_PTR(-ESRCH); +} + +int insert(struct map *map, void *data) +{ + struct rb_root *root = &map->root; + struct rb_node **new = &(root->rb_node), *parent = NULL; + key_func_t key_f = map->key_f; + cmp_func_t cmp_f = map->cmp_f; + void *key = key_f(data); + struct entry *entry; + + /* Figure out where to put new node */ + while (*new) { + struct entry *this = rb_entry(*new, struct entry, node); + int result = cmp_f(key_f(entry_data(this)), key); + + parent = *new; + if (result < 0) + new = &((*new)->rb_left); + else if (result > 0) + new = &((*new)->rb_right); + else /* entry already inserted */ + return -EEXIST; + } + + entry = alloc_entry(map, data); + if (!entry) + return -ENOMEM; + + /* Add new node and rebalance tree. */ + rb_link_node(&entry->node, parent, new); + rb_insert_color(&entry->node, root); + map->size++; + + return 0; +} + +int for_each_entry(struct map *map, act_func_t func, void *arg) +{ + struct rb_root *root = &map->root; + struct rb_node *node = rb_first(root); + int ret = 0; + + while (node) { + struct entry *entry = rb_entry(node, struct entry, node); + + /* Stop iteration if actor returns non zero */ + ret = func(entry_data(entry), arg); + if (ret) + break; + + node = rb_next(node); + } + + return ret; +} + +int for_each_entry_reverse(struct map *map, act_func_t func, void *arg) +{ + struct rb_root *root = &map->root; + struct rb_node *node = rb_last(root); + int ret = 0; + + while (node) { + struct entry *entry = rb_entry(node, struct entry, node); + + /* Stop iteration if actor returns non zero */ + ret = func(entry_data(entry), arg); + if (ret) + break; + + node = rb_prev(node); + } + + return ret; +} + +void clear(struct map *map, act_func_t destructor, void *arg) +{ + struct rb_root *root = &map->root; + struct rb_node *node = root->rb_node; + + while (node) { + struct entry *entry = rb_entry(node, struct entry, node); + void *data = __remove(map, entry); + + /* call the data 'destructor' if supplied */ + if (destructor) + destructor(data, arg); + + node = root->rb_node; + } + + WARN(map->size, "ks_map size: %d\n", map->size); + map->root = RB_ROOT; +} diff --git a/ks_features/ks_map.h b/ks_features/ks_map.h new file mode 100644 index 0000000..8d86a9c --- /dev/null +++ b/ks_features/ks_map.h @@ -0,0 +1,36 @@ +#ifndef __KS_MAP__ +#define __KS_MAP__ + +#include + +typedef void *(*key_func_t)(void *); +typedef int (*cmp_func_t)(void *, void *); +typedef int (*act_func_t)(void *, void *); + +struct map { + struct rb_root root; + int size; + key_func_t key_f; + cmp_func_t cmp_f; +}; + +#define __MAP_INITIALIZER(_key_f, _cmp_f) \ + { \ + .root = RB_ROOT, \ + .size = 0, \ + .key_f = _key_f, \ + .cmp_f = _cmp_f \ + } + +#define DEFINE_MAP(_name, _key_f, _cmp_f) \ + struct map _name = __MAP_INITIALIZER(_key_f, _cmp_f) + +void *search(struct map *map, void *key); +void *remove(struct map *map, void *key); +void *replace(struct map *map, void *data); +int insert(struct map *map, void *data); +int for_each_entry(struct map *map, act_func_t func, void *arg); +int for_each_entry_reverse(struct map *map, act_func_t act, void *arg); +void clear(struct map *map, act_func_t destructor, void *arg); + +#endif /* __KS_MAP__ */ -- 2.7.4