Skip to contentSkip to conversation

SMP syncronization on AMD processors (broken?)

DISCUSSION [email protected] 4 participants 5 messages Oct 11, 2005 – Oct 13, 2005

lore
Share & tools
lore
#0 lore raw
Quoted 22 lines

The whole story started when we wrote the following code:

void XXX(void)

{
	/* ints disabled */
restart:
	spin_lock(&lock);
	do_something();
	if (!flag)
		need_restart = 1;
	spin_unlock(&lock);
	if (need_restart)
		goto restart;	<<<< LOOPS 4EVER ON AMD!!!
}

void YYY(void)

{
	spin_lock(&lock);	<<<< SPINS 4EVER ON AMD!!!
	flag = 1;
	spin_unlock(&lock);
}
Quoted 3 lines

function XXX() starts on CPU0 and begins to loop since flag is not set, then CPU1 calls function YYY() and it turns out that it can't take the lock any arbitrary time.

The right thing to do here is to wait for the flag to be set *outside* the lock, and then re-validate inside the lock:

void XXX(void)

{
	/* ints disabled */
restart:
	spin_lock(&lock);
	do_something();
	if (!flag)
		need_restart = 1;
	spin_unlock(&lock);
	if (need_restart) {
		while (!flag)
			cpu_relax();
		goto restart;
	}
}

This way, XXX() keeps the lock dropped for as long as it takes for YYY() to notice and grab it.

However, I realize that this is of course a simplified case of some real code, where even *finding* the flag requires the spin lock.

The generic solution is to have a global "progress" counter, which records "I made progress toward setting flag", that XXX() can busy-loop on:

int progress;

void XXX(void)

{
	int old_progress;
	/* ints disabled */
restart:
	spin_lock(&lock);
	do_something();
	if (!flag) {
		old_progress = progress;
		need_restart = 1;
	}
	spin_unlock(&lock);
	if (need_restart) {
		while (progress == old_progress)
			cpu_relax();
		goto restart;
	}
}

void YYY(void)

{
	spin_lock(&lock);
	flag = 1;
	progress++;
	spin_unlock(&lock);
}

It may be that in your data structure, there is one or a series of fields that already exist that you can use for the purpose. The goal is to merely detect *change*, so you can reacquire the lock and test definitively. It's okay to read freed memory while doing this, as long as you can be sure that:
- The memory read won't oops the kernel, and
- You don't end up depending on the value of the freed memory to get you out of the stall.

#1 lore raw
Quoted 2 lines · [email protected] wrote:

The right thing to do here is to wait for the flag to be set *outside* the lock, and then re-validate inside the lock:

This may work on some processors, but on others the read of "progress" in XXX, or the write in YYY may require arch-specific code to force the update out to other cpus.

Alternately, explicitly atomic operations should suffice, but a simple increment is probably not enough for portable code.

Chris

#2 lore raw
Quoted 6 lines

This may work on some processors, but on others the read of "progress" in XXX, or the write in YYY may require arch-specific code to force the update out to other cpus.

Alternately, explicitly atomic operations should suffice, but a simple increment is probably not enough for portable code.

Er.. you mean, the pre-incremented value could be cached *indefinitely* by XXX? That seems odd...

I can see an arch hook (memory barrier sort of thuing) to push it out a bit faster, but are there architecures on which noticing the increment could be delayed indefinitely?

In particular, that same hook would already be used by the spin lock release sequence (to ensure that someone else notices the lock is now available), and unless it's address-specific, it would do for the "progress" counter as well.

#3 lore raw
Quoted 9 lines · On Oct 11, 2005, at 22:39:50, [email protected] wrote:
Quoted 3 lines

This may work on some processors, but on others the read of "progress" in XXX, or the write in YYY may require arch-specific code to force the update out to other cpus.

Alternately, explicitly atomic operations should suffice, but a simple increment is probably not enough for portable code.

Er.. you mean, the pre-incremented value could be cached *indefinitely* by XXX? That seems odd...

I can see an arch hook (memory barrier sort of thuing) to push it out a bit faster, but are there architecures on which noticing the increment could be delayed indefinitely?

In particular, that same hook would already be used by the spin lock release sequence (to ensure that someone else notices the lock is now available), and unless it's address-specific, it would do for the "progress" counter as well.

Umm, IIRC, some architectures (don't remember which ones, but I'd guess it's the big 512-way boxen) have cache-line-and-memory models such that a cacheline may remain out-of-date indefinitely unless the CPU with the update runs a "cache-line flush" instruction or the CPU who wants an update requests one with an exclusive cacheline lock or similar. On such a system, the only way to ensure safe distribution of data between CPUs is to make sure it's in the same cacheline as the spinlock (and document that fact) or use special instructions to verify coherency.

Cheers,
Kyle Moffett

--
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.
-- Brian Kernighan

#4 lore raw
In reply to [email protected]

Thanks a lot for the interesting idea provided below. I will try to implement it.

Kirill

Quoted 93 lines
Quoted 15 lines

The whole story started when we wrote the following code:

void XXX(void)

{
	/* ints disabled */
restart:
	spin_lock(&lock);
	do_something();
	if (!flag)
		need_restart = 1;
	spin_unlock(&lock);
	if (need_restart)
		goto restart;	<<<< LOOPS 4EVER ON AMD!!!
}
Quoted 8 lines

void YYY(void)

{
	spin_lock(&lock);	<<<< SPINS 4EVER ON AMD!!!
	flag = 1;
	spin_unlock(&lock);
}

function XXX() starts on CPU0 and begins to loop since flag is not set, then CPU1 calls function YYY() and it turns out that it can't take the lock any arbitrary time.

The right thing to do here is to wait for the flag to be set *outside* the lock, and then re-validate inside the lock:

void XXX(void)

{
	/* ints disabled */
restart:
	spin_lock(&lock);
	do_something();
	if (!flag)
		need_restart = 1;
	spin_unlock(&lock);
	if (need_restart) {
		while (!flag)
			cpu_relax();
		goto restart;
	}
}

This way, XXX() keeps the lock dropped for as long as it takes for YYY() to notice and grab it.

However, I realize that this is of course a simplified case of some real code, where even *finding* the flag requires the spin lock.

The generic solution is to have a global "progress" counter, which records "I made progress toward setting flag", that XXX() can busy-loop on:

int progress;

void XXX(void)

{
	int old_progress;
	/* ints disabled */
restart:
	spin_lock(&lock);
	do_something();
	if (!flag) {
		old_progress = progress;
		need_restart = 1;
	}
	spin_unlock(&lock);
	if (need_restart) {
		while (progress == old_progress)
			cpu_relax();
		goto restart;
	}
}

void YYY(void)

{
	spin_lock(&lock);
	flag = 1;
	progress++;
	spin_unlock(&lock);
}

It may be that in your data structure, there is one or a series of fields that already exist that you can use for the purpose. The goal is to merely detect *change*, so you can reacquire the lock and test definitively. It's okay to read freed memory while doing this, as long as you can be sure that:
- The memory read won't oops the kernel, and
- You don't end up depending on the value of the freed memory to get you out of the stall.