Re: [PATCH 05/10] Introduce ridr_get_new_above()

[Nadia Derbey <Nadia.Derbey@bull.net>]

Tim Pepper wrote:
> On Tue 29 Apr at 16:33:09 +0200 Nadia.Derbey@bull.net said:
> 
>>[PATCH 05/10]
>>
>>This patch introduces the ridr_get_new_above() routine, and some common code
>>between the idr an ridr API's.
> 
> 
> The ridr_get_new_above() is the first place we see something really
> different compared to idr (an RCU addition).  This is a lot of patching
> so far for what would be a small incremental change otherwise.
> 
> 
>>Index: linux-2.6.25-mm1/include/linux/idr.h
>>===================================================================
>>--- linux-2.6.25-mm1.orig/include/linux/idr.h	2008-04-29 13:08:00.000000000 +0200
>>+++ linux-2.6.25-mm1/include/linux/idr.h	2008-04-29 14:08:47.000000000 +0200
>>@@ -71,6 +71,27 @@ struct idr {
>> }
>> #define DEFINE_IDR(name)	struct idr name = IDR_INIT(name)
>>
>>+/* Actions to be taken after a call to _idr_sub_alloc */
>>+#define IDR_DONE         -1
>>+#define IDR_NEED_TO_GROW -2
>>+#define IDR_NOMORE_SPACE -3
>>+#define IDR_GO_TOP       -4
>>+#define IDR_GO_UP        -5
> 
> 
> This stuff is useful on its own in as much as it improves code
> readability.  A lot of this patch (the "some common code between the
> idr and ridr API's" part) could be a standalone patch distinct from the
> ridr series and then be at the head of your stack.
> 
> 
>>+			return action;
>>+		case IDR_DONE:
>>+			goto end_loop;
>>+		case IDR_GO_UP:
>>+			continue;
>>+		case IDR_GO_TOP:
>>+			goto restart;
>>+		default:
>>+			m = action;
>> 			break;
>>+		}
>>+		BUG_ON(m < 0);
> 
> 
> Why the added BUG_ON()?  These couple hunks are a bit muddled, so maybe I
> missed something.  But I don't see anything different in how m or bm are
> being manipulated such that m<0 is anymore likely after this patch.
> 
> 
>>Index: linux-2.6.25-mm1/lib/ridr.c
>>===================================================================
>>--- linux-2.6.25-mm1.orig/lib/ridr.c	2008-04-29 13:23:17.000000000 +0200
>>+++ linux-2.6.25-mm1/lib/ridr.c	2008-04-29 14:03:35.000000000 +0200
>>@@ -11,6 +11,23 @@
>> static struct kmem_cache *ridr_layer_cache;
>>
>>
>>+static struct ridr_layer *get_from_free_list(struct ridr *idp)
>>+{
>>+	struct ridr_layer *q;
>>+	struct idr_layer *p;
>>+	unsigned long flags;
>>+
>>+	spin_lock_irqsave(&idp->lock, flags);
>>+	if ((q = idp->id_free)) {
>>+		p = ridr_to_idr(q);
>>+		idp->id_free = p->ary[0];
>>+		idp->id_free_cnt--;
>>+		p->ary[0] = NULL;
>>+	}
>>+	spin_unlock_irqrestore(&idp->lock, flags);
>>+	return(q);
>>+}
>>+
> 
> 
> idr's alloc_layer() in disguise?
> 
> 
>>+static int sub_alloc(struct ridr *idp, int *starting_id,
>>+			struct ridr_layer **rpa, struct idr_layer **pa)
> 
> 
> ...
> More or less duplication
> ...
> 
> 
>>+		 * Create the layer below if it is missing.
>>+		 */
>>+		if (!p->ary[m]) {
>>+			new = get_from_free_list(idp);
>>+			if (!new)
>>+				return -1;
>>+			rcu_assign_pointer(p->ary[m], new);
>>+			p->count++;
>>+		}
>>+		pa[l] = p;
>>+		rpa[l--] = idr_to_ridr(p);
>>+		p = p->ary[m];
>>+	}
>>+
>>+end_loop:
>>+	pa[l] = p;
>>+	rpa[l] = idr_to_ridr(p);
>>+	return id;
>>+}
> 
> 
> Oh but wait..there's some RCU-ness tucked in there.
> 
> 
>>+
>>+static int ridr_get_empty_slot(struct ridr *idp, int starting_id,
>>+			      struct ridr_layer **rpa, struct idr_layer **pa)
>>+{
>>+	struct ridr_layer *p, *rnew;
>>+	int layers, v, id;
>>+	unsigned long flags;
>>+
>>+	id = starting_id;
>>+build_up:
>>+	p = idp->top;
>>+	layers = idp->layers;
>>+	if (unlikely(!p)) {
>>+		p = get_from_free_list(idp);
>>+		if (!p)
>>+			return -1;
>>+		layers = 1;
>>+	}
>>+	/*
>>+	 * Add a new layer to the top of the tree if the requested
>>+	 * id is larger than the currently allocated space.
>>+	 */
>>+	while (layers < MAX_LEVEL - 1 && id >= (1 << (layers * IDR_BITS))) {
> 
>                ^^                   ^^
> Dropped some parens.  Otherwise more duplication...
> 
> 
>>+				rnew->idr.ary[0] = NULL;
>>+				rnew->idr.bitmap = rnew->idr.count = 0;
>>+				__move_to_free_list(idp, rnew);
>>+			}
>>+			spin_unlock_irqrestore(&idp->lock, flags);
>>+			return -1;
>>+		}
>>+		_idr_set_new_slot(ridr_to_idr(rnew), ridr_to_idr(p));
>>+		p = rnew;
>>+	}
>>+	rcu_assign_pointer(idp->top, p);
>>+	idp->layers = layers;
>>+	v = sub_alloc(idp, &id, rpa, pa);
>>+	if (v == IDR_NEED_TO_GROW)
>>+		goto build_up;
>>+	return(v);
>>+}
> 
> 
> Some more RCU.
> 
> 
>>+static int ridr_get_new_above_int(struct ridr *idp, void *ptr, int starting_id)
>>+{
>>+	struct ridr_layer *rpa[MAX_LEVEL];
>>+	struct idr_layer *pa[MAX_LEVEL];
>>+	int id;
>>+
>>+	id = ridr_get_empty_slot(idp, starting_id, rpa, pa);
>>+	if (id >= 0) {
>>+		/*
>>+		 * Successfully found an empty slot.  Install the user
>>+		 * pointer and mark the slot full.
>>+		 */
>>+		rcu_assign_pointer(pa[0]->ary[id & IDR_MASK],
>>+				(struct ridr_layer *)ptr);
>>+		pa[0]->count++;
>>+		_idr_mark_full(pa, id);
>>+	}
>>+
>>+	return id;
>>+}
> 
> 
> And other line of RCU.
> 
> OK.  So at this point in patch 5/10 we've got 3 lines of new code and
> hundreds of lines of duplicated code?
> 
> A while more looking through the rest of the patches for the rest of the
> context and I might be able to actually think about the implications of
> these three lines being where they are.
> 
> Locking changes are complicated enough without all this obfuscation!
> I understand the desire to not break IDR, but...
> 

OK, you convinced me. I'll re-send a new patchset that is incremental on 
top of idr. Sorry (and thanks a lot) for the painful review!

Regards,
Nadia