Atomic Update of Data Structures, Stq | Compaq ECQD2KCTE guide

This load-locked/store-conditional paradigm may be used whenever an atomic update of a shared aligned quadword is desired, including getting the effect of atomic byte writes.

5.5.3 Atomic Update of Data Structures

Before accessing shared writable data structures (those that are not a single aligned longword or quadword), the programmer can acquire control of the data structure by using an atomic update to set a software lock variable. Such a software lock can be cleared with an ordinary store instruction.

A software-critical section, therefore, may look like the sequence:

stq_c_loop:
spin_loop:
LDQ	R1,lock_variable	; This optional spin-loop code
BLBS R1,already_set		; should be used unless the
		; lock is known to be low-contention.
LDQ_L R1,lock_variable		; \
BLBS R1,already_set		;	\
OR	R1,#1,R2	;	> Set lock bit
STQ_C R2,lock_variable		;	/
BEQ	R2,stq_c_fail	; /

MB

<critical section: updates various data structures>

MB		; Second MB
STQ	R31,lock_variable	; Clear lock bit
:
:
already_set:
<code to block or reschedule or test for too many iterations>
BR	spin_loop
stq_c_fail:
<code to test for too many iterations>
BR	stq_c_loop

This code has a number of subtleties:

•If the lock_variable is already set, the spin loop is done without doing any stores. This avoidance of stores improves memory subsystem performance and avoids the deadlock described below. The loop uses an ordinary load. This code sequence is preferred unless the lock is known to be low-contention, because the sequence increases the probability that the LDQ_L hits in the cache and the LDQ_L/STQ_C sequence complete quickly and successfully.

•If the lock_variable is actually being changed from 0 to 1, and the STQ_C fails (due to an interrupt, or because another processor simultaneously changed lock_variable), the entire process starts over by reading the lock_variable again.

•Only the fall-through path of the BLBS instructions does a STx_C; some implementa- tions may not allow a successful STx_C after a branch-taken.

•Only register-to-register operate instructions are used to do the modify.

System Architecture and Programming Implications 5–7

Image 219

Compaq ECQD2KCTE manual Atomic Update of Data Structures, Stq

Contents

Alpha Architecture Handbook October Table of Contents Instruction Formats Page 10.19 Integer Register to Floating-Point Register Move System Architecture and Programming Implications Digital Unix Ieee Floating-Point Conformance Index Figures Tables Xiii Xiv Preface Page Alpha Is Designed for Very High-Speed Implementations ChapterAlpha Approach to Risc Architecture Alpha Is a True 64-Bit Architecture PALcode Alpha’s Very Flexible Privileged Software Library Alpha Approach to Byte ManipulationAlpha Approach to Multiprocessor Shared Memory Alpha Instructions Include Hints for Achieving Higher Speed Alpha and Programming Languages Data Format Overview Instruction Format Overview Instruction OverviewPALcode Instructions Branch Instructions Load/Store InstructionsInteger Operate Instructions Instruction Set Characteristics Terminology and ConventionsFloating-Point Operate Instructions Numbering Security HolesUnpredictable and Undefined Ranges and Extents Aligned and UnalignedUnaligned Ignore IGN Must Be Zero MBZRead As Zero RAZ Should Be Zero SBZPage Word AddressingData Types Byte Quadword Longword Ffloating VAX Floating-Point Formats Gfloating Ffloating Load Exponent Mapping Mapf Dfloating Gfloating Register Format Ieee Floating-Point Formats Sfloating Load Exponent Mapping Maps Memory Register SFloating 13 Tfloating Datum Tfloating XFloating 14 Tfloating Register Format XFloating Big-Endian Formats 15 Xfloating Datum 17 Xfloating Big-Endian Datum Longword Integer Format in Floating-Point Unit Data Types with No Hardware Support Quadword Integer Format in Floating-Point Unit 23 Little-Endian Byte Addressing Big-Endian Addressing Support 14Alpha Architecture Handbook Implementation note Alpha RegistersProgram Counter Integer Registers Lock Registers Floating-Point Registers Memory Prefetch Registers NotationProcessor Cycle Counter PCC Register Optional Registers Expression Operand Notation Meaning Operand NotationOperand Notation Meaning Operand Value Notation Meaning Operand Name Notation Operand Access Type NotationOperand Access Type Notation Meaning Instruction Operand Notation Operators Meaning OperatorsOperand Data Type Notation Operand Data Type Notation Meaning Bit concatenation Case DIVLoadlocked LTU NotPhysicaladdress Priorityencode XOR Instruction FormatsNotation Conventions Software Note Memory Format Instructions with a Function Code Memory Instruction Format Branch Instruction Format Operate Instruction FormatMemory Format Jump Instructions Floating-Point Operate Instruction Format Floating-Point Operate Instruction Format PALcode Instruction Format Floating-Point Convert InstructionsFloating-Point/Integer Register Moves PALcode Instruction Format Page Instruction Type Section Instruction Set Overview Floating-Point Subsets Subsetting Rules Software Emulation Rules Opcode QualifiersOpcode Qualifiers Meaning Memory Integer Load/Store Instructions Mnemonic Operation Memory Integer Load/Store Instructions Load Address LDL Load Memory Data into Integer Register Implementation Notes Load Unaligned Memory Data into Integer Register Load Memory Data into Integer Register Locked 10Alpha Architecture Handbook Implementation Notes Store Integer Register Data into Memory Conditional Stqc BEQ Hardware/Software Implementation Note Store Integer Register Data into Memory 16Alpha Architecture Handbook Store Unaligned Integer Register Data into Memory Control Instructions Summary Mnemonic Operation Control Instructions JSR BNEBSR JMP Conditional Branch Unconditional Branch Jumps Encoding Meaning Integer Arithmetic Instructions Count instruction CIX extension implementation noteInteger Arithmetic Instructions Summary Mnemonic Operation Addl Longword Add Scaled Longword Add S4ADDLS8ADDL Addq Quadword Add Scaled Quadword Add S4ADDQS8ADDQ Integer Signed Compare Integer Unsigned Compare Count Leading Zero Count Population Count Trailing Zero Mull Longword Multiply Mulq Quadword Multiply Unsigned Quadword Multiply High Subl Longword Subtract Scaled Longword Subtract S4SUBLS8SUBL Subq Quadword Subtract Scaled Quadword Subtract S4SUBQS8SUBQ Logical and Shift Instructions Summary Mnemonic Operation Logical and Shift Instructions Logical Functions Conditional Move Integer Is exactly equivalent to Shift Logical Shift Arithmetic Instruction Meaning Described in Section Byte Manipulation Instructions Mskbl InswhInslh Insqh BEQ Loop Compare Byte To compare two character strings for greater/equal/less Extract Byte Ldqu Optimized examples Big-endian examples Byte Insert 56Alpha Architecture Handbook Byte Mask Insqh Inswh Sign Extend Zero Bytes Subsets and Faults Floating-Point InstructionsSingle-Precision Operations Alpha finite number Definitions Non-finite number DenormalDirty zero Infinity Meaning Finite EncodingsTrue zero Sign Exponent Fraction Vax Rounding Modes VAX Rounding ModesIeee Rounding Modes VAX-Format Arithmetic with Precise Exceptions VAX Rounding Mode Instruction NotationIeee Rounding Mode Instruction Notation Computational Models High-Performance VAX-Format Arithmetic IEEE-Compliant ArithmeticIEEE-Compliant Arithmetic Without Inexact Exception Trapping Modes High-Performance IEEE-Format ArithmeticVAX Trapping Modes When /U or /V mode is specified Ieee Trapping Modes VAX Trapping Modes Summary Trap Mode Notation Meaning SUI Summary of Ieee Trapping Modes Trap Mode Notation Meaning SVI Arithmetic Trap Completion Trap Shadow Length Rules Page Invalid Operation INV Arithmetic Trap Overflow OVF Arithmetic Trap Division by Zero DZE Arithmetic Trap Integer Overflow IOV Arithmetic Trap Ieee Floating-Point Trap Disable BitsUnderflow UNF Arithmetic Trap Inexact Result INE Arithmetic Trap Ieee Denormal Control Bits Floating-Point Control Register Fpcr Floating-Point Control Register Fpcr Format Ieee Rounding Mode SelectedPage Accessing the Fpcr Default Values of the Fpcr Saving and Restoring the FpcrSoftware Notes Floating-Point Instruction Function Field Floating-Point Instruction Function Field Format Contents Meaning for Opcodes 1616 FNC ITOFS/ITOFTSQRTS/SQRTT Unpredictable Conversion of NaN and Infinity Values Ieee Standard Copying NaN Values Generating NaN ValuesPropagating NaN Values Memory Format Floating-Point Instructions Load Ffloating Load Gfloating Load Sfloating Load Tfloating Store Ffloating Store Gfloating Store Sfloating Store Tfloating Branch Format Floating-Point Instructions FBxx Fa.rq,disp.al Branch format Page Floating-Point Operate Format Instructions Ieee AddfAddg Adds Mult MulfMulg Muls Copy Sign Convert Integer to Integer Floating-Point Conditional Move Fcmovne F3,F2,F1 Move from/to Floating-Point Control Register VAX Floating Add Ieee Floating Add Cmpglt VAX Floating CompareCmpgeq Cmpgle Cmptlt Ieee Floating CompareCmpteq Cmptle Convert VAX Floating to Integer Convert Integer to VAX Floating Convert VAX Floating to VAX Floating Convert Ieee Floating to Integer Convert Integer to Ieee Floating Convert Ieee SFloating to Ieee TFloating Convert Ieee TFloating to Ieee SFloating VAX Floating Divide Ieee Floating Divide Floating-Point Register to Integer Register Move Integer Register to Floating-Point Register Move Itofs is exactly equivalent to the sequence VAX Floating Multiply Ieee Floating Multiply VAX Floating Square Root Ieee Floating Square Root VAX Floating Subtract Ieee Floating Subtract 17 Miscellaneous Instructions Summary Mnemonic Operation Miscellaneous Instructions Architecture Mask 134Alpha Architecture Handbook Call Privileged Architecture Library Evict Data Cache Block Implementation Note Exception Barrier Prefetch Data 140Alpha Architecture Handbook Implementation Version Memory Barrier Read Processor Cycle Counter Trap Barrier Write Hint Implementation Note Write Memory Barrier Processor Processor j 18 VAX Compatibility Instructions Summary Mnemonic Operation VAX Compatibility Instructions VAX Compatibility Instructions Mnemonic Operation Multimedia Graphics and Video Support Byte and Word Minimum and Maximum Instruction mnemonics Pixel Error Pack Bytes Unpack Bytes Physical Address Space Characteristics Coherency of Memory AccessIntroduction Software/Hardware Note Granularity of Memory Access Memory-Like and Non-Memory-Like Behavior Width of Memory Access Translation Buffers and Virtual Caches Caches and Write BuffersHardware/Software Coordination Note Page Atomic Update of a Single Datum Data SharingAtomic Change of a Single Datum STQ Atomic Update of Data Structures 8Alpha Architecture Handbook Ordering Considerations for Shared Data Structures Alpha Shared Memory Model Read/Write Ordering Implementation Note Architectural Definition of Processor Issue Sequence Definition of Processor Issue ConstraintsDefinition of Before and After 1st↓ 2nd → PiIn=4y,b PiRny,b PiWny,b PiMB PiIMB Processor Issue Constraints Definition of Location Access Constraints Definition of VisibilityDefinition of Storage Definition of Dependence Constraint Definition of Load-Locked and Store-Conditional PiPj Litmus TestsTimeliness Litmus Test 1 Impossible Sequence Litmus Test 3 Impossible Sequence Litmus Test 2 Impossible Sequence Litmus Test 4 Sequence Okay Litmus Test 5 Sequence OkayLitmus Test 6 Sequence Okay Litmus Test 8 Impossible Sequence Litmus Test 7 Impossible Sequence Litmus Test 9 Impossible Sequence Litmus Test 10 Sequence OkayLitmus Test 11 Impossible Sequence Single Processor Instruction Stream Implied BarriersImplications for Software Single Processor Data Stream See Footnote 1 on First Processor Second Processor Multiprocessor Context SwitchPage Multiprocessor Send/Receive Interrupt Implications for Memory Mapped I/O Multiple Processors Writing to a Single I/O Device Implications for Hardware Dictable Arithmetic Traps PALcode Instructions and Functions PALcode Special Functions Required for PALcode PALcode Environment PALcode Effects on System Code PALcode Replacement PALcode Instructions that Require Recognition Mnemonic Name Required PALcode Instructions IMB Required PALcode Instructions Mnemonic Type OperationDraina Halt Callpal Draina Drain Aborts Callpal Halt Halt Callpal IMB Instruction Memory Barrier Console Subsystem Overview Page Input/Output Overview Page Unprivileged OpenVMS Alpha PALcode OpenVMS Alpha Chmu ChmeChmk Chms Insqhiqr InsqhilInsqhilr Insqhiq Insquel InsqtilrInsqtiq Insqtiqr Remqhil RdpsReadunq REI Remqtiq RemqhiqrRemqtil Remqtilr Swasten RemquelRemqueq Rscc Mfpr Privileged OpenVMS Alpha PalcodeCflush Ldqp Stqp SwpctxWtint Page Mnemonic Operation and Description Unprivileged Digital Unix PALcode Privileged Digital Unix PALcode 10-3 10-4Alpha Architecture Handbook Unprivileged Windows NT Alpha PALcode Instruction Summary Unprivileged Windows NT Alpha PALcode Privileged Windows NT Alpha PALcode 11-3 11-4Alpha Architecture Handbook 11-5 Page Hardware-Software Compact Appendix a Instruction-Stream Considerations Instruction AlignmentBranch Prediction and Minimizing Branch-Taken Factor Figure A-1 Branch-Format BSR and BR Opcodes Data Alignment Factor Data-Stream ConsiderationsImproving I-Stream Density Factor Instruction Scheduling Factor Shared Data in Multiple Processors Factor Avoiding Cache/TB Conflicts Factor Figure A-3 Bad Allocation in Cache Prefetching Factor Sequential Read/Write Factor Code Sequences Aligned Byte/Word Within Register Memory Accesses Division Byte Swap Stylized Code Forms4.1 NOP Load Literal Clear a Register Booleans Register-to-Register MoveNegate 4.6 not Pseudo-Operations Stylized Code Forms Exceptions and Trap Barriers Software Considerations A-15 Timing Considerations Atomic Sequences Alpha Choices for Ieee Options Appendix B 2Alpha Architecture Handbook Alpha Support for OS Completion Handlers Figure B-1 Ieee Floating-Point Control FPC Quadword Ieee Floating-Point Control FPC QuadwordPage Mapping to Ieee Standard Figure B-2 Ieee Trap Handling Behavior Table B-2 Ieee Floating-Point Trap Handling User Hardware1 Completion Signal Alpha Instructions Code Handler MULx Output Exceptions Cmptlt Cmptle Input Exceptions CVTff Output Exceptions SQRTx Output Exceptions Inexact Division by ZeroOverflow Underflow Common Architecture Instruction Summary Appendix C Table C-2 Common Architecture Instructions ADDL/VADDQ/V 15.0AF Convert Gfloating to quadword MULQ/V MULL/V SUBQ/V SUBL/V Table C-3 Ieee Floating-Point Instruction Function Codes Ieee Floating-Point Instructions Programming Note VAX Floating-Point Instructions Opcode Summary Independent Floating-Point Instructions Table C-6 Opcode Summary Table C-7 Key to Opcode Summary Symbol Meaning Table C-8 Common Architecture Opcodes in Numerical Order Common Architecture Opcodes in Numerical Order Instruction Summary C-11 Addt Instruction Summary C-13 OpenVMS Alpha PALcode Instruction Summary Mfpripl MfprasnMfpresp Mfprfen Digital Unix PALcode Instruction Summary Table C-12 Digital Unix Privileged PALcode InstructionsMnemonic Opcode Description Table C-14 Windows NT Alpha Privileged PALcode instructions Windows NT Alpha Instruction Summary OpenVMS Alpha PALcode Opcodes in Numerical OrderTable C-15 PALcode Opcodes in Numerical Order Windows NT Wtint 00.003F 00.0063 Table C-17 Opcodes Reserved for PALcode Mnemonic Required PALcode OpcodesOpcodes Reserved to PALcode Table C-16 Required PALcode Opcodes Mnemonic Type OPC01 OPC02 OPC03 OPC04 OPC05 OPC06 OPC07 Opcodes Reserved to CompaqUnused Function Code Behavior Table C-18 Opcodes Reserved for Compaq Mnemonic Table C-19 Ascii Character Set Hex Code Ascii Character Set EV3 Appendix DProcessor Type Assignments Table D-1 Processor Type Assignments Major Type Minor Type PALcode Variation Assignments Digital Unix Architecture Mask and Implementation ValuesTable D-3 Amask Bit Assignments Bit Meaning Table D-4 Implver Value Assignments MeaningPage Waivers Appendix E DECchip 21264 LDxL/STxC with WH64 Violation DECchip 21064/21066/21068 Performance Monitoring Implementation-Specific Functionality For the OpenVMS Alpha Operating System Functions and Arguments for the DECchip 21064/21066/21068 Disable performance monitoring = PCMUX1 Select desired events muxctlSelect performance monitoring options = PCMUX0 Value Description PC1 PC0 Performance Monitor Interrupt Mechanism DECchip 21164/21164PC Performance Monitoring Windows NT Alpha Functions and Argument Input Contents Register Bits Meaning CTR0 CTR1PCSEL0 PCSEL2 OpenVMS Alpha and Digital Unix Functions and ArgumentsModeselect PCSEL1 Select desired events Muxselect Disable performance monitoring do not reset counters Read the counters Select interrupt frequencies Operate on counter MBZ PCSEL0 MBZMBZ PCSEL1 Counters Operate Under These Modes When Bits Set Bits MeaningS U P 6310 Table E-13 21164/21164PC Counter 1 PCSEL1 Event Selection Table E-14 21164/21164PC Counter 2 PCSEL2 Event Selection Table E-15 21164 CBOX1 Event Selection Value MeaningTable E-16 21164 CBOX2 Event Selection Table E-18 21164PC PM1MUX Event Selection Table E-17 21164PC PM0MUX Event Selection 3 21264 Performance Monitoring PCTR1 SEXTPCTR0CTL47PCTR0 IERCMPCEN0 Bit value Meaning SL1 Select logging options Enable and write selected counters R17/a1 Bits Meaning Table E-26 21264 Enable and Write Counters for OpenVMS Alpha Page Index Index-2 Index-3 Index-4 Index-5 Index-6 Index-7 Index-8 Index-9 Index-10 Index-11 Index-12 Index-13