From owner-svn-src-all@FreeBSD.ORG Thu Dec 10 02:51:41 2009 Return-Path: Delivered-To: svn-src-all@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 59213106566C; Thu, 10 Dec 2009 02:51:41 +0000 (UTC) (envelope-from jasone@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id 47EC88FC15; Thu, 10 Dec 2009 02:51:41 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.3/8.14.3) with ESMTP id nBA2pfWM048410; Thu, 10 Dec 2009 02:51:41 GMT (envelope-from jasone@svn.freebsd.org) Received: (from jasone@localhost) by svn.freebsd.org (8.14.3/8.14.3/Submit) id nBA2pfr9048408; Thu, 10 Dec 2009 02:51:41 GMT (envelope-from jasone@svn.freebsd.org) Message-Id: <200912100251.nBA2pfr9048408@svn.freebsd.org> From: Jason Evans Date: Thu, 10 Dec 2009 02:51:41 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r200345 - head/lib/libc/stdlib X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 10 Dec 2009 02:51:41 -0000 Author: jasone Date: Thu Dec 10 02:51:40 2009 New Revision: 200345 URL: http://svn.freebsd.org/changeset/base/200345 Log: Simplify arena_run_reg_dalloc(), and remove a bug that was due to incorrect initialization of ssize_invs. Modified: head/lib/libc/stdlib/malloc.c Modified: head/lib/libc/stdlib/malloc.c ============================================================================== --- head/lib/libc/stdlib/malloc.c Thu Dec 10 01:45:06 2009 (r200344) +++ head/lib/libc/stdlib/malloc.c Thu Dec 10 02:51:40 2009 (r200345) @@ -2419,7 +2419,7 @@ arena_run_reg_alloc(arena_run_t *run, ar static inline void arena_run_reg_dalloc(arena_run_t *run, arena_bin_t *bin, void *ptr, size_t size) { - unsigned diff, regind, elm, bit; + unsigned shift, diff, regind, elm, bit; assert(run->magic == ARENA_RUN_MAGIC); @@ -2428,31 +2428,16 @@ arena_run_reg_dalloc(arena_run_t *run, a * actual division here can reduce allocator throughput by over 20%! */ diff = (unsigned)((uintptr_t)ptr - (uintptr_t)run - bin->reg0_offset); - if ((size & (size - 1)) == 0) { - /* - * log2_table allows fast division of a power of two in the - * [1..128] range. - * - * (x / divisor) becomes (x >> log2_table[divisor - 1]). - */ - static const unsigned char log2_table[] = { - 0, 1, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7 - }; - if (size <= 128) - regind = (diff >> log2_table[size - 1]); - else if (size <= 32768) - regind = diff >> (8 + log2_table[(size >> 8) - 1]); - else - regind = diff / size; - } else if (size < qspace_max) { + /* Rescale (factor powers of 2 out of the numerator and denominator). */ + shift = ffs(size) - 1; + diff >>= shift; + size >>= shift; + + if (size == 1) { + /* The divisor was a power of 2. */ + regind = diff; + } else { /* * To divide by a number D that is not a power of two we * multiply by (2^21 / D) and then right shift by 21 positions. @@ -2461,78 +2446,32 @@ arena_run_reg_dalloc(arena_run_t *run, a * * becomes * - * (X * qsize_invs[(D >> QUANTUM_2POW) - 3]) - * >> SIZE_INV_SHIFT + * (X * size_invs[D - 3]) >> SIZE_INV_SHIFT * * We can omit the first three elements, because we never - * divide by 0, and QUANTUM and 2*QUANTUM are both powers of - * two, which are handled above. + * divide by 0, and 1 and 2 are both powers of two, which are + * handled above. */ #define SIZE_INV_SHIFT 21 -#define QSIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s << QUANTUM_2POW)) + 1) - static const unsigned qsize_invs[] = { - QSIZE_INV(3), - QSIZE_INV(4), QSIZE_INV(5), QSIZE_INV(6), QSIZE_INV(7) -#if (QUANTUM_2POW < 4) - , - QSIZE_INV(8), QSIZE_INV(9), QSIZE_INV(10), QSIZE_INV(11), - QSIZE_INV(12),QSIZE_INV(13), QSIZE_INV(14), QSIZE_INV(15) -#endif - }; - assert(QUANTUM * (((sizeof(qsize_invs)) / sizeof(unsigned)) + 3) - >= (1U << QSPACE_MAX_2POW_DEFAULT)); - - if (size <= (((sizeof(qsize_invs) / sizeof(unsigned)) + 2) << - QUANTUM_2POW)) { - regind = qsize_invs[(size >> QUANTUM_2POW) - 3] * diff; - regind >>= SIZE_INV_SHIFT; - } else - regind = diff / size; -#undef QSIZE_INV - } else if (size < cspace_max) { -#define CSIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s << CACHELINE_2POW)) + 1) - static const unsigned csize_invs[] = { - CSIZE_INV(3), - CSIZE_INV(4), CSIZE_INV(5), CSIZE_INV(6), CSIZE_INV(7) +#define SIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s)) + 1) + static const unsigned size_invs[] = { + SIZE_INV(3), + SIZE_INV(4), SIZE_INV(5), SIZE_INV(6), SIZE_INV(7), + SIZE_INV(8), SIZE_INV(9), SIZE_INV(10), SIZE_INV(11), + SIZE_INV(12), SIZE_INV(13), SIZE_INV(14), SIZE_INV(15), + SIZE_INV(16), SIZE_INV(17), SIZE_INV(18), SIZE_INV(19), + SIZE_INV(20), SIZE_INV(21), SIZE_INV(22), SIZE_INV(23), + SIZE_INV(24), SIZE_INV(25), SIZE_INV(26), SIZE_INV(27), + SIZE_INV(28), SIZE_INV(29), SIZE_INV(30), SIZE_INV(31) }; - assert(CACHELINE * (((sizeof(csize_invs)) / sizeof(unsigned)) + - 3) >= (1U << CSPACE_MAX_2POW_DEFAULT)); - if (size <= (((sizeof(csize_invs) / sizeof(unsigned)) + 2) << - CACHELINE_2POW)) { - regind = csize_invs[(size >> CACHELINE_2POW) - 3] * - diff; - regind >>= SIZE_INV_SHIFT; - } else - regind = diff / size; -#undef CSIZE_INV - } else { -#define SSIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s << SUBPAGE_2POW)) + 1) - static const unsigned ssize_invs[] = { - SSIZE_INV(3), - SSIZE_INV(4), SSIZE_INV(5), SSIZE_INV(6), SSIZE_INV(7), - SSIZE_INV(8), SSIZE_INV(9), SSIZE_INV(10), SSIZE_INV(11), - SSIZE_INV(12), SSIZE_INV(13), SSIZE_INV(14), SSIZE_INV(15) -#if (PAGE_SHIFT == 13) - , - SSIZE_INV(16), SSIZE_INV(17), SSIZE_INV(18), SSIZE_INV(19), - SSIZE_INV(20), SSIZE_INV(21), SSIZE_INV(22), SSIZE_INV(23), - SSIZE_INV(24), SSIZE_INV(25), SSIZE_INV(26), SSIZE_INV(27), - SSIZE_INV(28), SSIZE_INV(29), SSIZE_INV(29), SSIZE_INV(30) -#endif - }; - assert(SUBPAGE * (((sizeof(ssize_invs)) / sizeof(unsigned)) + 3) - >= PAGE_SIZE); - - if (size < (((sizeof(ssize_invs) / sizeof(unsigned)) + 2) << - SUBPAGE_2POW)) { - regind = ssize_invs[(size >> SUBPAGE_2POW) - 3] * diff; - regind >>= SIZE_INV_SHIFT; - } else + if (size <= ((sizeof(size_invs) / sizeof(unsigned)) + 2)) + regind = (diff * size_invs[size - 3]) >> SIZE_INV_SHIFT; + else regind = diff / size; -#undef SSIZE_INV - } +#undef SIZE_INV #undef SIZE_INV_SHIFT + } assert(diff == regind * size); assert(regind < bin->nregs);