[parisc-linux] xchg implementation

[parisc-linux] xchg implementation

[Matthew Wilcox]

As you can read below, I've been thinking about the implementation
of xchg again.  For those who are unfamiliar with this, it is used to
atomically swap the contents of a register with a location in memory.
It is defined to be atomic wrt other CPUs and interrupts on the same CPU.
PA-RISC's only atomic operation is load-and-zero.  A large proportion
of the cases where xchg is used, it is with zero, and we can use the
load-and-zero instruction.

This is a uniprocessor optimisation of the xchg() case where it's _not_
exchanging with zero.  What I need is a spare CR register.  As far as I
can see from the comments, CR28-30 are currently reserved; leaving CRs
24, 25 and 31 available.  Unless someone's using one of them without
documenting it somewhere...?  That really does need to be written down
somewhere.

----- Forwarded message from Matthew Wilcox <Matthew.Wilcox@genedata.com> -----

Date: Sun, 31 Oct 1999 19:02:34 +0100
From: Matthew Wilcox <Matthew.Wilcox@genedata.com>
To: Ralf Baechle <ralf@uni-koblenz.de>
Cc: Matthew Wilcox <Matthew.Wilcox@genedata.com>,
        Keith Owens <kaos@ocs.com.au>, linux-kernel@vger.rutgers.edu
Subject: Re: FD array expansion problem
X-Mailer: Mutt 0.95.3i
In-Reply-To: <19991031010842.H15510@uni-koblenz.de>; from Ralf Baechle on Sun, Oct 31, 1999 at 01:08:42AM +0200

On Sun, Oct 31, 1999 at 01:08:42AM +0200, Ralf Baechle wrote:
> On Sat, Oct 30, 1999 at 03:42:17PM +0200, Matthew Wilcox wrote:
> 
> > We don't have ll/sc instructions or compare-and-swap on pa-risc.
> > I'd really like to be able to do this without disabling interrupts,
> > but I don't think there's a way.
> 
> Actually there is a neat way for uniprocessor MIPSes to implement this.
> The two registers k0 and k1 are reserved for use of the kernel, for example
> in interrupt processing.  All exception handles will destroy the content
> of these registers and set it to a value != NULL which allows to implement
> an atomic increment for uniprocessors like:
> 
> 	move	k0, zero
> 1:	lw	old, addr
> 	sw	new, addr
> 	bnez	k0, 1b
> 
> Dunno if that'd hold for HPPA as well.

I don't think that works.  Look:

main code	interrupt
set k0 to zero
load A from addr
store B at addr
		set k0 to zero
		load B from addr
		store C at addr
		return (i assume this makes k0 non-zero)
k0 is non-zero, so loop again
load C from addr
store B at addr

And you've lost the original A.  I came up with a similar scheme while
taking a long walk today (many people seem to prefer the shower for their
good ideas.  I find Japanese stroll gardens are ideal, and a nice long
walk is almost as good.)

The idea is to flag whether we're in the middle of an xchg operation in
a register such as k0, then have the interrupt handler's exit routine fix
it up:

move k0, one
lw A, addr
sw B. addr
move k0, zero

would then be the typical non-interrupted case.

The modified interrupt code looks like:

int xchging = (k0 == 1);

... normal irq code ...

if (!xchging)
	return;
if (instruction we will return to is a store)
	return to addr - 4;
return;

This should work, and have a minimal cost per interrupt.
Now to find out whether we have a suitable register on PA-RISC..

-- 
Matthew Wilcox <willy@bofh.ai>
"Windows and MacOS are products, contrived by engineers in the service of
specific companies. Unix, by contrast, is not so much a product as it is a
painstakingly compiled oral history of the hacker subculture." - N Stephenson

----- End forwarded message -----

-- 
Matthew Wilcox <willy@bofh.ai>
"Windows and MacOS are products, contrived by engineers in the service of
specific companies. Unix, by contrast, is not so much a product as it is a
painstakingly compiled oral history of the hacker subculture." - N Stephenson

Re: [parisc-linux] xchg implementation

[LaMont Jones]

> This is a uniprocessor optimisation of the xchg() case where it's _not_
> exchanging with zero.  What I need is a spare CR register.  As far as I
> can see from the comments, CR28-30 are currently reserved; leaving CRs
> 24, 25 and 31 available.  Unless someone's using one of them without
> documenting it somewhere...?  That really does need to be written down
> somewhere.

IIRC, CR24 and 25 are readable from user space (not writable), and can be
quite useful for thread specific data, thread id, etc...  It might do to
leave them available for such a use.

lamont

Re: [parisc-linux] xchg implementation

[Matthew Wilcox]

On Mon, Nov 01, 1999 at 02:03:05PM -0700, LaMont Jones wrote:
> > This is a uniprocessor optimisation of the xchg() case where it's _not_
> > exchanging with zero.  What I need is a spare CR register.  As far as I
> > can see from the comments, CR28-30 are currently reserved; leaving CRs
> > 24, 25 and 31 available.  Unless someone's using one of them without
> > documenting it somewhere...?  That really does need to be written down
> > somewhere.
> 
> IIRC, CR24 and 25 are readable from user space (not writable), and can be
> quite useful for thread specific data, thread id, etc...  It might do to
> leave them available for such a use.

You're thinking of CR26 and 27 (ref: Kane's PA-RISC 2.0 Architecture,
page 2-17).  CR31 _is_ used, I didn't read carefully enough:

$ find arch/parisc/ -name \*.[chS] |xargs grep ctl |grep 31
arch/parisc/kernel/interruption.S:      mtctl           29,31
arch/parisc/kernel/interruption.S:      mtctl           29,31
arch/parisc/kernel/interruption.S:      mtctl           29,31
arch/parisc/kernel/syscall.S:   mfctl   31, %r27                        ; get the kernel dp

cr26,27 are used, but only in a debug macro in head.S.

-- 
Matthew Wilcox <willy@bofh.ai>
"Windows and MacOS are products, contrived by engineers in the service of
specific companies. Unix, by contrast, is not so much a product as it is a
painstakingly compiled oral history of the hacker subculture." - N Stephenson

Re: [parisc-linux] xchg implementation

[LaMont Jones]

> > IIRC, CR24 and 25 are readable from user space (not writable), and can be
> > quite useful for thread specific data, thread id, etc...  It might do to
> > leave them available for such a use.
> You're thinking of CR26 and 27 (ref: Kane's PA-RISC 2.0 Architecture,
> page 2-17).  CR31 _is_ used, I didn't read carefully enough:

And the worst of it is that I knew that.  Sigh...

thanks for the clarification,
lamont

Re: [parisc-linux] xchg implementation

[Philipp Rumpf]

> You're thinking of CR26 and 27 (ref: Kane's PA-RISC 2.0 Architecture,
> page 2-17).  CR31 _is_ used, I didn't read carefully enough:

Summary of current temporary register usage:


register	today		soon
CR24		unused		what CR26 is today (I thought CR2[45] were readable
CR25		unused		what CR25 is today  from userspace. stupid prumpf)
CR26		used in head.S	unused
CR27		used in head.S	unused
CR28		temporary usage in interruption handlers [GR1  saved here]
CR29		temporary usage in interruption handlers [arg0 (for the interruption
			handler, NOT GR26) saved here]
CR30	 	current, 0 if in kernel mode (this might not work for syscalls yet)
CR31		temporary usage in interruption handlers [GR29 saved here]

I think using three temporary registers for interruption handlers is okay.

The current/0 register is quite helpful and I'd like to keep it the way it is.

One register to add is a pointer to our PGD so our TLB insertion handler can be

mtctl		 1, TR_INTR_GR1
mtctl		29, TR_INTR_GR29
mtctl		 2, TR_INTR_ARG0	/* we don't have an argument */
mfctl		TR_PGD,  1
mfctl		IOR, 29
extru		29,  9, 10, 2		/* PGD offset */
ldwx,s		 2( 1),  1 		/* load word scaled(?) (so at address GR1 + 4*GR2) */
bb,<,n		 1, PG_PRESENT_BIT, major_page_fault	/* major page fault if pte invalid */
extru		29, 19, 10, 2		/* PTE offset */
ldwx,s		 2( 1),  1		/* load PTE */
/* do the PTE translation here */
/* do idtlba, idtlbp, iitlba, iitlbp, idtlbt, iitlbt, idtlbaf, idtlbpf, iitlbaf, or iitlbpf
 * depending on CPU / fault type. */

I still haven't found any magic tricks to speed up xchg (the way I understand it
hashing the address and indexing an array of spinlocks for the atomic operations
probably is the best thing to do for SMP, for UP I think we have to do an irqsave/
irqrestore).  Should there be any I am too stupid to see I think it's no problem
using a temporary register for it.

That leaves one or two registers for future use (our FP emulator for some of the
CPUs with half an FPU (PA7100LC) might need one to point to the FP registers or
something, don't know whether syscalls could use one too), and the two we can read
out of userspace.  What does HP/UX use them for ?

	Philipp Rumpf