From owner-p4-projects@FreeBSD.ORG Tue May 13 01:41:14 2003 Return-Path: Delivered-To: p4-projects@freebsd.org Received: by hub.freebsd.org (Postfix, from userid 32767) id 2F06F37B404; Tue, 13 May 2003 01:41:14 -0700 (PDT) Delivered-To: perforce@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id DA55537B401 for ; Tue, 13 May 2003 01:41:13 -0700 (PDT) Received: from repoman.freebsd.org (repoman.freebsd.org [216.136.204.115]) by mx1.FreeBSD.org (Postfix) with ESMTP id 64CA743F75 for ; Tue, 13 May 2003 01:41:13 -0700 (PDT) (envelope-from marcel@freebsd.org) Received: from repoman.freebsd.org (localhost [127.0.0.1]) by repoman.freebsd.org (8.12.6/8.12.6) with ESMTP id h4D8fD0U087346 for ; Tue, 13 May 2003 01:41:13 -0700 (PDT) (envelope-from marcel@freebsd.org) Received: (from perforce@localhost) by repoman.freebsd.org (8.12.6/8.12.6/Submit) id h4D8fCG0087343 for perforce@freebsd.org; Tue, 13 May 2003 01:41:12 -0700 (PDT) Date: Tue, 13 May 2003 01:41:12 -0700 (PDT) Message-Id: <200305130841.h4D8fCG0087343@repoman.freebsd.org> X-Authentication-Warning: repoman.freebsd.org: perforce set sender to marcel@freebsd.org using -f From: Marcel Moolenaar To: Perforce Change Reviews Subject: PERFORCE change 31058 for review X-BeenThere: p4-projects@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: p4 projects tree changes List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 13 May 2003 08:41:15 -0000 http://perforce.freebsd.org/chv.cgi?CH=31058 Change 31058 by marcel@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); }