Messages in this thread Patch in this message | | | From | David Mosberger <> | Date | Thu, 25 Mar 2004 17:45:44 -0800 | Subject | Re: Fw: potential /dev/urandom scalability improvement |
| |
>>>>> On Thu, 25 Mar 2004 16:47:27 -0600, Matt Mackall <mpm@selenic.com> said:
>> I'm addressing this patch to you because you seem to have been >> the person who most recently made some performance improvements >> to the random driver.
Matt> That was probably me, actually.
Sorry, that's what I get for trusting the BK log.
Matt> However, I've got a few pending patches that touch the same Matt> areas and do some more critical cleanup that I've been sitting Matt> on since the 2.6.0 freeze. So perhaps I should start pushing Matt> those again and we can queue this behind them. David, if you Matt> get a chance, grab the latest copy of my linux-tiny tree from
Matt> Matt> http://www.selenic.com/tiny/2.6.5-rc2-tiny1-broken-out.tar.bz2 Matt> http://www.selenic.com/tiny/2.6.5-rc2-tiny1.patch.bz2
Matt> and see how I've tweaked the pool structure and the locking Matt> and how your bits fit with it.
Not much left of the original bits!
>> +#ifdef ARCH_HAS_PREFETCH
Matt> Can we avoid adding this ifdef in some fashion? What does the Matt> compiler generate here when prefetch is a no-op? This seems to Matt> call for a prefetch_range(start, len) function/macro in any Matt> case.
Sounds reasonable, but I would prefer to do this in separate steps.
I tried your changes and performance was virtually unchanged. The patch below is updated to go on top of your patch and gives about the same performance as I reported yesterday. For now, I defined an inline prefetch_range(). If and when all architectures get updated to define this directly, we can simply remove prefetch_range() from the driver.
Thanks
--david
-- --- drivers/char/random.c 2004-03-25 17:41:54.432358997 -0800 +++ drivers/char/random.c-davidm 2004-03-25 17:34:59.040063215 -0800 @@ -421,14 +421,20 @@ **********************************************************************/ struct entropy_store { + /* mostly-read data: */ const char *name; + struct poolinfo *poolinfo; + __u32 *pool; + /* + * read-write data (colocate with lock such that when we get + * the lock, we get the other data for "free"; may cause some + * extra bus-transactions, though): + */ + spinlock_t lock ____cacheline_aligned; unsigned add_ptr; int entropy_count; int input_rotate; int reserved; - struct poolinfo *poolinfo; - spinlock_t lock; - __u32 *pool; }; static __u32 input_pool_data[INPUT_POOL_WORDS]; @@ -456,6 +462,16 @@ .pool = nonblocking_pool_data }; +static inline void +prefetch_range (void *addr, size_t len) +{ +#ifdef ARCH_HAS_PREFETCH + char *cp, *end = (char *) addr + len; + for (cp = addr; cp < end; cp += PREFETCH_STRIDE) + prefetch(cp); +#endif +} + /* * This function adds words into the entropy "pool". It does not * update the entropy estimate. The caller should call @@ -472,17 +488,30 @@ static __u32 const twist_table[8] = { 0, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 }; - unsigned i; - int new_rotate; - int wordmask = r->poolinfo->poolwords - 1; - __u32 w; - unsigned long flags; + unsigned long i, add_ptr, tap1, tap2, tap3, tap4, tap5; + int new_rotate, input_rotate; + unsigned long flags, wordmask = r->poolinfo->poolwords - 1; + __u32 w, next_w, *pool = r->pool; + + /* Taps are constant, so we can load them without holding r->lock. */ + tap1 = r->poolinfo->tap1; + tap2 = r->poolinfo->tap2; + tap3 = r->poolinfo->tap3; + tap4 = r->poolinfo->tap4; + tap5 = r->poolinfo->tap5; + next_w = *in++; spin_lock_irqsave(&r->lock, flags); + prefetch_range(pool, 4 * (wordmask + 1)); + input_rotate = r->input_rotate; + add_ptr = r->add_ptr; + while (nwords--) { - w = rol32(*in++, r->input_rotate); - i = r->add_ptr = (r->add_ptr - 1) & wordmask; + w = rol32(next_w, input_rotate); + if (nwords > 0) + next_w = *in++; + i = add_ptr = (add_ptr - 1) & wordmask; /* * Normally, we add 7 bits of rotation to the pool. @@ -490,21 +519,24 @@ * rotation, so that successive passes spread the * input bits across the pool evenly. */ - new_rotate = r->input_rotate + 14; + new_rotate = input_rotate + 14; if (i) - new_rotate = r->input_rotate + 7; - r->input_rotate = new_rotate & 31; + new_rotate = input_rotate + 7; + input_rotate = new_rotate & 31; /* XOR in the various taps */ - w ^= r->pool[(i + r->poolinfo->tap1) & wordmask]; - w ^= r->pool[(i + r->poolinfo->tap2) & wordmask]; - w ^= r->pool[(i + r->poolinfo->tap3) & wordmask]; - w ^= r->pool[(i + r->poolinfo->tap4) & wordmask]; - w ^= r->pool[(i + r->poolinfo->tap5) & wordmask]; - w ^= r->pool[i]; - r->pool[i] = (w >> 3) ^ twist_table[w & 7]; + w ^= pool[(i + tap1) & wordmask]; + w ^= pool[(i + tap2) & wordmask]; + w ^= pool[(i + tap3) & wordmask]; + w ^= pool[(i + tap4) & wordmask]; + w ^= pool[(i + tap5) & wordmask]; + w ^= pool[i]; + pool[i] = (w >> 3) ^ twist_table[w & 7]; } + r->input_rotate = input_rotate; + r->add_ptr = add_ptr; + spin_unlock_irqrestore(&r->lock, flags); } - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |