2 files changed, 179 insertions, 2 deletions

diff --git a/sys/compat/linuxkpi/common/include/linux/idr.h b/sys/compat/linuxkpi/common/include/linux/idr.h
index d13aeaf..234fcb6 100644
--- a/sys/compat/linuxkpi/common/include/linux/idr.h
+++ b/sys/compat/linuxkpi/common/include/linux/idr.h
@@ -63,15 +63,23 @@ struct idr {
 	int			next_cyclic_id;
 };
 
-#define DEFINE_IDR(name)						\
+/* NOTE: It is the applications responsibility to destroy the IDR */
+#define	DEFINE_IDR(name)						\
 	struct idr name;						\
 	SYSINIT(name##_idr_sysinit, SI_SUB_DRIVERS, SI_ORDER_FIRST,	\
-	    idr_init, &(name));
+	    idr_init, &(name))
+
+/* NOTE: It is the applications responsibility to destroy the IDA */
+#define	DEFINE_IDA(name)						\
+	struct ida name;						\
+	SYSINIT(name##_ida_sysinit, SI_SUB_DRIVERS, SI_ORDER_FIRST,	\
+	    ida_init, &(name))
 
 #define	idr_preload(x) do { } while (0)
 #define	idr_preload_end() do { } while (0)
 
 void	*idr_find(struct idr *idp, int id);
+void	*idr_get_next(struct idr *idp, int *nextid);
 int	idr_pre_get(struct idr *idp, gfp_t gfp_mask);
 int	idr_get_new(struct idr *idp, void *ptr, int *id);
 int	idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id);
@@ -82,5 +90,39 @@ void	idr_destroy(struct idr *idp);
 void	idr_init(struct idr *idp);
 int	idr_alloc(struct idr *idp, void *ptr, int start, int end, gfp_t);
 int	idr_alloc_cyclic(struct idr *idp, void *ptr, int start, int end, gfp_t);
+int	idr_for_each(struct idr *idp, int (*fn)(int id, void *p, void *data), void *data);
+
+#define	idr_for_each_entry(idp, entry, id)	\
+	for ((id) = 0; ((entry) = idr_get_next(idp, &(id))) != NULL; ++(id))
+
+#define	IDA_CHUNK_SIZE		128	/* 128 bytes per chunk */
+#define	IDA_BITMAP_LONGS	(IDA_CHUNK_SIZE / sizeof(long) - 1)
+#define	IDA_BITMAP_BITS 	(IDA_BITMAP_LONGS * sizeof(long) * 8)
+
+struct ida_bitmap {
+	long			nr_busy;
+	unsigned long		bitmap[IDA_BITMAP_LONGS];
+};
+
+struct ida {
+	struct idr		idr;
+	struct ida_bitmap	*free_bitmap;
+};
+
+int	ida_pre_get(struct ida *ida, gfp_t gfp_mask);
+int	ida_get_new_above(struct ida *ida, int starting_id, int *p_id);
+void	ida_remove(struct ida *ida, int id);
+void	ida_destroy(struct ida *ida);
+void	ida_init(struct ida *ida);
+
+int	ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
+    gfp_t gfp_mask);
+void	ida_simple_remove(struct ida *ida, unsigned int id);
+
+static inline int
+ida_get_new(struct ida *ida, int *p_id)
+{
+	return (ida_get_new_above(ida, 0, p_id));
+}
 
 #endif	/* _LINUX_IDR_H_ */
diff --git a/sys/compat/linuxkpi/common/src/linux_idr.c b/sys/compat/linuxkpi/common/src/linux_idr.c
index 0440c78..92e3815 100644
--- a/sys/compat/linuxkpi/common/src/linux_idr.c
+++ b/sys/compat/linuxkpi/common/src/linux_idr.c
@@ -227,6 +227,24 @@ idr_find(struct idr *idr, int id)
 	return (res);
 }
 
+void *
+idr_get_next(struct idr *idr, int *nextidp)
+{
+	void *res = NULL;
+	int id = *nextidp;
+
+	mtx_lock(&idr->lock);
+	for (; id <= idr_max(idr); id++) {
+		res = idr_find_locked(idr, id);
+		if (res == NULL)
+			continue;
+		*nextidp = id;
+		break;
+	}
+	mtx_unlock(&idr->lock);
+	return (res);
+}
+
 int
 idr_pre_get(struct idr *idr, gfp_t gfp_mask)
 {
@@ -487,6 +505,12 @@ idr_get_new_above(struct idr *idr, void *ptr, int starting_id, int *idp)
 	return (retval);
 }
 
+int
+ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
+{
+	return (idr_get_new_above(&ida->idr, NULL, starting_id, p_id));
+}
+
 static int
 idr_alloc_locked(struct idr *idr, void *ptr, int start, int end)
 {
@@ -540,3 +564,114 @@ idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
 	mtx_unlock(&idr->lock);
 	return (retval);
 }
+
+static int
+idr_for_each_layer(struct idr_layer *il, int layer,
+    int (*f)(int id, void *p, void *data), void *data)
+{
+	int i, err;
+
+	if (il == NULL)
+		return (0);
+	if (layer == 0) {
+		for (i = 0; i < IDR_SIZE; i++) {
+			if (il->ary[i] == NULL)
+				continue;
+			err = f(i, il->ary[i],  data);
+			if (err)
+				return (err);
+		}
+		return (0);
+	}
+	for (i = 0; i < IDR_SIZE; i++) {
+		if (il->ary[i] == NULL)
+			continue;
+		err = idr_for_each_layer(il->ary[i], layer - 1, f, data);
+		if (err)
+			return (err);
+	}
+	return (0);
+}
+
+int
+idr_for_each(struct idr *idp, int (*f)(int id, void *p, void *data), void *data)
+{
+	int err;
+
+	mtx_lock(&idp->lock);
+	err = idr_for_each_layer(idp->top, idp->layers - 1, f, data);
+	mtx_unlock(&idp->lock);
+	return (err);
+}
+
+int
+ida_pre_get(struct ida *ida, gfp_t flags)
+{
+	if (idr_pre_get(&ida->idr, flags) == 0)
+		return (0);
+
+	if (ida->free_bitmap == NULL) {
+		ida->free_bitmap =
+		    malloc(sizeof(struct ida_bitmap), M_IDR, flags);
+	}
+	return (ida->free_bitmap != NULL);
+}
+
+int
+ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
+    gfp_t flags)
+{
+	int ret, id;
+	unsigned int max;
+
+	MPASS((int)start >= 0);
+	MPASS((int)end >= 0);
+
+	if (end == 0)
+		max = 0x80000000;
+	else {
+		MPASS(end > start);
+		max = end - 1;
+	}
+again:
+	if (!ida_pre_get(ida, flags))
+		return (-ENOMEM);
+
+	if ((ret = ida_get_new_above(ida, start, &id)) == 0) {
+		if (id > max) {
+			ida_remove(ida, id);
+			ret = -ENOSPC;
+		} else {
+			ret = id;
+		}
+	}
+	if (__predict_false(ret == -EAGAIN))
+		goto again;
+
+	return (ret);
+}
+
+void
+ida_simple_remove(struct ida *ida, unsigned int id)
+{
+	idr_remove(&ida->idr, id);
+}
+
+void
+ida_remove(struct ida *ida, int id)
+{	
+	idr_remove(&ida->idr, id);
+}
+
+void
+ida_init(struct ida *ida)
+{
+	idr_init(&ida->idr);
+}
+
+void
+ida_destroy(struct ida *ida)
+{
+	idr_destroy(&ida->idr);
+	free(ida->free_bitmap, M_IDR);
+}