summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorKent Overstreet <koverstreet@google.com>2013-06-14 15:58:26 -0700
committerKent Overstreet <koverstreet@google.com>2013-06-14 15:58:26 -0700
commit9db900062844e23377ee76b69554ade1ae41ae3b (patch)
tree0de08b621587d60665a7ad0765e44a6e435de4cd
parent39bcd629373f0e4c491b95d89d09c0ffb0a59854 (diff)
non radix tree idr version
-rw-r--r--include/linux/idr.h47
-rw-r--r--lib/idr.c236
2 files changed, 283 insertions, 0 deletions
diff --git a/include/linux/idr.h b/include/linux/idr.h
index f2830614d9b7..029941562c66 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -96,6 +96,53 @@ static inline int idr_alloc(struct idr *idr, void *ptr, gfp_t gfp)
return idr_alloc_range(idr, ptr, 0, 0, gfp);
}
+#if 0
+#define IDR_FIRST_LAYER_SIZE (1 << 7)
+#define IDR_LAYERS 14
+
+struct idr {
+ struct ida ida;
+ void __rcu **layers[IDR_LAYERS];
+};
+
+static inline unsigned __idr_layer_from_id(unsigned *id)
+{
+ unsigned i, size = IDR_FIRST_LAYER_SIZE;
+
+ for (i = 0; *id >= size; i++) {
+ *id -= size;
+ size *= 2;
+ }
+
+ return i;
+}
+
+/**
+ * idr_find - return pointer for given id
+ * @idr: idr handle
+ * @id: lookup key
+ *
+ * Return the pointer given the id it has been registered with. A %NULL
+ * return indicates that @id is not valid or you passed %NULL in
+ * idr_alloc().
+ */
+static inline void *idr_find(struct idr *idr, unsigned id)
+{
+ unsigned layer;
+ void *ptr = NULL;
+
+ rcu_read_lock();
+ layer = __idr_layer_from_id(&id);
+
+ if (layer < IDR_LAYERS && idr->layers[layer])
+ ptr = rcu_dereference(rcu_dereference(idr->layers[layer])[id]);
+
+ rcu_read_unlock();
+
+ return ptr;
+}
+#endif
+
struct idr {
struct ida ida;
unsigned cur;
diff --git a/lib/idr.c b/lib/idr.c
index a9a7168b6431..34d4ee985139 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -113,6 +113,242 @@ void ida_init(struct ida *ida)
EXPORT_SYMBOL(ida_init);
/* IDR */
+#if 0
+/**
+ * idr_find_next - lookup next object of id to given id.
+ * @idp: idr handle
+ * @nextidp: pointer to lookup key
+ *
+ * Returns pointer to registered object with id, which is next number to
+ * given id. After being looked up, *@nextidp will be updated for the next
+ * iteration.
+ *
+ * This function can be called under rcu_read_lock(), given that the leaf
+ * pointers lifetimes are correctly managed.
+ */
+void *idr_find_next(struct idr *idr, int *nextidp)
+{
+ unsigned layer, id_this_layer, id = *nextidp, slot = id;
+ void **layer_p, *ret = NULL;
+
+ layer = __idr_layer_from_id(&slot);
+ id_this_layer = id - slot;
+
+ rcu_read_lock();
+
+ for (; layer < IDR_LAYERS; layer++) {
+ if (!idr->layers[layer])
+ goto next;
+
+ layer_p = rcu_dereference(idr->layers[layer]);
+
+ for (; slot < IDR_FIRST_LAYER_SIZE << layer; slot++) {
+ if (layer_p[slot]) {
+ ret = rcu_dereference(layer_p[slot]);
+ *nextidp = id_this_layer + slot;
+ goto out;
+
+ }
+ }
+next:
+ id_this_layer += IDR_FIRST_LAYER_SIZE << layer;
+ slot = 0;
+ }
+out:
+ rcu_read_unlock();
+ return ret;
+}
+EXPORT_SYMBOL(idr_find_next);
+
+/**
+ * idr_for_each - iterate through all stored pointers
+ * @idp: idr handle
+ * @fn: function to be called for each pointer
+ * @data: data passed back to callback function
+ *
+ * Iterate over the pointers registered with the given idr. The
+ * callback function will be called for each pointer currently
+ * registered, passing the id, the pointer and the data pointer passed
+ * to this function. It is not safe to modify the idr tree while in
+ * the callback, so functions such as idr_remove are not allowed.
+ *
+ * We check the return of @fn each time. If it returns anything other
+ * than %0, we break out and return that value.
+ *
+ * The caller must serialize idr_for_each() vs idr_remove().
+ */
+int idr_for_each(struct idr *idr,
+ int (*fn)(int id, void *p, void *data), void *data)
+{
+ void *p;
+ unsigned id;
+ int error = 0;
+
+ idr_for_each_entry(idr, p, id) {
+ error = fn(id, (void *)p, data);
+ if (error)
+ break;
+ }
+
+ return error;
+}
+EXPORT_SYMBOL(idr_for_each);
+
+/**
+ * idr_replace - replace pointer for given id
+ * @idp: idr handle
+ * @ptr: pointer you want associated with the id
+ * @id: lookup key
+ *
+ * Replace the pointer registered with an id and return the old value.
+ * A %-ENOENT return indicates that @id was not found.
+ * A %-EINVAL return indicates that @id was not within valid constraints.
+ *
+ * The caller must serialize with writers.
+ */
+void *idr_replace(struct idr *idr, void *ptr, unsigned id)
+{
+ void *old = ERR_PTR(-ENOENT);
+ unsigned layer;
+
+ rcu_read_lock();
+
+ layer = __idr_layer_from_id(&id);
+
+ if (layer < IDR_LAYERS && idr->layers[layer]) {
+ old = rcu_dereference(rcu_dereference(idr->layers[layer])[id]);
+ if (old)
+ rcu_assign_pointer(idr->layers[layer][id], ptr);
+ }
+
+ rcu_read_unlock();
+
+ return old;
+}
+EXPORT_SYMBOL(idr_replace);
+
+/**
+ * idr_remove - remove the given id and free its slot
+ * @idp: idr handle
+ * @id: unique key
+ */
+void idr_remove(struct idr *idr, unsigned id)
+{
+ unsigned layer, slot = id;
+
+ layer = __idr_layer_from_id(&slot);
+ BUG_ON(!idr->layers[layer]);
+
+ rcu_assign_pointer(idr->layers[layer][slot], NULL);
+ ida_remove(&idr->ida, id);
+}
+EXPORT_SYMBOL(idr_remove);
+
+/**
+ * idr_alloc_range - allocate new idr entry
+ * @idr: the (initialized) idr
+ * @ptr: pointer to be associated with the new id
+ * @start: the minimum id (inclusive)
+ * @end: the maximum id (exclusive, <= 0 for max)
+ * @gfp: memory allocation flags
+ *
+ * Allocate an id in [start, end) and associate it with @ptr. If no ID is
+ * available in the specified range, returns -ENOSPC. On memory allocation
+ * failure, returns -ENOMEM.
+ *
+ * Note that @end is treated as max when <= 0. This is to always allow
+ * using @start + N as @end as long as N is inside integer range.
+ *
+ * The user is responsible for exclusively synchronizing all operations
+ * which may modify @idr. However, read-only accesses such as idr_find()
+ * or iteration can be performed under RCU read lock provided the user
+ * destroys @ptr in RCU-safe way after removal from idr.
+ */
+int idr_alloc_range(struct idr *idr, void *ptr, unsigned start,
+ unsigned end, gfp_t gfp)
+{
+ void **layer_p;
+ unsigned layer, slot;
+ int id;
+
+ might_sleep_if(gfp & __GFP_WAIT);
+
+ id = ida_get_range(&idr->ida, start, end, gfp);
+ if (unlikely(id < 0))
+ return id;
+
+ slot = id;
+
+ layer = __idr_layer_from_id(&slot);
+ if (layer >= IDR_LAYERS) {
+ ida_remove(&idr->ida, id);
+ return -ENOSPC;
+ }
+
+ if (!idr->layers[layer]) {
+ /* allocate */
+ size_t size = (IDR_FIRST_LAYER_SIZE << layer) * sizeof(void *);
+
+ layer_p = (size < PAGE_SIZE)
+ ? kzalloc(size, gfp)
+ : (void **) __get_free_pages(gfp, get_order(size));
+ if (!layer_p) {
+ ida_remove(&idr->ida, id);
+ return -ENOMEM;
+ }
+
+ rcu_assign_pointer(idr->layers[layer], layer_p);
+ }
+
+ rcu_assign_pointer(idr->layers[layer][slot], ptr);
+ return id;
+}
+EXPORT_SYMBOL_GPL(idr_alloc_range);
+
+/**
+ * idr_destroy - release all cached layers within an idr tree
+ * @idp: idr handle
+ *
+ * Free all id mappings and all idp_layers. After this function, @idp is
+ * completely unused and can be freed / recycled. The caller is
+ * responsible for ensuring that no one else accesses @idp during or after
+ * idr_destroy().
+ *
+ * A typical clean-up sequence for objects stored in an idr tree will use
+ * idr_for_each() to free all objects, if necessay, then idr_destroy() to
+ * free up the id mappings and cached idr_layers.
+ */
+void idr_destroy(struct idr *idr)
+{
+ unsigned i, size = IDR_FIRST_LAYER_SIZE * sizeof(void *);
+
+ for (i = 0; i < IDR_LAYERS; i++) {
+ if (size < PAGE_SIZE)
+ kfree(idr->layers[i]);
+ else
+ free_pages((unsigned long) idr->layers[i],
+ get_order(size));
+
+ size *= 2;
+ }
+
+ ida_destroy(&idr->ida);
+}
+EXPORT_SYMBOL(idr_destroy);
+
+/**
+ * idr_init - initialize idr handle
+ * @idp: idr handle
+ *
+ * This function is use to set up the handle (@idp) that you will pass
+ * to the rest of the functions.
+ */
+void idr_init(struct idr *idr)
+{
+ ida_init(&idr->ida);
+}
+EXPORT_SYMBOL(idr_init);
+#endif
/**
* idr_find_next - lookup next object of id to given id.