This container is mapping from an index datatype to a "value"
datatatype, using rbtree for the implementation.
This datatype is used for various purposes by ktf to
store and find data related to the actual test cases.
ktf_map.c: Implementation of a kernel version independent std::map like API
ktf_map.h: simple objects with key lookup to be inlined into a
Signed-off-by: Knut Omang <knut.omang@xxxxxxxxxx>
---
tools/testing/selftests/ktf/kernel/ktf_map.c | 261 ++++++++++++++++++++-
tools/testing/selftests/ktf/kernel/ktf_map.h | 154 ++++++++++++-
2 files changed, 415 insertions(+)
create mode 100644 tools/testing/selftests/ktf/kernel/ktf_map.c
create mode 100644 tools/testing/selftests/ktf/kernel/ktf_map.h
diff --git a/tools/testing/selftests/ktf/kernel/ktf_map.c b/tools/testing/selftests/ktf/kernel/ktf_map.c
new file mode 100644
index 0000000..78ae5fb
--- /dev/null
+++ b/tools/testing/selftests/ktf/kernel/ktf_map.c
@@ -0,0 +1,261 @@
+/*
+ * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.
+ * Author: Knut Omang <knut.omang@xxxxxxxxxx>
+ *
+ * SPDX-License-Identifier: GPL-2.0
+ *
+ * ktf_map.c: Implementation of a kernel version independent std::map like API
+ * (made abstract to allow impl to change)
+ */
+
+#include "ktf_map.h"
+#include "ktf.h"
+
+void ktf_map_init(struct ktf_map *map, ktf_map_elem_comparefn elem_comparefn,
+ ktf_map_elem_freefn elem_freefn)
+{
+ map->root = RB_ROOT;
+ map->size = 0;
+ map->elem_comparefn = elem_comparefn;
+ map->elem_freefn = elem_freefn;
+ spin_lock_init(&map->lock);
+}
+
+int ktf_map_elem_init(struct ktf_map_elem *elem, const char *key)
+{
+ memcpy(elem->key, key, KTF_MAX_KEY);
+ /* For strings that are too long, ensure truncation at
+ * KTF_MAX_NAME == KTF_MAX_KEY - 1 length:
+ */
+ elem->key[KTF_MAX_NAME] = '\0';
+ elem->map = NULL;
+ kref_init(&elem->refcount);
+ return 0;
+}
+
+/* A convenience unsigned int compare function as an alternative
+ * to the string compare:
+ */
+int ktf_uint_compare(const char *ac, const char *bc)
+{
+ unsigned int a = *((unsigned int *)ac);
+ unsigned int b = *((unsigned int *)bc);
+
+ return a > b ? 1 : (a < b ? -1 : 0);
+}
+EXPORT_SYMBOL(ktf_uint_compare);
+
+/* Copy "elem"s key representation into "name". For cases where no
+ * compare function is defined - i.e. string keys - just copy string,
+ * otherwise name is hexascii of first 8 bytes of key.
+ */
+char *
+ktf_map_elem_name(struct ktf_map_elem *elem, char *name)
+{
+ if (!name)
+ return NULL;
+
+ if (!elem || !elem->map)
+ (void)strlcpy(name, "<none>", KTF_MAX_NAME);
+ else if (!elem->map->elem_comparefn)
+ (void)strlcpy(name, elem->key, KTF_MAX_NAME);
+ else
+ (void)snprintf(name, KTF_MAX_NAME, "'%*ph'", 8, elem->key);
+
+ return name;
+}
+
+/* Called when refcount of elem is 0. */
+static void ktf_map_elem_release(struct kref *kref)
+{
+ struct ktf_map_elem *elem = container_of(kref, struct ktf_map_elem,
+ refcount);
+ struct ktf_map *map = elem->map;
+ char name[KTF_MAX_KEY];
+
+ tlog(T_DEBUG_V, "Releasing %s, %s free function",
+ ktf_map_elem_name(elem, name),
+ map && map->elem_freefn ? "calling" : "no");
+ if (map && map->elem_freefn)
+ map->elem_freefn(elem);
+}
+
+void ktf_map_elem_put(struct ktf_map_elem *elem)
+{
+ char name[KTF_MAX_KEY];
+
+ tlog(T_DEBUG_V, "Decreasing refcount for %s to %d",
+ ktf_map_elem_name(elem, name),
+ refcount_read(&elem->refcount.refcount) - 1);
+ kref_put(&elem->refcount, ktf_map_elem_release);
+}
+
+void ktf_map_elem_get(struct ktf_map_elem *elem)
+{
+ char name[KTF_MAX_KEY];
+
+ tlog(T_DEBUG_V, "Increasing refcount for %s to %d",
+ ktf_map_elem_name(elem, name),
+ refcount_read(&elem->refcount.refcount) + 1);
+ kref_get(&elem->refcount);
+}
+
+struct ktf_map_elem *ktf_map_find(struct ktf_map *map, const char *key)
+{
+ struct rb_node *node;
+ unsigned long flags;
+
+ /* may be called in interrupt context */
+ spin_lock_irqsave(&map->lock, flags);
+ node = map->root.rb_node;
+
+ while (node) {
+ struct ktf_map_elem *elem = container_of(node, struct ktf_map_elem, node);
+ int result;
+
+ if (map->elem_comparefn)
+ result = map->elem_comparefn(key, elem->key);
+ else
+ result = strncmp(key, elem->key, KTF_MAX_KEY);
+
+ if (result < 0) {
+ node = node->rb_left;
+ } else if (result > 0) {
+ node = node->rb_right;
+ } else {
+ ktf_map_elem_get(elem);
+ spin_unlock_irqrestore(&map->lock, flags);
+ return elem;
+ }
+ }
+ spin_unlock_irqrestore(&map->lock, flags);
+ return NULL;
+}
+
+/* Find the first map elem in 'map' */
+struct ktf_map_elem *ktf_map_find_first(struct ktf_map *map)
+{
+ struct ktf_map_elem *elem = NULL;
+ struct rb_node *node;
+ unsigned long flags;
+
+ spin_lock_irqsave(&map->lock, flags);
+ node = rb_first(&map->root);
+ if (node) {
+ elem = container_of(node, struct ktf_map_elem, node);
+ ktf_map_elem_get(elem);
+ }
+ spin_unlock_irqrestore(&map->lock, flags);
+ return elem;
+}
+
+/* Find the next element in the map after 'elem' if any */
+struct ktf_map_elem *ktf_map_find_next(struct ktf_map_elem *elem)
+{
+ struct ktf_map_elem *next = NULL;
+ struct ktf_map *map = elem->map;
+ struct rb_node *node;
+ unsigned long flags;
+
+ if (!elem->map)
+ return NULL;
+ spin_lock_irqsave(&map->lock, flags);
+ node = rb_next(&elem->node);
+
+ /* Assumption here - we don't need ref to elem any more.
+ * Common usage pattern is
+ *
+ * for (elem = ktf_map_elem_first(map); elem != NULL;
+ * elem = ktf_map_find_next(elem))
+ *
+ * but if other use cases occur we may need to revisit.
+ * This assumption allows us to define our _for_each macros
+ * and still manage refcounts.
+ */
+ ktf_map_elem_put(elem);
+
+ if (node) {
+ next = container_of(node, struct ktf_map_elem, node);
+ ktf_map_elem_get(next);
+ }
+ spin_unlock_irqrestore(&map->lock, flags);
+ return next;
+}
+
+int ktf_map_insert(struct ktf_map *map, struct ktf_map_elem *elem)
+{
+ struct rb_node **newobj, *parent = NULL;
+ unsigned long flags;
+
+ spin_lock_irqsave(&map->lock, flags);
+ newobj = &map->root.rb_node;
+ while (*newobj) {
+ struct ktf_map_elem *this = container_of(*newobj, struct ktf_map_elem, node);
+ int result;
+
+ if (map->elem_comparefn)
+ result = map->elem_comparefn(elem->key, this->key);
+ else
+ result = strncmp(elem->key, this->key, KTF_MAX_KEY);
+
+ parent = *newobj;
+ if (result < 0) {
+ newobj = &((*newobj)->rb_left);
+ } else if (result > 0) {
+ newobj = &((*newobj)->rb_right);
+ } else {
+ spin_unlock_irqrestore(&map->lock, flags);
+ return -EEXIST;
+ }
+ }
+
+ /* Add newobj node and rebalance tree. */
+ rb_link_node(&elem->node, parent, newobj);
+ rb_insert_color(&elem->node, &map->root);
+ elem->map = map;
+ map->size++;
+ /* Bump reference count for map reference */
+ ktf_map_elem_get(elem);
+ spin_unlock_irqrestore(&map->lock, flags);
+ return 0;
+}
+
+void ktf_map_remove_elem(struct ktf_map *map, struct ktf_map_elem *elem)
+{
+ if (elem) {
+ rb_erase(&elem->node, &map->root);
+ map->size--;
+ ktf_map_elem_put(elem);
+ }
+}
+
+struct ktf_map_elem *ktf_map_remove(struct ktf_map *map, const char *key)
+{
+ struct ktf_map_elem *elem;
+ unsigned long flags;
+
+ elem = ktf_map_find(map, key);
+ spin_lock_irqsave(&map->lock, flags);
+ ktf_map_remove_elem(map, elem);
+ spin_unlock_irqrestore(&map->lock, flags);
+ return elem;
+}
+
+void ktf_map_delete_all(struct ktf_map *map)
+{
+ struct ktf_map_elem *elem;
+ struct rb_node *node;
+ unsigned long flags;
+
+ spin_lock_irqsave(&map->lock, flags);
+ do {
+ node = rb_first(&(map)->root);
+ if (node) {
+ rb_erase(node, &(map)->root);
+ map->size--;
+ elem = container_of(node, struct ktf_map_elem, node);
+ ktf_map_elem_put(elem);
+ }
+ } while (node);
+ spin_unlock_irqrestore(&map->lock, flags);
+}
diff --git a/tools/testing/selftests/ktf/kernel/ktf_map.h b/tools/testing/selftests/ktf/kernel/ktf_map.h
new file mode 100644
index 0000000..1c8ae9b
--- /dev/null
+++ b/tools/testing/selftests/ktf/kernel/ktf_map.h
@@ -0,0 +1,154 @@
+/*
+ * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.
+ * Author: Knut Omang <knut.omang@xxxxxxxxxx>
+ *
+ * SPDX-License-Identifier: GPL-2.0
+ *
+ * ktf_map.h: simple objects with key lookup to be inlined into a
+ * larger object
+ */
+
+#ifndef _KTF_MAP_H
+#define _KTF_MAP_H
+#include <linux/kref.h>
+#include <linux/version.h>
+#include <linux/rbtree.h>
+
+#define KTF_MAX_KEY 64
+#define KTF_MAX_NAME (KTF_MAX_KEY - 1)
+
+struct ktf_map_elem;
+
+/* Compare function called to compare element keys - optional and if
+ * not specified we revert to string comparison. Should return < 0
+ * if first key < second, > 0 if first key > second, and 0 if they are
+ * identical.
+ */
+typedef int (*ktf_map_elem_comparefn)(const char *, const char *);
+
+/* A convenience unsigned int compare function as an alternative
+ * to the string compare:
+ */
+int ktf_uint_compare(const char *a, const char *b);
+
+/* Free function called when elem refcnt is 0 - optional and of course for
+ * dynamically-allocated elems only.
+ */
+typedef void (*ktf_map_elem_freefn)(struct ktf_map_elem *);
+
+struct ktf_map {
+ struct rb_root root; /* The rb tree holding the map */
+ size_t size; /* Current size (number of elements) of the map */
+ spinlock_t lock; /* held for map lookup etc */
+ ktf_map_elem_comparefn elem_comparefn; /* Key comparison function */
+ ktf_map_elem_freefn elem_freefn; /* Free function */
+};
+
+struct ktf_map_elem {
+ struct rb_node node; /* Linkage for the map */
+ char key[KTF_MAX_KEY+1] __aligned(8);
+ /* Key of the element - must be unique within the same map */
+ struct ktf_map *map; /* owning map */
+ struct kref refcount; /* reference count for element */
+};
+
+#define __KTF_MAP_INITIALIZER(_mapname, _elem_comparefn, _elem_freefn) \
+ { \
+ .root = RB_ROOT, \
+ .size = 0, \
+ .lock = __SPIN_LOCK_UNLOCKED(_mapname), \
+ .elem_comparefn = _elem_comparefn, \
+ .elem_freefn = _elem_freefn, \
+ }
+
+#define DEFINE_KTF_MAP(_mapname, _elem_comparefn, _elem_freefn) \
+ struct ktf_map _mapname = __KTF_MAP_INITIALIZER(_mapname, _elem_comparefn, _elem_freefn)
+
+void ktf_map_init(struct ktf_map *map, ktf_map_elem_comparefn elem_comparefn,
+ ktf_map_elem_freefn elem_freefn);
+
+/* returns 0 upon success or -errno upon error */
+int ktf_map_elem_init(struct ktf_map_elem *elem, const char *key);
+
+/* increase/reduce reference count to element. If count reaches 0, the
+ * free function associated with map (if any) is called.
+ */
+void ktf_map_elem_get(struct ktf_map_elem *elem);
+void ktf_map_elem_put(struct ktf_map_elem *elem);
+
+char *ktf_map_elem_name(struct ktf_map_elem *elem, char *name);
+
+/* Insert a new element in map - return 0 iff 'elem' was inserted or -1 if
+ * the key already existed - duplicates are not insterted.
+ */
+int ktf_map_insert(struct ktf_map *map, struct ktf_map_elem *elem);
+
+/* Find and return the element with 'key' */
+struct ktf_map_elem *ktf_map_find(struct ktf_map *map, const char *key);
+
+/* Find the first map elem in 'map' with reference count increased. */
+struct ktf_map_elem *ktf_map_find_first(struct ktf_map *map);
+
+/* Find the next element in the map after 'elem' if any. Decreases refcount
+ * for "elem" and increases it for returned map element - this helps manage
+ * reference counts when iterating over map elements.
+ */
+struct ktf_map_elem *ktf_map_find_next(struct ktf_map_elem *elem);
+
+/* Remove the element 'key' from the map and return a pointer to it with
+ * refcount increased.
+ */
+struct ktf_map_elem *ktf_map_remove(struct ktf_map *map, const char *key);
+
+/* Remove specific element elem from the map. Refcount is not increased
+ * as caller must already have had a reference.
+ */
+void ktf_map_remove_elem(struct ktf_map *map, struct ktf_map_elem *elem);
+
+void ktf_map_delete_all(struct ktf_map *map);
+
+static inline size_t ktf_map_size(struct ktf_map *map) {
+ return map->size;
+}
+
+static inline bool ktf_map_empty(struct ktf_map *map) {
+ return map->size == 0;
+}
+
+/* Gets first entry with refcount of entry increased for caller. */
+#define ktf_map_first_entry(_map, _type, _member) \
+ ktf_map_empty(_map) ? NULL : \
+ container_of(ktf_map_find_first(_map), _type, _member)
+
+/* Gets next elem after "pos", decreasing refcount for pos and increasing
+ * it for returned entry.
+ */
+#define ktf_map_next_entry(_pos, _member) ({ \
+ struct ktf_map_elem *_e = ktf_map_find_next(&(_pos)->_member); \
+ _e ? container_of(_e, typeof(*_pos), _member) : NULL; \
+})
+
+/* Iterates over map elements, incrementing refcount for current element and
+ * decreasing it when we iterate to the next element. Important - if you
+ * break out of the loop via break/return, ensure ktf_map_elem_put(pos)
+ * is called for current element since we have a reference to it for the
+ * current loop body iteration.
+ */
+#define ktf_map_for_each(pos, map) \
+ for (pos = ktf_map_find_first(map); pos != NULL; pos = ktf_map_find_next(pos))
+
+/* Iterate over map elements in similar manner as above but using
+ * container_of() wrappers to work with the type embedding a
+ * "struct ktf_map_elem".
+ */
+#define ktf_map_for_each_entry(_pos, _map, _member) \
+ for (_pos = ktf_map_first_entry(_map, typeof(*_pos), _member); \
+ _pos != NULL; \
+ _pos = ktf_map_next_entry(_pos, _member))
+
+#define ktf_map_find_entry(_map, _key, _type, _member) ({ \
+ struct ktf_map_elem *_entry = ktf_map_find(_map, _key); \
+ _entry ? container_of(_entry, _type, _member) : NULL; \
+})
+
+#endif
--
git-series 0.9.1
