WebSVN – Kolibri OS – Diff – /drivers/ddk/linux/idr.c

+ *
  * You call it to allocate an id (an int) an associate with that id a
  * pointer or what ever, we treat it as a (void *).  You can pass this
  * id to a user for him to pass back at a later time.  You then pass
  * that id to this code and it returns your pointer.
- * You can release ids at any time. When all ids are released, most of
- * the memory is returned (we keep MAX_IDR_FREE) in a local pool so we
- * don't need to go to the memory "store" during an id allocate, just
- * so you don't need to be too concerned about locking and conflicts
- * with the slab allocator.
  */
 #include
 #include
     kfree(layer);
+}
 static inline void free_layer(struct idr *idr, struct idr_layer *p)
 {
-	if (idr->hint && idr->hint == p)
+	if (idr->hint == p)
 		RCU_INIT_POINTER(idr->hint, NULL);
     idr_layer_rcu_free(&p->rcu_head);
+}
 		id = id >> IDR_BITS;
 		__set_bit((id & IDR_MASK), p->bitmap);
+	}
+}
-int __idr_pre_get(struct idr *idp, gfp_t gfp_mask)
+static int __idr_pre_get(struct idr *idp, gfp_t gfp_mask)
+{
 	while (idp->id_free_cnt < MAX_IDR_FREE) {
        struct idr_layer *new;
        new = kzalloc(sizeof(struct idr_layer), gfp_mask);
        if (new == NULL)
            return (0);
        move_to_free_list(idp, new);
+   }
    return 1;
-}
 EXPORT_SYMBOL(__idr_pre_get);
 /**
  * sub_alloc - try to allocate an id without growing the tree depth
 			l++;
 			oid = id;
 			id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
 			/* if already at the top layer, we need to grow */
-			if (id >= 1 << (idp->layers * IDR_BITS)) {
+			if (id > idr_max(idp->layers)) {
 				*starting_id = id;
 				return -EAGAIN;
+			}
 			p = pa[l];
 	rcu_assign_pointer(pa[0]->ary[id & IDR_MASK], (struct idr_layer *)ptr);
 		pa[0]->count++;
 		idr_mark_full(pa, id);
+}
-int __idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)
-{
-	struct idr_layer *pa[MAX_IDR_LEVEL + 1];
-	int rv;
-	rv = idr_get_empty_slot(idp, starting_id, pa, 0, idp);
-	if (rv < 0)
-		return rv == -ENOMEM ? -EAGAIN : rv;
-	idr_fill_slot(idp, ptr, rv, pa);
-	*id = rv;
-    return 0;
-}
 EXPORT_SYMBOL(__idr_get_new_above);
 /**
  * idr_preload - preload for idr_alloc()
 	struct idr_layer *to_free;
 	if (id < 0)
+		return;
+	if (id > idr_max(idp->layers)) {
+		idr_remove_warning(id);
+		return;
 		return;
 	sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
 	if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
 	    idp->top->ary[0]) {
 		--idp->layers;
 		to_free->count = 0;
 		bitmap_clear(to_free->bitmap, 0, IDR_SIZE);
 		free_layer(idp, to_free);
+	}
-	while (idp->id_free_cnt >= MAX_IDR_FREE) {
-		p = get_from_free_list(idp);
-		/*
-		 * Note: we don't call the rcu callback here, since the only
-		 * layers that fall into the freelist are those that have been
-		 * preallocated.
-		 */
-        kfree(p);
-	}
-	return;
+}
 EXPORT_SYMBOL(idr_remove);
-void __idr_remove_all(struct idr *idp)
+static void __idr_remove_all(struct idr *idp)
+{
 	int n, id, max;
 	int bt_mask;
 	struct idr_layer *p;
 	struct idr_layer *pa[MAX_IDR_LEVEL + 1];
 	struct idr_layer **paa = &pa[0];
 	n = idp->layers * IDR_BITS;
-	p = idp->top;
+	*paa = idp->top;
 	rcu_assign_pointer(idp->top, NULL);
 	max = idr_max(idp->layers);
 	id = 0;
-	id = 0;
+	while (id >= 0 && id <= max) {
-	while (id >= 0 && id <= max) {
-		while (n > IDR_BITS && p) {
+		p = *paa;
+		while (n > IDR_BITS && p) {
 			n -= IDR_BITS;
-			*paa++ = p;
+			p = p->ary[(id >> n) & IDR_MASK];
-			p = p->ary[(id >> n) & IDR_MASK];
+			*++paa = p;
+		}
 		bt_mask = id;
 		id += 1 << n;
 		/* Get the highest bit that the above add changed from 0->1. */
 		while (n < fls(id ^ bt_mask)) {
-			if (p)
+			if (*paa)
-				free_layer(idp, p);
+				free_layer(idp, *paa);
 			n += IDR_BITS;
-			p = *--paa;
+			--paa;
-		}
+		}
 	idp->layers = 0;
 	idp->layers = 0;
 EXPORT_SYMBOL(__idr_remove_all);
 	struct idr_layer *p;
 	struct idr_layer *pa[MAX_IDR_LEVEL + 1];
 	struct idr_layer **paa = &pa[0];
 	n = idp->layers * IDR_BITS;
-	p = rcu_dereference_raw(idp->top);
+	*paa = rcu_dereference_raw(idp->top);
 	max = idr_max(idp->layers);
+	id = 0;
-	id = 0;
+	while (id >= 0 && id <= max) {
-	while (id >= 0 && id <= max) {
+		p = *paa;
-		while (n > 0 && p) {
-			n -= IDR_BITS;
+		while (n > 0 && p) {
+			n -= IDR_BITS;
-			*paa++ = p;
+			p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
-			p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
+			*++paa = p;
+		}
+		}
 		id += 1 << n;
 		while (n < fls(id)) {
 			n += IDR_BITS;
-			p = *--paa;
+			--paa;
+		}
+	}
 	struct idr_layer **paa = &pa[0];
 	int id = *nextidp;
 	int n, max;
 	/* find first ent */
-	p = rcu_dereference_raw(idp->top);
+	p = *paa = rcu_dereference_raw(idp->top);
 	if (!p)
 		return NULL;
 	n = (p->layer + 1) * IDR_BITS;
 	max = idr_max(p->layer + 1);
 	while (id >= 0 && id <= max) {
-	while (id >= 0 && id <= max) {
+		p = *paa;
-		while (n > 0 && p) {
-			n -= IDR_BITS;
+		while (n > 0 && p) {
+			n -= IDR_BITS;
-			*paa++ = p;
+			p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
-			p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
+			*++paa = p;
+		}
 		 * beginning of the next layer using round_up().
 		 */
 		id = round_up(id + 1, 1 << n);
 		while (n < fls(id)) {
 			n += IDR_BITS;
-			p = *--paa;
+			--paa;
+		}
+	}
 	return NULL;
+}
 EXPORT_SYMBOL(idr_get_next);
 	if (id < 0)
 		return ERR_PTR(-EINVAL);
 	p = idp->top;
 	if (!p)
-		return ERR_PTR(-EINVAL);
-	n = (p->layer+1) * IDR_BITS;
+		return ERR_PTR(-ENOENT);
-	if (id >= (1 << n))
+	if (id > idr_max(p->layer + 1))
-		return ERR_PTR(-EINVAL);
+		return ERR_PTR(-ENOENT);
-	n -= IDR_BITS;
+	n = p->layer * IDR_BITS;
 	while ((n > 0) && p) {
 	memset(idp, 0, sizeof(struct idr));
 	spin_lock_init(&idp->lock);
+}
 EXPORT_SYMBOL(idr_init);
+static int idr_has_entry(int id, void *p, void *data)
+{
+	return 1;
+}
+bool idr_is_empty(struct idr *idp)
+{
+	return !idr_for_each(idp, idr_has_entry, NULL);
+}
 EXPORT_SYMBOL(idr_is_empty);
 /**
  * DOC: IDA description
 	int idr_id = id / IDA_BITMAP_BITS;
 	int offset = id % IDA_BITMAP_BITS;
 	int n;
 	struct ida_bitmap *bitmap;
+	if (idr_id > idr_max(ida->idr.layers))
+		goto err;
 	/* clear full bits while looking up the leaf idr_layer */
 	while ((shift > 0) && p) {
 		n = (idr_id >> shift) & IDR_MASK;
 		__clear_bit(n, p->bitmap);
 	n = idr_id & IDR_MASK;
 	__clear_bit(n, p->bitmap);
 	bitmap = (void *)p->ary[n];
-	if (!test_bit(offset, bitmap->bitmap))
+	if (!bitmap || !test_bit(offset, bitmap->bitmap))
 		goto err;
         res = (res + (res >> 4)) & 0x0F0F0F0F;
         res = res + (res >> 8);
         return (res + (res >> 16)) & 0x000000FF;
+}
+unsigned long hweight64(__u64 w)
+{
+#if BITS_PER_LONG == 32
+        return hweight32((unsigned int)(w >> 32)) + hweight32((unsigned int)w);
+#elif BITS_PER_LONG == 64
+        __u64 res = w - ((w >> 1) & 0x5555555555555555ul);
+        res = (res & 0x3333333333333333ul) + ((res >> 2) & 0x3333333333333333ul);
+        res = (res + (res >> 4)) & 0x0F0F0F0F0F0F0F0Ful;
+        res = res + (res >> 8);
+        res = res + (res >> 16);
+        return (res + (res >> 32)) & 0x00000000000000FFul;
+#endif
+}

Subversion Repositories Kolibri OS

(root)/drivers/ddk/linux/idr.c – Rev 4103 → 5056