PERFORCE change 31058 for review

[Marcel Moolenaar]

http://perforce.freebsd.org/chv.cgi?CH=31058

Change 31058 by marcel at marcel_nfs on 2003/05/13 01:40:27

	Avoid using a random number generator to generate unique RIDs.
	We don't need randomness, nor uniform distribution. The cost
	generally increases with the number of RIDs allocated due to
	picking a RID that is in use already.
	Instead we maintain an index into a bitmap to the 64-bit word
	that still has unset bits (=unallocated RIDs). We advance the
	index if all bits are set.

Affected files ...

.. //depot/projects/ia64_epc/sys/ia64/ia64/pmap.c#12 edit

Differences ...

==== //depot/projects/ia64_epc/sys/ia64/ia64/pmap.c#12 (text+ko) ====

@@ -224,8 +224,11 @@
 /*
  * Data for the RID allocator
  */
-static u_int64_t *pmap_ridbusy;
-static int pmap_ridmax, pmap_ridcount;
+static int pmap_ridcount;
+static int pmap_rididx;
+static int pmap_ridmapsz;
+static int pmap_ridmax;
+static u_int64_t *pmap_ridmap;
 struct mtx pmap_ridmutex;
 
 /*
@@ -338,12 +341,18 @@
 			printf("Processor supports %d Region ID bits\n",
 			       ridbits);
 	}
-	pmap_ridmax = (1 << ridbits);
+
+	/*
+	 * XXX: If we have enough bits in the RID to use the thread ID then
+	 * we should avoid the overhead of the map and create unique RIDs
+	 * based on the thread ID.
+	 */
+ 	pmap_ridmax = (1 << ridbits);
+	pmap_ridmapsz = pmap_ridmax / 64;
+	pmap_ridmap = (u_int64_t *)pmap_steal_memory(pmap_ridmax / 8);
+	pmap_ridmap[0] |= 0xff;
+	pmap_rididx = 0;
 	pmap_ridcount = 8;
-	pmap_ridbusy = (u_int64_t *)
-		pmap_steal_memory(pmap_ridmax / 8);
-	bzero(pmap_ridbusy, pmap_ridmax / 8);
-	pmap_ridbusy[0] |= 0xff;
 	mtx_init(&pmap_ridmutex, "RID allocator lock", NULL, MTX_DEF);
 
 	/*
@@ -638,16 +647,29 @@
 static u_int32_t
 pmap_allocate_rid(void)
 {
+	uint64_t bit, bits;
 	int rid;
 
 	mtx_lock(&pmap_ridmutex);
 	if (pmap_ridcount == pmap_ridmax)
 		panic("pmap_allocate_rid: All Region IDs used");
 
-	do {
-		rid = arc4random() & (pmap_ridmax - 1);
-	} while (pmap_ridbusy[rid / 64] & (1L << (rid & 63)));
-	pmap_ridbusy[rid / 64] |= (1L << (rid & 63));
+	/* Find an index with a free bit. */
+	while ((bits = pmap_ridmap[pmap_rididx]) == ~0UL) {
+		pmap_rididx++;
+		if (pmap_rididx == pmap_ridmapsz)
+			pmap_rididx = 0;
+	}
+	rid = pmap_rididx * 64;
+
+	/* Find a free bit. */
+	bit = 1UL;
+	while (bits & bit) {
+		rid++;
+		bit <<= 1;
+	}
+
+	pmap_ridmap[pmap_rididx] |= bit;
 	pmap_ridcount++;
 	mtx_unlock(&pmap_ridmutex);
 
@@ -657,8 +679,14 @@
 static void
 pmap_free_rid(u_int32_t rid)
 {
+	uint64_t bit;
+	int idx;
+
+	idx = rid / 64;
+	bit = ~(1UL << (rid & 63));
+
 	mtx_lock(&pmap_ridmutex);
-	pmap_ridbusy[rid / 64] &= ~(1L << (rid & 63));
+	pmap_ridmap[idx] &= bit;
 	pmap_ridcount--;
 	mtx_unlock(&pmap_ridmutex);
 }