Skip to contentSkip to conversation

queued spinlock code and results

DISCUSSION Nick Piggin 5 participants 14 messages Jul 8, 2007 – Jul 11, 2007

lore
Share & tools
lore
#0 lore raw

I made some tests of the queued spinlock code using userspace test code on 64-bit processors. I believe the xadd based code no longer has any theoretical memory ordering problems.

The tests were done on 3 different architectures of different speeds and vintages (so not really comparable between columns). I have attached the two programs I used to make the results. Times are total elapsed time divided by the number of locks (so effectively you get the time required for lock+unlock).

The threaded results also attempt to have an unfairness count, which is the max number of times in a row that a lock is acquired, when all other threads are also executing in the loop -- the reason xadd for example is not always 0 there is because the other threads may not have reached the lock before the current thread was able to get it several times (eg. if an interrupt comes in, this could happen).

The threaded results are actually not too interesting because firstly they don't really simulate the right mixture and timing of locks and critical section time vs parallel time, and secondly the times are pretty heavily skewed toward the unfair locks which tend to be _really_ unfair (eg. on the last test, some threads were taking a full 2x longer to finish than others) and so each thread gets to run for a long time without cache misses and thus the overall throughput goes up. The dual-core core2 for another example did regularly starve each thread for up to about 7*ms* (13 million cycles) while the other was taking and releasing the lock.

However the non-threaded numbers (first 4 rows) are reasonably good. I found on Core2 that if the inner loop was simply a lock+unlock and nothing else, the inc-lock gained a bit more over the xadd-lock, but I don't think this is representative of real code and it may just have been some alignment or scheduling easter egg.

The results show that the xadd lock is definitely slower in single thread, however the Core2 does really well, and also the cache cold case is pretty insignificant.

It suggests to me that it *may* be worth trying a wholesale replacement of spinlock with queued spinlock on x86 (starting as a config option which we could perhaps default to ON in -mm / early -rcs). I think the main risk is if there is some code that is really relying on the unfair batching nature of the locks for good performance. I would argue that would usually be poor code (eg. taking and dropping the spinlock too often, too much contention on the lock, or using the wrong type of lock in the first place) -- I think cacheline batching is great for regular lines, but not quite so nice for locks. It would be interesting to see how something like the dcache lock goes in dcache heavy workloads...

                         | Core2           Pentium 4 (Nocona)  Opteron
inc in cache             |  21.4ns           38.7ns              11.8ns
xadd in cache            |  22.5ns           44.4ns              14.5ns
                         |
inc no cache             | 122.2ns          153.5ns             172.7ns
xadd no cache            | 123.9ns          154.7ns             174.0ns
                         |
inc 2 thread (unfair)    | 230.9ns (69211)  376.5ns (3104)      174.0ns (2068) 
xadd 2 thread (unfair)   | 273.2ns (0)      307.1ns (59)        743.8ns (220)
                         |
inc 2 thread, other skt  |                  144.8ns (20444)     145.7ns (39739)
xadd 2 thread, other skt |                  306.8ns (147)       748.0ns (488)
                         |
inc 4 thread             |                 1248.9ns (172)      1158.5ns (139410)
xadd 4 thread            |                 1014.0ns (0)        2843.5ns (0)
                         |
inc 4 thread, diff skts  |                                     1598.0ns (65727)
xadd 4 thread, diff skts |                                     2848.1ns (0)
                         |
inc 16 thread            |                                     19017ns (55698)
xadd 16 thread           |                                     42723ns (0)

#define LOCK_INIT 1
static void lock(short *lock)

{
	__asm__ __volatile__ ("1:\n\t"
			      "lock ; decb %0\n\t"
			      "jns 2f\n\t"
			      "3:\n\t"
			      "rep ; nop\n\t"
			      "cmpb $0,%0\n\t"
			      "jle 3b\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

static void unlock(short *lock)

{
	__asm__ __volatile__ ("movb $1,%0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

#define XLOCK_INIT 0
static void xlock(short *lock)

{
	short i = 0x0100;
	__asm__ __volatile__ ("lock ; xaddw %%ax, %1\n\t"
			      "1:\n\t"
			      "cmpb %%ah, %%al\n\t"
			      "je 2f\n\t"
			      "rep ; nop\n\t"
			      "movb %1, %%al\n\t"
			      "lfence\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+a" (i), "+m" (*lock)
			    : : "memory");
}

static void xunlock(short *lock)

{
	__asm__ __volatile__ ("incb %0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

---

#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>

struct page {
	short lock;
	unsigned int next;
};

#define NR_PAGES (2*1024*1024)
static struct page pages[NR_PAGES];

#define LOCK_INIT 1
static void lock(short *lock)

{
	__asm__ __volatile__ ("1:\n\t"
			      "lock ; decb %0\n\t"
			      "jns 2f\n\t"
			      "3:\n\t"
			      "rep ; nop\n\t"
			      "cmpb $0,%0\n\t"
			      "jle 3b\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

static void unlock(short *lock)

{
	__asm__ __volatile__ ("movb $1,%0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

#define XLOCK_INIT 0
static void xlock(short *lock)

{
	short i = 0x0100;
	__asm__ __volatile__ ("lock ; xaddw %%ax, %1\n\t"
			      "1:\n\t"
			      "cmpb %%ah, %%al\n\t"
			      "je 2f\n\t"
			      "rep ; nop\n\t"
			      "movb %1, %%al\n\t"
			      "lfence\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+a" (i), "+m" (*lock)
			    : : "memory");
}

static void xunlock(short *lock)

{
	__asm__ __volatile__ ("incb %0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

static int xlock_is_locked(short *lock)

{
	short tmp = *lock;
	char *x = (char *)&tmp;

	return (*x != *(x+1));
}

#define ITERS (16*1024*1024)
#define IN_ITERS (ITERS*5)

int main(void)

{
	int nr_pages;
	int nr;
	int i;
	struct page *p;
	struct timeval start, end;
	unsigned long long usec;
	unsigned int tmp;

	nr_pages = 10;
	srandom(10);
	p = &pages[0];
	i = 0;
	nr = 0;
	while (nr < nr_pages-1) {
		unsigned int n;

		n = random() % NR_PAGES;
		while (p == &pages[n] || pages[n].next)
			n = (n+1) % NR_PAGES;
		p->next = n;
		p = &pages[n];
		nr++;
	}
	p->next = 0;

	for (i = 0; i < NR_PAGES; i++)
		pages[i].lock = LOCK_INIT;
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < IN_ITERS; i++) {
		lock(&p->lock);
		tmp = p->next;
		unlock(&p->lock);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("inc-lock in cache takes %0.2lfns\n", (double)usec * 1000 / IN_ITERS);

	for (i = 0; i < NR_PAGES; i++)
		pages[i].lock = XLOCK_INIT;
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < IN_ITERS; i++) {
		xlock(&p->lock);
		tmp = p->next;
		xunlock(&p->lock);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("xadd-lock in cache takes %0.2lfns\n", (double)usec * 1000 / IN_ITERS);

	for (i = 0; i < NR_PAGES; i++)
		pages[i].next = 0;

	nr_pages = NR_PAGES;
	srandom(10);
	p = &pages[0];
	i = 0;
	nr = 0;
	while (nr < nr_pages-1) {
		unsigned int n;

		n = random() % NR_PAGES;
		while (p == &pages[n] || pages[n].next)
			n = (n+1) % NR_PAGES;
		p->next = n;
		p = &pages[n];
		nr++;
	}
	p->next = 0;

	for (i = 0; i < NR_PAGES; i++)
		pages[i].lock = LOCK_INIT;
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < ITERS; i++) {
		lock(&p->lock);
		tmp = p->next;
		unlock(&p->lock);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("inc-lock out of cache takes %0.2lfns\n", (double)usec * 1000 / ITERS);


	for (i = 0; i < NR_PAGES; i++)
		pages[i].lock = XLOCK_INIT;
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < ITERS; i++) {
		xlock(&p->lock);
		tmp = p->next;
		xunlock(&p->lock);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("xadd-lock out of cache takes %0.2lfns\n", (double)usec * 1000 / ITERS);


	return 0;
}

#define _GNU_SOURCE
#include <sched.h>
#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include <unistd.h>

static short glock;

#define LOCK_INIT 1
static void lock(short *lock)

{
	__asm__ __volatile__ ("1:\n\t"
			      "lock ; decb %0\n\t"
			      "jns 2f\n\t"
			      "3:\n\t"
			      "rep ; nop\n\t"
			      "cmpb $0,%0\n\t"
			      "jle 3b\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

static void unlock(short *lock)

{
	__asm__ __volatile__ ("movb $1,%0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

#define XLOCK_INIT 0
static void xlock(short *lock)

{
	short i = 0x0100;
	__asm__ __volatile__ ("lock ; xaddw %%ax, %1\n\t"
			      "1:\n\t"
			      "cmpb %%ah, %%al\n\t"
			      "je 2f\n\t"
			      "rep ; nop\n\t"
			      "movb %1, %%al\n\t"
			      "lfence\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+a" (i), "+m" (*lock)
			    : : "memory");
}

static void xunlock(short *lock)

{
	__asm__ __volatile__ ("incb %0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

#define NR_THREADS 16
#define ITERS (1024*1024)

static int seq;
static int started, finished;

static void *thread(void *arg)

{
	unsigned long nr = (unsigned long)arg;
	int i;
	int oldseq = -1;
	int max_row = 0;
	int row = 0;
	cpu_set_t cpuset;

	CPU_ZERO(&cpuset);
	CPU_SET(nr, &cpuset);
	if (sched_setaffinity(0, sizeof(cpuset), &cpuset) == -1)
		perror("sched_setaffinity"), exit(1);

	lock(&glock);
	started++;
	unlock(&glock);

	for (i = 0; i < ITERS; i++) {
		int tmp;

		lock(&glock);	
		tmp = seq;
		seq++;		
		unlock(&glock);	

		if (started == NR_THREADS && !finished && tmp == oldseq) {
			row++;
			if (row > max_row)
				max_row = row;
		} else
			row = 0;
		oldseq = tmp+1;
	}

	lock(&glock);
	finished++;
	unlock(&glock);

	printf("inc-lock maximum unfair locks = %d\n", max_row);

	return NULL;
}

static void *xthread(void *arg)

{
	unsigned long nr = (unsigned long)arg;
	int i;
	int oldseq = -1;
	int max_row = 0;
	int row = 0;
	cpu_set_t cpuset;

	CPU_ZERO(&cpuset);
	CPU_SET(nr, &cpuset);
	if (sched_setaffinity(0, sizeof(cpuset), &cpuset) == -1)
		perror("sched_setaffinity"), exit(1);

	xlock(&glock);
	started++;
	xunlock(&glock);

	for (i = 0; i < ITERS; i++) {
		int tmp;

		xlock(&glock);	
		tmp = seq;
		seq++;		
		xunlock(&glock);	

		if (started == NR_THREADS && !finished && tmp == oldseq) {
			row++;
			if (row > max_row)
				max_row = row;
		} else {
			row = 0;
		}
		oldseq = tmp+1;
	}

	xlock(&glock);
	finished++;
	xunlock(&glock);

	printf("xadd-lock maximum unfair locks = %d\n", max_row);

	return NULL;
}

int main(void)

{
	struct timeval start, end;
	unsigned long long usec;
	pthread_t t[NR_THREADS];
	int i;

	seq = started = finished = 0;
	glock = LOCK_INIT;
	lock(&glock);
	for (i = 0; i < NR_THREADS; i++) {
		if (pthread_create(&t[i], NULL, thread, (void *)(unsigned long)i) == -1)
			perror("pthread_create"), exit(1);
	}
	usleep(1000000);
	gettimeofday(&start, NULL);
	unlock(&glock);

	for (i = 0; i < NR_THREADS; i++) {
		if (pthread_join(t[i], NULL) == -1)
			perror("pthread_join"), exit(1);
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("inc-lock contended takes %0.2lfns\n", (double)usec * 1000 / ITERS);

	seq = started = finished = 0;
	glock = XLOCK_INIT;
	xlock(&glock);
	for (i = 0; i < NR_THREADS; i++) {
		if (pthread_create(&t[i], NULL, xthread, (void *)(unsigned long)i) == -1)
			perror("pthread_create"), exit(1);
	}
	usleep(1000000);
	gettimeofday(&start, NULL);
	xunlock(&glock);

	for (i = 0; i < NR_THREADS; i++) {
		if (pthread_join(t[i], NULL) == -1)
			perror("pthread_join"), exit(1);
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("xadd-lock contended takes %0.2lfns\n", (double)usec * 1000 / ITERS);

	return 0;
}
#1 lore raw
Quoted 3 lines · Nick Piggin

I made some tests of the queued spinlock code using userspace test code on 64-bit processors. I believe the xadd based code no longer has any theoretical memory ordering problems.

Linus, the background of this is that on 8 socket Opteron systems the current spinlocks can become very unfair to the point of severe starvation. These boxes are becomming more common.

Quoted 6 lines

The threaded results also attempt to have an unfairness count, which is the max number of times in a row that a lock is acquired, when all other threads are also executing in the loop -- the reason xadd for example is not always 0 there is because the other threads may not have reached the lock before the current thread was able to get it several times (eg. if an interrupt comes in, this could happen).

Interesting. I was also thinking about switching the lock types at boot time. Since all the lock calls are out of line this would be reasonably easy.

I would say the main drawback of switchable and queued locks would be also that they require a larger spinlock_t thus increasing cache usage

e.g. it would probably hurt for the large spinlock tables used by TCP, but then those should be fixed anyways to be smaller.

-Andi

#2 lore raw
Quoted 17 lines · Andi Kleen
Quoted 3 lines · Nick Piggin

I made some tests of the queued spinlock code using userspace test code on 64-bit processors. I believe the xadd based code no longer has any theoretical memory ordering problems.

Linus, the background of this is that on 8 socket Opteron systems the current spinlocks can become very unfair to the point of severe starvation. These boxes are becomming more common.

Quoted 6 lines

The threaded results also attempt to have an unfairness count, which is the max number of times in a row that a lock is acquired, when all other threads are also executing in the loop -- the reason xadd for example is not always 0 there is because the other threads may not have reached the lock before the current thread was able to get it several times (eg. if an interrupt comes in, this could happen).

Quoted 7 lines

Interesting. I was also thinking about switching the lock types at boot time. Since all the lock calls are out of line this would be reasonably easy.

I would say the main drawback of switchable and queued locks would be also that they require a larger spinlock_t thus increasing cache usage

Technically the queued locks require twice the size (but I think the implementation can handle 256 CPUs with 16 bits, while dec based can only handle 128 with 8 bits -- not a big deal I know, but we'll probably get there soon).

However currently spinlocks are much bigger than they could be anyway (4 bytes, could be 1). Although often the alignment of data structures will make the gain not so big.

But that said, I don't like to justify slightly suboptimal code by saying that existing code is even less optimal :)

One other upshot of the queued spinlocks is that they don't need the break_lock field, or any of the associated logic with that (because it is trivial to test whether a lock is held and also how many others are spinning on it). So that gives us for free an avenue into more advanced congestion or spin backoff algorithms.

#3 lore raw
In reply to Andi Kleen
Quoted 10 lines · Andi Kleen
Quoted 3 lines · Nick Piggin

I made some tests of the queued spinlock code using userspace test code on 64-bit processors. I believe the xadd based code no longer has any theoretical memory ordering problems.

Linus, the background of this is that on 8 socket Opteron systems the current spinlocks can become very unfair to the point of severe starvation. These boxes are becomming more common.

Yeah, considering the numbers, I don't have any real objections here.

I would ask that the code be given to both Intel and AMD engineers to look over, just to verify that the lfence is sufficient (or whether it's even needed), but I think the use of "xaddw" to both increment _and_ load the old value for the non-contention case is an obviously good (and clever) way to handle that one, and even if we'd have to add something heavier than the lfence to the contended case, it looks fine to me.

So the only remaining issue is that unfairness is probably really good for some loads (not just for the spinlock itself - it will likely cause much better cache behaviour for stuff _inside_ the lock to stay on the same core), but I don't think we want to optimize for the contended case anyway, so that's more of a "it will be interesting to see" kind of comment.

In short: if we can have AMD/Intel engineers look this over for any subtle issues, and they are happy, then I'm happy.

Linus

#4 lore raw
In reply to Andi Kleen
Quoted 3 lines · Andi Kleen

I would say the main drawback of switchable and queued locks would be also that they require a larger spinlock_t thus increasing cache usage

Right. Zoran Radovic has shown that queued locks are inferior to other approaches. The best approach that he found in his research were the HBO locks that are somewhat more intelligent form of spinlocks.

http://user.it.uu.se/~zoranr/
http://www.it.uu.se/research/group/uart/projects/nucasynch/

Paper on the issue with measurements:
http://www.it.uu.se/research/publications/lic/2003-008/2003-008.pdf

#5 lore raw
Quoted 10 lines · Christoph Lameter
Quoted 3 lines · Andi Kleen

I would say the main drawback of switchable and queued locks would be also that they require a larger spinlock_t thus increasing cache usage

Right. Zoran Radovic has shown that queued locks are inferior to other approaches. The best approach that he found in his research were the HBO locks that are somewhat more intelligent form of spinlocks.

Quoted 5 lines

http://user.it.uu.se/~zoranr/
http://www.it.uu.se/research/group/uart/projects/nucasynch/

Paper on the issue with measurements:
http://www.it.uu.se/research/publications/lic/2003-008/2003-008.pdf

OK, maybe I do have my terminology wrong -- we'll call them FIFO locks or ticket locks. The point is not to improve performance of the contended case (although they may have slightly better contended case characteristicds), but to improve worst case latency and improve fairness.

BTW. some advanced congestion algorithms like HBO may find these ticket locks useful because you can see immediately how many CPUs are contending the lock, and spinners know how many CPUs are in front of them. That info could be fed into the spin backoff scheme.

#6 lore raw
Quoted 4 lines · Nick Piggin

BTW. some advanced congestion algorithms like HBO may find these ticket locks useful because you can see immediately how many CPUs are contending the lock, and spinners know how many CPUs are in front of them. That info could be fed into the spin backoff scheme.

That would mean having to keep a lot of status information for a spinlock. Gets pretty complicated.

The RT tree already converts spinlocks to sleeping locks? If we want to be that complicated then maybe going with one sophisticated lock type for all would be the solution.

#7 lore raw
Quoted 9 lines · Christoph Lameter
Quoted 4 lines · Nick Piggin

BTW. some advanced congestion algorithms like HBO may find these ticket locks useful because you can see immediately how many CPUs are contending the lock, and spinners know how many CPUs are in front of them. That info could be fed into the spin backoff scheme.

That would mean having to keep a lot of status information for a spinlock. Gets pretty complicated.

Did you look at the implementation? It takes 2 bytes on x86 and is almost the same code size and speed as the existing locks.

Quoted 3 lines

The RT tree already converts spinlocks to sleeping locks? If we want to be that complicated then maybe going with one sophisticated lock type for all would be the solution.

I don't want to convert spinlocks to sleeping locks though.

#8 lore raw
In reply to Nick Piggin
Quoted 9 lines · Nick Piggin

I made some tests of the queued spinlock code using userspace test code on 64-bit processors. I believe the xadd based code no longer has any theoretical memory ordering problems.

The tests were done on 3 different architectures of different speeds and vintages (so not really comparable between columns). I have attached the two programs I used to make the results. Times are total elapsed time divided by the number of locks (so effectively you get the time required for lock+unlock).

Quoted 6 lines

The threaded results also attempt to have an unfairness count, which is the max number of times in a row that a lock is acquired, when all other threads are also executing in the loop -- the reason xadd for example is not always 0 there is because the other threads may not have reached the lock before the current thread was able to get it several times (eg. if an interrupt comes in, this could happen).

I was trying to look how costly is having a double-short counter, instead of a single byte.
The V-lock uses two short counters w/out the double-xadd optimization, while the Z-lock uses it.
This is a dual Opteron 252, but the test is done in single thread only (multi-thread really has no meaning for this test):

inc-lock in cache takes 7.28ns
xadd-lock in cache takes 8.93ns
vadd-lock in cache takes 10.35ns
zadd-lock in cache takes 8.43ns
inc-lock out of cache takes 87.85ns
xadd-lock out of cache takes 88.15ns
vadd-lock out of cache takes 89.38ns
zadd-lock out of cache takes 88.10ns

In this box, the always-lfence V-lock code pays for it. If I remove the lfence from the V-lock (but that's not possible), I get:

inc-lock in cache takes 7.28ns
xadd-lock in cache takes 8.93ns
vadd-lock in cache takes 7.67ns
zadd-lock in cache takes 8.44ns
inc-lock out of cache takes 87.87ns
xadd-lock out of cache takes 88.15ns
vadd-lock out of cache takes 88.24ns
zadd-lock out of cache takes 88.12ns

So in this box, and in this test, the double-short Z-lock seems faster than a double-byte. I've no idea why, since it uses two ops more and an extra register.

- Davide

#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>

struct page {
	short lock[2];
	unsigned int next;
};

#define NR_PAGES (2*1024*1024)
static struct page pages[NR_PAGES];

#define LOCK_INIT(l) (l)[0] = 1
static inline void lock(short *lock)

{
	__asm__ __volatile__ ("1:\n\t"
			      "lock ; decb %0\n\t"
			      "jns 2f\n\t"
			      "3:\n\t"
			      "rep ; nop\n\t"
			      "cmpb $0,%0\n\t"
			      "jle 3b\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

static inline void unlock(short *lock)

{
	__asm__ __volatile__ ("movb $1,%0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

#define XLOCK_INIT(l) (l)[0] = 0
static inline void xlock(short *lock)

{
	short i = 0x0100;
	__asm__ __volatile__ ("lock ; xaddw %%ax, %1\n\t"
			      "1:\n\t"
			      "cmpb %%ah, %%al\n\t"
			      "je 2f\n\t"
			      "rep ; nop\n\t"
			      "movb %1, %%al\n\t"
			      "lfence\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+a" (i), "+m" (*lock)
			    : : "memory");
}

static inline void xunlock(short *lock)

{
	__asm__ __volatile__ ("incb %0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

#define VLOCK_INIT(l) (l)[0] = 0, (l)[1] = 0
static inline void vlock(short *lock)

{
	__asm__ __volatile__ ("lock ; xaddw %%ax, %0\n\t"
			      "1:\n\t"
			      "cmpw %%ax, %1\n\t"
			      "je 2f\n\t"
			      "rep ; nop\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			      "lfence\n\t"
			    : "+m" (lock[1])
			    : "m" (lock[0]), "a" (1) : "memory");
}

static inline void vunlock(short *lock)

{
	__asm__ __volatile__ ("incw %0\n\t"
			    : "+m" (lock[0])
			    : : "memory");
}

#define ZLOCK_INIT(l) (l)[0] = 0, (l)[1] = 0
static inline void zlock(short *lock)

{
	__asm__ __volatile__ ("lock ; xaddl %%eax, %0\n\t"
			      "mov %%eax, %%ebx\n\t"
			      "shr $16, %%ebx\n\t"
			      "1:\n\t"
			      "cmpw %%ax, %%bx\n\t"
			      "je 2f\n\t"
			      "rep ; nop\n\t"
			      "movw %1, %%bx\n\t"
			      "lfence\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+m" (*(int *) lock)
			    : "m" (lock[0]), "a" (0x10000) : "ebx", "memory");
}

static inline void zunlock(short *lock)

{
	__asm__ __volatile__ ("incw %0\n\t"
			    : "+m" (lock[0])
			    : : "memory");
}

static int xlock_is_locked(short *lock)

{
	short tmp = *lock;
	char *x = (char *)&tmp;

	return (*x != *(x+1));
}

#define ITERS (16*1024*1024)
#define IN_ITERS (ITERS*5)

int main(void)

{
	int nr_pages;
	int nr;
	int i;
	struct page *p;
	struct timeval start, end;
	unsigned long long usec;
	unsigned int tmp;

	nr_pages = 10;
	srandom(10);
	p = &pages[0];
	i = 0;
	nr = 0;
	while (nr < nr_pages-1) {
		unsigned int n;

		n = random() % NR_PAGES;
		while (p == &pages[n] || pages[n].next)
			n = (n+1) % NR_PAGES;
		p->next = n;
		p = &pages[n];
		nr++;
	}
	p->next = 0;

	for (i = 0; i < NR_PAGES; i++)
		LOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < IN_ITERS; i++) {
		lock(&p->lock[0]);
		tmp = p->next;
		unlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("inc-lock in cache takes %0.2lfns\n", (double)usec * 1000 / IN_ITERS);

	for (i = 0; i < NR_PAGES; i++)
		XLOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < IN_ITERS; i++) {
		xlock(&p->lock[0]);
		tmp = p->next;
		xunlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("xadd-lock in cache takes %0.2lfns\n", (double)usec * 1000 / IN_ITERS);

	for (i = 0; i < NR_PAGES; i++)
		VLOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < IN_ITERS; i++) {
		vlock(&p->lock[0]);
		tmp = p->next;
		vunlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("vadd-lock in cache takes %0.2lfns\n", (double)usec * 1000 / IN_ITERS);

	for (i = 0; i < NR_PAGES; i++)
		ZLOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < IN_ITERS; i++) {
		zlock(&p->lock[0]);
		tmp = p->next;
		zunlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("zadd-lock in cache takes %0.2lfns\n", (double)usec * 1000 / IN_ITERS);
	
	for (i = 0; i < NR_PAGES; i++)
		pages[i].next = 0;

	nr_pages = NR_PAGES;
	srandom(10);
	p = &pages[0];
	i = 0;
	nr = 0;
	while (nr < nr_pages-1) {
		unsigned int n;

		n = random() % NR_PAGES;
		while (p == &pages[n] || pages[n].next)
			n = (n+1) % NR_PAGES;
		p->next = n;
		p = &pages[n];
		nr++;
	}
	p->next = 0;

	for (i = 0; i < NR_PAGES; i++)
		LOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < ITERS; i++) {
		lock(&p->lock[0]);
		tmp = p->next;
		unlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("inc-lock out of cache takes %0.2lfns\n", (double)usec * 1000 / ITERS);


	for (i = 0; i < NR_PAGES; i++)
		XLOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < ITERS; i++) {
		xlock(&p->lock[0]);
		tmp = p->next;
		xunlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("xadd-lock out of cache takes %0.2lfns\n", (double)usec * 1000 / ITERS);

	for (i = 0; i < NR_PAGES; i++)
		VLOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < ITERS; i++) {
		vlock(&p->lock[0]);
		tmp = p->next;
		vunlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("vadd-lock out of cache takes %0.2lfns\n", (double)usec * 1000 / ITERS);

	for (i = 0; i < NR_PAGES; i++)
		ZLOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < ITERS; i++) {
		zlock(&p->lock[0]);
		tmp = p->next;
		zunlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("zadd-lock out of cache takes %0.2lfns\n", (double)usec * 1000 / ITERS);

	return 0;
}
#9 lore raw
Quoted 10 lines · Davide Libenzi

#define ZLOCK_INIT(l) (l)[0] = 0, (l)[1] = 0
static inline void zlock(short *lock)

{
	__asm__ __volatile__ ("lock ; xaddl %%eax, %0\n\t"
			      "mov %%eax, %%ebx\n\t"
			      "shr $16, %%ebx\n\t"
			      "1:\n\t"
			      "cmpw %%ax, %%bx\n\t"
			      "je 2f\n\t"
			      "rep ; nop\n\t"
- 			      "movw %1, %%bx\n\t"
+ 			      "movw %1, %%ax\n\t"
> 			      "lfence\n\t"
> 			      "jmp 1b\n\t"
> 			      "2:\n\t"
Quoted 3 lines
			    : "+m" (*(int *) lock)
			    : "m" (lock[0]), "a" (0x10000) : "ebx", "memory");
}

Erm, modulo that bugger ;) that'd never should up in the non-contended case (and that does not change numbers):

inc-lock in cache takes 7.28ns xadd-lock in cache takes 8.93ns vadd-lock in cache takes 10.34ns zadd-lock in cache takes 8.43ns inc-lock out of cache takes 87.98ns xadd-lock out of cache takes 88.89ns vadd-lock out of cache takes 89.59ns zadd-lock out of cache takes 89.86ns

- Davide

#10 lore raw
In reply to Davide Libenzi
Quoted 4 lines · Davide Libenzi

So in this box, and in this test, the double-short Z-lock seems faster than a double-byte. I've no idea why, since it uses two ops more and an extra register.

At this kind of level, the exact instruction scheduling can make a big difference.

The extra register usage won't matter if there is no register pressure, and any extra instructions can actually happen to *help*, if they end up just aligning something just the right way.

There can also be various random effects of prefixes: decoding x86 instructions is basically a very uarch-specific issue, and for all we know it might be that the AMD setup may well end up behaving differently from most Intel chips (and within the Intel family, the netburst situation is likely different from the other P6-derived cores).

For example, does a single prefix decode faster? It could be that the combination of "lock" _and_ "opsize" prefixes is problematic (as in a 16-bit locked "lock xaddw"), and causes a decode hickup, but that "lock" and "opsize" on their own don't cause any decoder issues (ie doing the "lock" on the 32-bit xadd, and just the "opsize" prefix on the 16-bit decw both are fast).

But on another uarch it might work out the other way: if "lock" is always a complex op, then having a opsize prefix on that one might be "free", and then you're better combining them for the locked 16-bit xadd, and having the releasing "decb" not have any prefix at all.

And regardless of that, just a random "it happened to get aligned that way" (where "alignment" might be about hitting the cache-line just right, but might also be about just having the right instruction mix to get the intel decoders to run at their full 4-1-1-1 capacity), causing the timing differences.

So before taking these numbers as any kind of "real" values, I'd suggest:

- trying it out on at least a few different uarchs (Opteron, P4 and Core 2 all have quite different restrictions on decoding)

- possibly trying it out with things in different order and different compiler options (-O2 vs -Os), trying to cause different kinds of alignment issues.

Also, just a small nit: in the kernel, the locking would _not_ be inlined (but the unlocking would), so marking the lock functions "inline" is probably a bad idea. Without the inline, it's likely more realistic, and the effects of register pressure will be hidden. Because of the uninlining nature of locks, I think you can generally ignore the "one or two registers" issue - you'll have three caller-clobbered registers to play with regardless.

Linus

#11 lore raw
Quoted 46 lines · Linus Torvalds
Quoted 4 lines · Davide Libenzi

So in this box, and in this test, the double-short Z-lock seems faster than a double-byte. I've no idea why, since it uses two ops more and an extra register.

At this kind of level, the exact instruction scheduling can make a big difference.

The extra register usage won't matter if there is no register pressure, and any extra instructions can actually happen to *help*, if they end up just aligning something just the right way.

There can also be various random effects of prefixes: decoding x86 instructions is basically a very uarch-specific issue, and for all we know it might be that the AMD setup may well end up behaving differently from most Intel chips (and within the Intel family, the netburst situation is likely different from the other P6-derived cores).

For example, does a single prefix decode faster? It could be that the combination of "lock" _and_ "opsize" prefixes is problematic (as in a 16-bit locked "lock xaddw"), and causes a decode hickup, but that "lock" and "opsize" on their own don't cause any decoder issues (ie doing the "lock" on the 32-bit xadd, and just the "opsize" prefix on the 16-bit decw both are fast).

But on another uarch it might work out the other way: if "lock" is always a complex op, then having a opsize prefix on that one might be "free", and then you're better combining them for the locked 16-bit xadd, and having the releasing "decb" not have any prefix at all.

And regardless of that, just a random "it happened to get aligned that way" (where "alignment" might be about hitting the cache-line just right, but might also be about just having the right instruction mix to get the intel decoders to run at their full 4-1-1-1 capacity), causing the timing differences.

So before taking these numbers as any kind of "real" values, I'd suggest:

- trying it out on at least a few different uarchs (Opteron, P4 and Core 2 all have quite different restrictions on decoding)

- possibly trying it out with things in different order and different compiler options (-O2 vs -Os), trying to cause different kinds of alignment issues.

Quoted 7 lines

Also, just a small nit: in the kernel, the locking would _not_ be inlined (but the unlocking would), so marking the lock functions "inline" is probably a bad idea. Without the inline, it's likely more realistic, and the effects of register pressure will be hidden. Because of the uninlining nature of locks, I think you can generally ignore the "one or two registers" issue - you'll have three caller-clobbered registers to play with regardless.

Indeed, with no inline, on a P4 (with -O2), numbers betweeen xadd-lock and zadd-lock gets closer:

inc-lock in cache takes 35.15ns
xadd-lock in cache takes 43.84ns
vadd-lock in cache takes 53.51ns
zadd-lock in cache takes 43.28ns
inc-lock out of cache takes 122.92ns
xadd-lock out of cache takes 126.98ns
vadd-lock out of cache takes 172.36ns
zadd-lock out of cache takes 126.01ns

The always-lfence instruction in vadd-lock really is painfull though. If numbers are close, and given that spinlock size considering structure alignments should not matter much, wouldn't it be better to use a double short and remove the 256 CPUs cap?

- Davide

#12 lore raw
Quoted 5 lines · Davide Libenzi

The always-lfence instruction in vadd-lock really is painfull though. If numbers are close, and given that spinlock size considering structure alignments should not matter much, wouldn't it be better to use a double short and remove the 256 CPUs cap?

On x86? No.

There are no issues with the 255-CPU cap on 32-bit x86. It's just not relevant to anybody. So the _only_ thing that matters is speed and to a secondary degree size.

On x86-64, things are slightly different, and we would want to have at least the _capability_ to do 16 bits. So there might be a (somewhat weak) argument in favor of trying to share code.

But even then, size and performance are really the only things that matter, and if the 8/16-bit version is no slower, then I'd pick that by default, and suggest the 16/32-bit one to be enabled by CONFIG_MAX_CPU's being >=256 (at which point you can share the code with x86 anyway, since that just becomes the <256 cpu case).

Linus

#13 lore raw
Quoted 4 lines · Linus Torvalds

There are no issues with the 255-CPU cap on 32-bit x86. It's just not relevant to anybody. So the _only_ thing that matters is speed and to a secondary degree size.

..of course, from a pure speed standpoint, the "lock dec" one seems to be the fastest, with the difference bwteen the 16-bit/32-bit "lock xadd" being comparatively totally in the noise.

Which is what I'd expect.

The difference between a 16-bit and 32-bit xadd should basically not be likely to be really measurable (ie we're likely talking about a single CPU cycle - if that - for the decode of the operand size override, and since both variants need it for _one_ of the operations, it likely ends up being about instruction scheduling noise), while the difference between a "dec" and "xadd" could be the difference between a native uop and microcoded.

[ Not that "xadd" couldn't be as fast as a "dec" in theory, but it's much
less likely to be that. It obviously has to actually write to two
targets: the register -and- memory, and that tends to require at least an extra uop.

And together with being a r-op-w memory instruction to begin with (which is generally the "most complex" normal instruction), and not a very often used instruction, the end result is that it would often tend to be handled specially somehow - either in a special decode unit, or as actual microcode. ]

So from a pure performance standpoint, xadd will likely continue to lose against dec. So the reason to choose xadd in the first place isn't "best performance", but "best performance given fairness".

And any performance difference between xadd and dec is going to be much bigger than any difference between 16/32-bit versions of xadd.

So I wouldn't get too hung up on a potential single cycle, and it's arguably more important to make the (inlined) "unlock" thing be as simple and small as possible.

Linus