Skip to contentSkip to conversation

potential /dev/urandom scalability improvement

DISCUSSION Matt Mackall 5 participants 20 messages Mar 25, 2004 – Mar 27, 2004 1 message not in the archive Random number driver

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw
Quoted 12 lines · Andrew Morton

Matt, could you please review David's changes?

Begin forwarded message:

Date: Wed, 24 Mar 2004 22:06:57 -0800
From: David Mosberger <[email protected]>
To: [email protected]
Cc: [email protected], [email protected]
Subject: potential /dev/urandom scalability improvement

Quoted 5 lines

Hi Andrew,

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.

That was probably me, actually.

Quoted 2 lines

Oh, and somebody who actually understands this code may want to double-check the patch for correctness.

Seems perfectly sane.

However, I've got a few pending patches that touch the same areas and do some more critical cleanup that I've been sitting on since the 2.6.0 freeze. So perhaps I should start pushing those again and we can queue this behind them. David, if you get a chance, grab the latest copy of my linux-tiny tree from

http://www.selenic.com/tiny/2.6.5-rc2-tiny1-broken-out.tar.bz2
http://www.selenic.com/tiny/2.6.5-rc2-tiny1.patch.bz2

and see how I've tweaked the pool structure and the locking and how your bits fit with it.

Review

Quoted 4 lines
(quoted diff) +4 -0
+#ifdef ARCH_HAS_PREFETCH
+	for (cp = (char *) r->pool; cp <= (char *) (r->pool + wordmask); cp += PREFETCH_STRIDE)
+		prefetch(cp);
+#endif

Can we avoid adding this ifdef in some fashion? What does the compiler generate here when prefetch is a no-op? This seems to call for a prefetch_range(start, len) function/macro in any case.

Signature · 1 line
Matt Mackall : http://www.selenic.com : Linux development and consulting
#2 lore raw
Quoted 5 lines
Quoted 5 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line · Matt Mackall

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!

Quoted 1 line
Quoted 1 line

+#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

--

char/random.c-davidm renamed from char/random.c +52 -20
@@ -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);
 }
 
#3 lore raw
Quoted 7 lines · David Mosberger

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.

We may as well stick prefetch_range() in prefetch.h.

And Matt's patch series is not a thing I want to take on board at present, so let's stick with the straight scalability patch for now.

I moved the prefetch_range() call to outside the spinlock. Does that make sense?

 25-akpm/drivers/char/random.c    |   51 ++++++++++++++++++++++++++-------------
 25-akpm/include/linux/prefetch.h |   11 ++++++++
 2 files changed, 46 insertions(+), 16 deletions(-)
drivers/char/random.c renamed from drivers/char/random.c~urandom-scalability-fix +35 -16
diff -puN drivers/char/random.c~urandom-scalability-fix drivers/char/random.c
@@ -490,12 +490,15 @@ static inline __u32 int_ln_12bits(__u32 
  **********************************************************************/
 
 struct entropy_store {
+	/* mostly-read data: */
+	struct poolinfo poolinfo;
+	__u32		*pool;
+
+	/* read-write data: */
+	spinlock_t lock ____cacheline_aligned;
 	unsigned	add_ptr;
 	int		entropy_count;
 	int		input_rotate;
-	struct poolinfo poolinfo;
-	__u32		*pool;
-	spinlock_t lock;
 };
 
 /*
@@ -571,38 +574,54 @@ static void add_entropy_words(struct ent
 	static __u32 const twist_table[8] = {
 		         0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
 		0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
-	unsigned i;
-	int new_rotate;
+	unsigned long i, add_ptr, tap1, tap2, tap3, tap4, tap5;
+	int new_rotate, input_rotate;
 	int wordmask = r->poolinfo.poolwords - 1;
-	__u32 w;
+	__u32 w, next_w;
 	unsigned long flags;
 
+	/* 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++;
+
+	prefetch_range(r->pool, wordmask);
 	spin_lock_irqsave(&r->lock, flags);
+	input_rotate = r->input_rotate;
+	add_ptr = r->add_ptr;
 
 	while (nwords--) {
-		w = rotate_left(r->input_rotate, *in++);
-		i = r->add_ptr = (r->add_ptr - 1) & wordmask;
+		w = rotate_left(input_rotate, next_w);
+		if (nwords > 0)
+			next_w = *in++;
+		i = add_ptr = (add_ptr - 1) & wordmask;
 		/*
 		 * Normally, we add 7 bits of rotation to the pool.
 		 * At the beginning of the pool, add an extra 7 bits
 		 * 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 + tap1) & wordmask];
+		w ^= r->pool[(i + tap2) & wordmask];
+		w ^= r->pool[(i + tap3) & wordmask];
+		w ^= r->pool[(i + tap4) & wordmask];
+		w ^= r->pool[(i + tap5) & wordmask];
 		w ^= r->pool[i];
 		r->pool[i] = (w >> 3) ^ twist_table[w & 7];
 	}
 
+	r->input_rotate = input_rotate;
+	r->add_ptr = add_ptr;
+
 	spin_unlock_irqrestore(&r->lock, flags);
 }
 
include/linux/prefetch.h renamed from include/linux/prefetch.h~urandom-scalability-fix +11 -0
diff -puN include/linux/prefetch.h~urandom-scalability-fix include/linux/prefetch.h
@@ -54,4 +54,15 @@ static inline void prefetchw(const void 
 #define PREFETCH_STRIDE (4*L1_CACHE_BYTES)
 #endif
 
+static inline void prefetch_range(void *addr, size_t len)
+{
+#ifdef ARCH_HAS_PREFETCH
+	char *cp;
+	char *end = addr + len;
+
+	for (cp = addr; cp < end; cp += PREFETCH_STRIDE)
+		prefetch(cp);
+#endif
+}
+
 #endif

_

#4 lore raw
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line · Andrew Morton

Andrew> We may as well stick prefetch_range() in prefetch.h.

Fair enough.

Andrew> And Matt's patch series is not a thing I want to take on Andrew> board at present, so let's stick with the straight Andrew> scalability patch for now.

Andrew> I moved the prefetch_range() call to outside the spinlock. Andrew> Does that make sense?

The other CPUs will dirty that data, so prefetching it before you hold the lock is almost certainly bad for performance. (Well, to be precise, it really depends on the number of lines dirtied.)

	--david
#5 lore raw
In reply to Andrew Morton
Quoted 9 lines · Andrew Morton
Quoted 7 lines · David Mosberger

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.

Quoted 4 lines

We may as well stick prefetch_range() in prefetch.h.

And Matt's patch series is not a thing I want to take on board at present, so let's stick with the straight scalability patch for now.

Sigh, I'll trim it back to some bits I think are critical.

Quoted 2 lines

I moved the prefetch_range() call to outside the spinlock. Does that make sense?

I don't think that's actually a win. If there's contention, threads racing to the lock will grab the same cache lines and all but one thread's cache will end up invalidated by the time the lock is released.

Signature · 1 line
Matt Mackall : http://www.selenic.com : Linux development and consulting
#6 lore raw
In reply to Andrew Morton
Quoted 14 lines · Andrew Morton
 25-akpm/drivers/char/random.c    |   51 ++++++++++++++++++++++++++-------------
 25-akpm/include/linux/prefetch.h |   11 ++++++++
 2 files changed, 46 insertions(+), 16 deletions(-)

diff -puN drivers/char/random.c~urandom-scalability-fix drivers/char/random.c
+++ 25-akpm/drivers/char/random.c 2004-03-25 17:57:39.795881168 -0800

drivers/char/random.c renamed from drivers/char/random.c~urandom-scalability-fix +3 -0
@@ -490,12 +490,15 @@ static inline __u32 int_ln_12bits(__u32 
  **********************************************************************/
 
 struct entropy_store {
+	/* mostly-read data: */
+	struct poolinfo poolinfo;
+	__u32		*pool;

drivers/char/random.c static inline __u32 int_ln_12bits(__u32 · line 502

Quoted 10 lines
drivers/char/random.c renamed from drivers/char/random.c~urandom-scalability-fix +3 -3
+
+	/* read-write data: */
+	spinlock_t lock ____cacheline_aligned;
 	unsigned	add_ptr;
 	int		entropy_count;
 	int		input_rotate;
-	struct poolinfo poolinfo;
-	__u32		*pool;
-	spinlock_t lock;
 };

Also, I think in general we'd prefer to stick the aligned bit at the front of the structure rather than at the middle, as we'll avoid extra padding. The size of cachelines is getting rather obscene on some modern processors.

Signature · 1 line
Matt Mackall : http://www.selenic.com : Linux development and consulting
#7 lore raw
Quoted 6 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line · Matt Mackall

struct entropy_store {

drivers/char/random.c renamed from drivers/char/random.c~urandom-scalability-fix +3 -0
+	/* mostly-read data: */
+	struct poolinfo poolinfo;
+	__u32		*pool;

drivers/char/random.c static inline __u32 int_ln_12bits(__u32 · line 502

Quoted 10 lines
drivers/char/random.c renamed from drivers/char/random.c~urandom-scalability-fix +3 -3
+
+	/* read-write data: */
+	spinlock_t lock ____cacheline_aligned;
 	unsigned	add_ptr;
 	int		entropy_count;
 	int		input_rotate;
-	struct poolinfo poolinfo;
-	__u32		*pool;
-	spinlock_t lock;
 };

Matt> Also, I think in general we'd prefer to stick the aligned bit at the Matt> front of the structure rather than at the middle, as we'll avoid extra Matt> padding. The size of cachelines is getting rather obscene on some Matt> modern processors.

Not sharing the cacheline between the mostly-read data and the read-write data is the _point_ of this change. If you reverse the order, the "poolinfo" and "pool" members will also get invalidated whenever someone updates the write-intensive data.

	--david
#8 lore raw
Quoted 22 lines · David Mosberger
Quoted 6 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line · Matt Mackall

struct entropy_store {

drivers/char/random.c renamed from drivers/char/random.c~urandom-scalability-fix +3 -0
+	/* mostly-read data: */
+	struct poolinfo poolinfo;
+	__u32		*pool;

drivers/char/random.c static inline __u32 int_ln_12bits(__u32 · line 502

Quoted 10 lines
drivers/char/random.c renamed from drivers/char/random.c~urandom-scalability-fix +3 -3
+
+	/* read-write data: */
+	spinlock_t lock ____cacheline_aligned;
 	unsigned	add_ptr;
 	int		entropy_count;
 	int		input_rotate;
-	struct poolinfo poolinfo;
-	__u32		*pool;
-	spinlock_t lock;
 };

Matt> Also, I think in general we'd prefer to stick the aligned bit at the Matt> front of the structure rather than at the middle, as we'll avoid extra Matt> padding. The size of cachelines is getting rather obscene on some Matt> modern processors.

Quoted 4 lines

Not sharing the cacheline between the mostly-read data and the read-write data is the _point_ of this change. If you reverse the order, the "poolinfo" and "pool" members will also get invalidated whenever someone updates the write-intensive data.

Ok, previous observation made no sense; I should really be taking a nap right now. Hopefully this next one will make more sense: it ought to be ____cacheline_aligned_in_smp as the zero-byte spinlock struct still forces alignment.

Signature · 1 line
Matt Mackall : http://www.selenic.com : Linux development and consulting
#9 lore raw
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line · Matt Mackall

Matt> Ok, previous observation made no sense; I should really be taking a Matt> nap right now. Hopefully this next one will make more sense: it ought Matt> to be ____cacheline_aligned_in_smp as the zero-byte spinlock struct Matt> still forces alignment.

Makes tons of sense, agreed.

	--david
#10 lore raw
In reply to Andrew Morton

include/linux/prefetch.h static inline void prefetchw(const void · line 68

Quoted 12 lines · Andrew Morton
include/linux/prefetch.h renamed from include/linux/prefetch.h~urandom-scalability-fix +11 -0
+static inline void prefetch_range(void *addr, size_t len)
+{
+#ifdef ARCH_HAS_PREFETCH
+	char *cp;
+	char *end = addr + len;
+
+	for (cp = addr; cp < end; cp += PREFETCH_STRIDE)
+		prefetch(cp);
+#endif
+}
+
 #endif

I think this may be dangerous on some CPUs, if may prefetch past the end of the buffer. Ie, if PREFETCH_STRIDE was 32, and len was 65, we'd end up prefetching 65->97. As well as being wasteful to cachelines, this can crash if theres for eg nothing mapped after the next page boundary.

Dave

#11 lore raw
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line · Dave Jones
Quoted 4 lines · Andrew Morton
Quoted 4 lines
(quoted diff) +3 -0
+static inline void prefetch_range(void *addr, size_t len) +{
+#ifdef ARCH_HAS_PREFETCH + char *cp; + char *end = addr + len; +
+ for (cp = addr; cp < end; cp += PREFETCH_STRIDE) +

prefetch(cp); +#endif +} + #endif

Dave> I think this may be dangerous on some CPUs, if may prefetch Dave> past the end of the buffer. Ie, if PREFETCH_STRIDE was 32, and Dave> len was 65, we'd end up prefetching 65->97. As well as being Dave> wasteful to cachelines, this can crash if theres for eg Dave> nothing mapped after the next page boundary.

Huh? It only ever prefetches addresses that are _within_ the specified buffer. Of course it will prefetch entire cachelines, but I hope you're not worried about cachlines crossing page-boundaries! ;-))

	--david
#12 lore raw
Quoted 9 lines · David Mosberger
Quoted 5 lines

I think this may be dangerous on some CPUs, if may prefetch past the end of the buffer. Ie, if PREFETCH_STRIDE was 32, and len was 65, we'd end up prefetching 65->97. As well as being wasteful to cachelines, this can crash if theres for eg nothing mapped after the next page boundary.

Huh? It only ever prefetches addresses that are _within_ the specified buffer. Of course it will prefetch entire cachelines, but I hope you're not worried about cachlines crossing page-boundaries! ;-))

The proposed only user of this may take care of this requirement, but I'm more concerned someone not aware of this requirement using this helper routine. At the least it deserves a comment IMO.

Dave

#13 lore raw
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line · Dave Jones

Dave> The proposed only user of this may take care of this Dave> requirement, but I'm more concerned someone not aware of this Dave> requirement using this helper routine. At the least it Dave> deserves a comment IMO.

A comment sounds like a fine idea. But while at it, the equivalent comment for prefetch() and prefetchw() seems just as appropriate and perhaps even more important.

	--david
#14 lore raw
In reply to David Mosberger
Quoted 15 lines · David Mosberger
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines · Dave Jones
Quoted 4 lines · Andrew Morton
Quoted 4 lines
(quoted diff) +3 -0
+static inline void prefetch_range(void *addr, size_t len) +{
+#ifdef ARCH_HAS_PREFETCH + char *cp; + char *end = addr + len; +
+ for (cp = addr; cp < end; cp += PREFETCH_STRIDE) +

prefetch(cp); +#endif +} + #endif

Dave> I think this may be dangerous on some CPUs, if may prefetch Dave> past the end of the buffer. Ie, if PREFETCH_STRIDE was 32, and Dave> len was 65, we'd end up prefetching 65->97. As well as being Dave> wasteful to cachelines, this can crash if theres for eg Dave> nothing mapped after the next page boundary.

Quoted 4 lines

Huh? It only ever prefetches addresses that are _within_ the specified buffer. Of course it will prefetch entire cachelines, but I hope you're not worried about cachlines crossing page-boundaries! ;-))

But the start address which is fed into prefetch_range() may not be cacheline-aligned. So if appropriately abused, a prefetch_range() could wander off the end of the user's buffer and into a new page.

I think this gets it right, but I probably screwed something up.

static inline void prefetch_range(void *addr, size_t len) {

#ifdef ARCH_HAS_PREFETCH
	char *cp;
	unsigned long end;

	end = ((unsigned long)addr + len + PREFETCH_STRIDE - 1);
	end &= ~(PREFETCH_STRIDE - 1);

	for (cp = addr; cp < (char *)end; cp += PREFETCH_STRIDE)
		prefetch(cp);

#endif
}

#15 lore raw
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line · Andrew Morton

Andrew> But the start address which is fed into prefetch_range() may Andrew> not be cacheline-aligned. So if appropriately abused, a Andrew> prefetch_range() could wander off the end of the user's Andrew> buffer and into a new page.

Andrew> I think this gets it right, but I probably screwed something Andrew> up.

Please, let's not make this more complicated than it is. The cacheline alignment doesn't matter at all. Provided prefetch_range() is given a range of guaranteed to be valid memory, then it will be fine. It never touches anything outside the specified range.

	--david
#16 lore raw
Quoted 8 lines · David Mosberger
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines · Andrew Morton

Andrew> But the start address which is fed into prefetch_range() may Andrew> not be cacheline-aligned. So if appropriately abused, a Andrew> prefetch_range() could wander off the end of the user's Andrew> buffer and into a new page.

Quoted 7 lines

Andrew> I think this gets it right, but I probably screwed something Andrew> up.

Please, let's not make this more complicated than it is. The cacheline alignment doesn't matter at all. Provided prefetch_range() is given a range of guaranteed to be valid memory, then it will be fine. It never touches anything outside the specified range.

If someone does, say,

	prefetch_range(some_pointer, sizeof(*some_pointer));

then it is possible that prefetch_range() could

a) execute a prefetch at addresses which are not PREFETCH_STRIDE-aligned and, as a consequence,

b) prefetch data from the next page, outside the range of the user's (addr,len).

#17 lore raw
Quoted 6 lines

a) execute a prefetch at addresses which are not PREFETCH_STRIDE-aligned and, as a consequence,

b) prefetch data from the next page, outside the range of the user's (addr,len).

well if you assume that cachelines (and prefetch stride) are proper divisors of PAGE_SIZE is that still true ?

#18 lore raw
Quoted 9 lines · Arjan van de Ven
Quoted 6 lines

a) execute a prefetch at addresses which are not PREFETCH_STRIDE-aligned and, as a consequence,

b) prefetch data from the next page, outside the range of the user's (addr,len).

well if you assume that cachelines (and prefetch stride) are proper divisors of PAGE_SIZE is that still true ?

Probably not ;)

If someone does

	prefetch_range(4096, 1);

on 4k pagesize, what should we do?

Issuing a single

	prefetch 4090

sounds reasonable.

In that case I'm arranging for it to perform

	prefetch (4096 - 32)

in that case, which seems neater.

#19 lore raw
Quoted 5 lines · Andrew Morton

If someone does

	prefetch_range(4090, 20);

on 4k pagesize, what should we do?

well if the datastructure you prefetch crosses pageboundary you know both pages are safe to prefetch.

Quoted 11 lines

Issuing a single

	prefetch 4090

sounds reasonable.

In that case I'm arranging for it to perform

	prefetch (4096 - 32)

in that case, which seems neater.

well prefetch is defined as "get the cacheline the address is located in"; eg the cpu does the rounding to cacheline size for you.

(btw prefetch stride isn't the cacheline size! it's how far you're supposed to prefetch ahead to get any useful gain, si for aligning and stuff it's useless)

#20 lore raw
In reply to Andrew Morton
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line · Andrew Morton

Andrew> If someone does, say,

  Andrew> 	prefetch_range(some_pointer, sizeof(*some_pointer));

Andrew> then it is possible that prefetch_range() could

Andrew> a) execute a prefetch at addresses which are not Andrew> PREFETCH_STRIDE-aligned and, as a consequence,

Andrew> b) prefetch data from the next page, outside the range of Andrew> the user's (addr,len).

This is getting silly. Cache-lines _never_ cross page-boundaries.

	--david