Skip to content

Commit 3e3a027

Browse files
schuayV8 LUCI CQ
schuay
authored and
V8 LUCI CQ
committed
[regexp] Fix stack growth for global regexps
Irregexp reentrancy (crrev.com/c/3162604) introduced a bug for global regexp execution in which each iteration would use a new stack region (i.e. we forgot to pop the regexp stack pointer when starting a new iteration). This CL fixes that by popping the stack pointer on the loop backedge. At a high level: - Initialize the backtrack_stackpointer earlier and avoid clobbering it by setup code. - Pop it on the loop backedge. - Slightly refactor Push/Pop operations to avoid unneeded memory accesses. Bug: v8:11382 Change-Id: Ibad6235767e110089a2b346034f923590b286a05 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/3194251 Reviewed-by: Patrick Thier <[email protected]> Commit-Queue: Jakob Gruber <[email protected]> Cr-Commit-Position: refs/heads/main@{#77158}
1 parent d6c0105 commit 3e3a027

8 files changed

Lines changed: 283 additions & 231 deletions

‎src/regexp/arm/regexp-macro-assembler-arm.cc‎

Lines changed: 67 additions & 57 deletions
Original file line numberDiff line numberDiff line change
@@ -628,26 +628,26 @@ void RegExpMacroAssemblerARM::StoreRegExpStackPointerToMemory(
628628
__ str(src, MemOperand(scratch));
629629
}
630630

631-
void RegExpMacroAssemblerARM::PushRegExpBasePointer(Register scratch1,
632-
Register scratch2) {
633-
LoadRegExpStackPointerFromMemory(scratch1);
631+
void RegExpMacroAssemblerARM::PushRegExpBasePointer(Register stack_pointer,
632+
Register scratch) {
634633
ExternalReference ref =
635634
ExternalReference::address_of_regexp_stack_memory_top_address(isolate());
636-
__ mov(scratch2, Operand(ref));
637-
__ ldr(scratch2, MemOperand(scratch2));
638-
__ sub(scratch2, scratch1, scratch2);
639-
__ str(scratch2, MemOperand(frame_pointer(), kRegExpStackBasePointer));
635+
__ mov(scratch, Operand(ref));
636+
__ ldr(scratch, MemOperand(scratch));
637+
__ sub(scratch, stack_pointer, scratch);
638+
__ str(scratch, MemOperand(frame_pointer(), kRegExpStackBasePointer));
640639
}
641640

642-
void RegExpMacroAssemblerARM::PopRegExpBasePointer(Register scratch1,
643-
Register scratch2) {
641+
void RegExpMacroAssemblerARM::PopRegExpBasePointer(Register stack_pointer_out,
642+
Register scratch) {
644643
ExternalReference ref =
645644
ExternalReference::address_of_regexp_stack_memory_top_address(isolate());
646-
__ ldr(scratch1, MemOperand(frame_pointer(), kRegExpStackBasePointer));
647-
__ mov(scratch2, Operand(ref));
648-
__ ldr(scratch2, MemOperand(scratch2));
649-
__ add(scratch1, scratch1, scratch2);
650-
StoreRegExpStackPointerToMemory(scratch1, scratch2);
645+
__ ldr(stack_pointer_out,
646+
MemOperand(frame_pointer(), kRegExpStackBasePointer));
647+
__ mov(scratch, Operand(ref));
648+
__ ldr(scratch, MemOperand(scratch));
649+
__ add(stack_pointer_out, stack_pointer_out, scratch);
650+
StoreRegExpStackPointerToMemory(stack_pointer_out, scratch);
651651
}
652652

653653
Handle<HeapObject> RegExpMacroAssemblerARM::GetCode(Handle<String> source) {
@@ -688,37 +688,43 @@ Handle<HeapObject> RegExpMacroAssemblerARM::GetCode(Handle<String> source) {
688688
kBacktrackCount - kSystemPointerSize);
689689
__ push(r0); // The regexp stack base ptr.
690690

691+
// Initialize backtrack stack pointer. It must not be clobbered from here on.
692+
// Note the backtrack_stackpointer is callee-saved.
693+
STATIC_ASSERT(backtrack_stackpointer() == r8);
694+
LoadRegExpStackPointerFromMemory(backtrack_stackpointer());
695+
691696
// Store the regexp base pointer - we'll later restore it / write it to
692697
// memory when returning from this irregexp code object.
693-
PushRegExpBasePointer(r0, r1);
694-
695-
// Check if we have space on the stack for registers.
696-
Label stack_limit_hit;
697-
Label stack_ok;
698+
PushRegExpBasePointer(backtrack_stackpointer(), r1);
699+
700+
{
701+
// Check if we have space on the stack for registers.
702+
Label stack_limit_hit, stack_ok;
703+
704+
ExternalReference stack_limit =
705+
ExternalReference::address_of_jslimit(isolate());
706+
__ mov(r0, Operand(stack_limit));
707+
__ ldr(r0, MemOperand(r0));
708+
__ sub(r0, sp, r0, SetCC);
709+
// Handle it if the stack pointer is already below the stack limit.
710+
__ b(ls, &stack_limit_hit);
711+
// Check if there is room for the variable number of registers above
712+
// the stack limit.
713+
__ cmp(r0, Operand(num_registers_ * kPointerSize));
714+
__ b(hs, &stack_ok);
715+
// Exit with OutOfMemory exception. There is not enough space on the stack
716+
// for our working registers.
717+
__ mov(r0, Operand(EXCEPTION));
718+
__ jmp(&return_r0);
698719

699-
ExternalReference stack_limit =
700-
ExternalReference::address_of_jslimit(isolate());
701-
__ mov(r0, Operand(stack_limit));
702-
__ ldr(r0, MemOperand(r0));
703-
__ sub(r0, sp, r0, SetCC);
704-
// Handle it if the stack pointer is already below the stack limit.
705-
__ b(ls, &stack_limit_hit);
706-
// Check if there is room for the variable number of registers above
707-
// the stack limit.
708-
__ cmp(r0, Operand(num_registers_ * kPointerSize));
709-
__ b(hs, &stack_ok);
710-
// Exit with OutOfMemory exception. There is not enough space on the stack
711-
// for our working registers.
712-
__ mov(r0, Operand(EXCEPTION));
713-
__ jmp(&return_r0);
714-
715-
__ bind(&stack_limit_hit);
716-
CallCheckStackGuardState();
717-
__ cmp(r0, Operand::Zero());
718-
// If returned value is non-zero, we exit with the returned value as result.
719-
__ b(ne, &return_r0);
720+
__ bind(&stack_limit_hit);
721+
CallCheckStackGuardState();
722+
__ cmp(r0, Operand::Zero());
723+
// If returned value is non-zero, we exit with the returned value as result.
724+
__ b(ne, &return_r0);
720725

721-
__ bind(&stack_ok);
726+
__ bind(&stack_ok);
727+
}
722728

723729
// Allocate space on stack for registers.
724730
__ AllocateStackSpace(num_registers_ * kPointerSize);
@@ -740,18 +746,21 @@ Handle<HeapObject> RegExpMacroAssemblerARM::GetCode(Handle<String> source) {
740746
// Initialize code pointer register
741747
__ mov(code_pointer(), Operand(masm_->CodeObject()));
742748

743-
Label load_char_start_regexp, start_regexp;
744-
// Load newline if index is at start, previous character otherwise.
745-
__ cmp(r1, Operand::Zero());
746-
__ b(ne, &load_char_start_regexp);
747-
__ mov(current_character(), Operand('\n'), LeaveCC, eq);
748-
__ jmp(&start_regexp);
749-
750-
// Global regexp restarts matching here.
751-
__ bind(&load_char_start_regexp);
752-
// Load previous char as initial value of current character register.
753-
LoadCurrentCharacterUnchecked(-1, 1);
754-
__ bind(&start_regexp);
749+
Label load_char_start_regexp;
750+
{
751+
Label start_regexp;
752+
// Load newline if index is at start, previous character otherwise.
753+
__ cmp(r1, Operand::Zero());
754+
__ b(ne, &load_char_start_regexp);
755+
__ mov(current_character(), Operand('\n'), LeaveCC, eq);
756+
__ jmp(&start_regexp);
757+
758+
// Global regexp restarts matching here.
759+
__ bind(&load_char_start_regexp);
760+
// Load previous char as initial value of current character register.
761+
LoadCurrentCharacterUnchecked(-1, 1);
762+
__ bind(&start_regexp);
763+
}
755764

756765
// Initialize on-stack registers.
757766
if (num_saved_registers_ > 0) { // Always is, if generated from a regexp.
@@ -772,9 +781,6 @@ Handle<HeapObject> RegExpMacroAssemblerARM::GetCode(Handle<String> source) {
772781
}
773782
}
774783

775-
// Initialize backtrack stack pointer.
776-
LoadRegExpStackPointerFromMemory(backtrack_stackpointer());
777-
778784
__ jmp(&start_label_);
779785

780786
// Exit code:
@@ -841,6 +847,10 @@ Handle<HeapObject> RegExpMacroAssemblerARM::GetCode(Handle<String> source) {
841847
// Prepare r0 to initialize registers with its value in the next run.
842848
__ ldr(r0, MemOperand(frame_pointer(), kStringStartMinusOne));
843849

850+
// Restore the original regexp stack pointer value (effectively, pop the
851+
// stored base pointer).
852+
PopRegExpBasePointer(backtrack_stackpointer(), r2);
853+
844854
if (global_with_zero_length_check()) {
845855
// Special case for zero-length matches.
846856
// r4: capture start index
@@ -873,7 +883,7 @@ Handle<HeapObject> RegExpMacroAssemblerARM::GetCode(Handle<String> source) {
873883
__ bind(&return_r0);
874884
// Restore the original regexp stack pointer value (effectively, pop the
875885
// stored base pointer).
876-
PopRegExpBasePointer(r1, r2);
886+
PopRegExpBasePointer(backtrack_stackpointer(), r2);
877887

878888
// Skip sp past regexp registers and local variables..
879889
__ mov(sp, frame_pointer());

‎src/regexp/arm/regexp-macro-assembler-arm.h‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -181,8 +181,8 @@ class V8_EXPORT_PRIVATE RegExpMacroAssemblerARM
181181

182182
void LoadRegExpStackPointerFromMemory(Register dst);
183183
void StoreRegExpStackPointerToMemory(Register src, Register scratch);
184-
void PushRegExpBasePointer(Register scratch1, Register scratch2);
185-
void PopRegExpBasePointer(Register scratch1, Register scratch2);
184+
void PushRegExpBasePointer(Register stack_pointer, Register scratch);
185+
void PopRegExpBasePointer(Register stack_pointer_out, Register scratch);
186186

187187
Isolate* isolate() const { return masm_->isolate(); }
188188

‎src/regexp/arm64/regexp-macro-assembler-arm64.cc‎

Lines changed: 63 additions & 52 deletions
Original file line numberDiff line numberDiff line change
@@ -710,26 +710,26 @@ void RegExpMacroAssemblerARM64::StoreRegExpStackPointerToMemory(
710710
__ Str(src, MemOperand(scratch));
711711
}
712712

713-
void RegExpMacroAssemblerARM64::PushRegExpBasePointer(Register scratch1,
714-
Register scratch2) {
715-
LoadRegExpStackPointerFromMemory(scratch1);
713+
void RegExpMacroAssemblerARM64::PushRegExpBasePointer(Register stack_pointer,
714+
Register scratch) {
716715
ExternalReference ref =
717716
ExternalReference::address_of_regexp_stack_memory_top_address(isolate());
718-
__ Mov(scratch2, ref);
719-
__ Ldr(scratch2, MemOperand(scratch2));
720-
__ Sub(scratch2, scratch1, scratch2);
721-
__ Str(scratch2, MemOperand(frame_pointer(), kRegExpStackBasePointer));
717+
__ Mov(scratch, ref);
718+
__ Ldr(scratch, MemOperand(scratch));
719+
__ Sub(scratch, stack_pointer, scratch);
720+
__ Str(scratch, MemOperand(frame_pointer(), kRegExpStackBasePointer));
722721
}
723722

724-
void RegExpMacroAssemblerARM64::PopRegExpBasePointer(Register scratch1,
725-
Register scratch2) {
723+
void RegExpMacroAssemblerARM64::PopRegExpBasePointer(Register stack_pointer_out,
724+
Register scratch) {
726725
ExternalReference ref =
727726
ExternalReference::address_of_regexp_stack_memory_top_address(isolate());
728-
__ Ldr(scratch1, MemOperand(frame_pointer(), kRegExpStackBasePointer));
729-
__ Mov(scratch2, ref);
730-
__ Ldr(scratch2, MemOperand(scratch2));
731-
__ Add(scratch1, scratch1, scratch2);
732-
StoreRegExpStackPointerToMemory(scratch1, scratch2);
727+
__ Ldr(stack_pointer_out,
728+
MemOperand(frame_pointer(), kRegExpStackBasePointer));
729+
__ Mov(scratch, ref);
730+
__ Ldr(scratch, MemOperand(scratch));
731+
__ Add(stack_pointer_out, stack_pointer_out, scratch);
732+
StoreRegExpStackPointerToMemory(stack_pointer_out, scratch);
733733
}
734734

735735
Handle<HeapObject> RegExpMacroAssemblerARM64::GetCode(Handle<String> source) {
@@ -786,9 +786,14 @@ Handle<HeapObject> RegExpMacroAssemblerARM64::GetCode(Handle<String> source) {
786786
((kNumberOfStackLocals * kWRegPerXReg) + align_mask) & ~align_mask);
787787
__ Claim(kNumberOfStackLocals * kWRegPerXReg);
788788

789+
// Initialize backtrack stack pointer. It must not be clobbered from here on.
790+
// Note the backtrack_stackpointer is callee-saved.
791+
STATIC_ASSERT(backtrack_stackpointer() == x23);
792+
LoadRegExpStackPointerFromMemory(backtrack_stackpointer());
793+
789794
// Store the regexp base pointer - we'll later restore it / write it to
790795
// memory when returning from this irregexp code object.
791-
PushRegExpBasePointer(x10, x11);
796+
PushRegExpBasePointer(backtrack_stackpointer(), x11);
792797

793798
// Set the number of registers we will need to allocate, that is:
794799
// - (num_registers_ - kNumCachedRegisters) (W registers)
@@ -797,35 +802,36 @@ Handle<HeapObject> RegExpMacroAssemblerARM64::GetCode(Handle<String> source) {
797802
const int num_wreg_to_allocate =
798803
(num_stack_registers + align_mask) & ~align_mask;
799804

800-
// Check if we have space on the stack.
801-
Label stack_limit_hit;
802-
Label stack_ok;
805+
{
806+
// Check if we have space on the stack.
807+
Label stack_limit_hit, stack_ok;
803808

804-
ExternalReference stack_limit =
805-
ExternalReference::address_of_jslimit(isolate());
806-
__ Mov(x10, stack_limit);
807-
__ Ldr(x10, MemOperand(x10));
808-
__ Subs(x10, sp, x10);
809+
ExternalReference stack_limit =
810+
ExternalReference::address_of_jslimit(isolate());
811+
__ Mov(x10, stack_limit);
812+
__ Ldr(x10, MemOperand(x10));
813+
__ Subs(x10, sp, x10);
809814

810-
// Handle it if the stack pointer is already below the stack limit.
811-
__ B(ls, &stack_limit_hit);
815+
// Handle it if the stack pointer is already below the stack limit.
816+
__ B(ls, &stack_limit_hit);
812817

813-
// Check if there is room for the variable number of registers above
814-
// the stack limit.
815-
__ Cmp(x10, num_wreg_to_allocate * kWRegSize);
816-
__ B(hs, &stack_ok);
818+
// Check if there is room for the variable number of registers above
819+
// the stack limit.
820+
__ Cmp(x10, num_wreg_to_allocate * kWRegSize);
821+
__ B(hs, &stack_ok);
817822

818-
// Exit with OutOfMemory exception. There is not enough space on the stack
819-
// for our working registers.
820-
__ Mov(w0, EXCEPTION);
821-
__ B(&return_w0);
823+
// Exit with OutOfMemory exception. There is not enough space on the stack
824+
// for our working registers.
825+
__ Mov(w0, EXCEPTION);
826+
__ B(&return_w0);
822827

823-
__ Bind(&stack_limit_hit);
824-
CallCheckStackGuardState(x10);
825-
// If returned value is non-zero, we exit with the returned value as result.
826-
__ Cbnz(w0, &return_w0);
828+
__ Bind(&stack_limit_hit);
829+
CallCheckStackGuardState(x10);
830+
// If returned value is non-zero, we exit with the returned value as result.
831+
__ Cbnz(w0, &return_w0);
827832

828-
__ Bind(&stack_ok);
833+
__ Bind(&stack_ok);
834+
}
829835

830836
// Allocate space on stack.
831837
__ Claim(num_wreg_to_allocate, kWRegSize);
@@ -858,25 +864,26 @@ Handle<HeapObject> RegExpMacroAssemblerARM64::GetCode(Handle<String> source) {
858864
// Initialize code pointer register.
859865
__ Mov(code_pointer(), Operand(masm_->CodeObject()));
860866

861-
Label load_char_start_regexp, start_regexp;
862-
// Load newline if index is at start, previous character otherwise.
863-
__ Cbnz(start_offset(), &load_char_start_regexp);
864-
__ Mov(current_character(), '\n');
865-
__ B(&start_regexp);
867+
Label load_char_start_regexp;
868+
{
869+
Label start_regexp;
870+
// Load newline if index is at start, previous character otherwise.
871+
__ Cbnz(start_offset(), &load_char_start_regexp);
872+
__ Mov(current_character(), '\n');
873+
__ B(&start_regexp);
874+
875+
// Global regexp restarts matching here.
876+
__ Bind(&load_char_start_regexp);
877+
// Load previous char as initial value of current character register.
878+
LoadCurrentCharacterUnchecked(-1, 1);
879+
__ Bind(&start_regexp);
880+
}
866881

867-
// Global regexp restarts matching here.
868-
__ Bind(&load_char_start_regexp);
869-
// Load previous char as initial value of current character register.
870-
LoadCurrentCharacterUnchecked(-1, 1);
871-
__ Bind(&start_regexp);
872882
// Initialize on-stack registers.
873883
if (num_saved_registers_ > 0) {
874884
ClearRegisters(0, num_saved_registers_ - 1);
875885
}
876886

877-
// Initialize backtrack stack pointer.
878-
LoadRegExpStackPointerFromMemory(backtrack_stackpointer());
879-
880887
// Execute.
881888
__ B(&start_label_);
882889

@@ -1027,6 +1034,10 @@ Handle<HeapObject> RegExpMacroAssemblerARM64::GetCode(Handle<String> source) {
10271034
// Update output size on the frame before we restart matching.
10281035
__ Str(output_size, MemOperand(frame_pointer(), kOutputSize));
10291036

1037+
// Restore the original regexp stack pointer value (effectively, pop the
1038+
// stored base pointer).
1039+
PopRegExpBasePointer(backtrack_stackpointer(), x11);
1040+
10301041
if (global_with_zero_length_check()) {
10311042
// Special case for zero-length matches.
10321043
__ Cmp(current_input_offset(), first_capture_start);
@@ -1059,7 +1070,7 @@ Handle<HeapObject> RegExpMacroAssemblerARM64::GetCode(Handle<String> source) {
10591070
__ Bind(&return_w0);
10601071
// Restore the original regexp stack pointer value (effectively, pop the
10611072
// stored base pointer).
1062-
PopRegExpBasePointer(x10, x11);
1073+
PopRegExpBasePointer(backtrack_stackpointer(), x11);
10631074

10641075
// Set stack pointer back to first register to retain.
10651076
__ Mov(sp, fp);

‎src/regexp/arm64/regexp-macro-assembler-arm64.h‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -262,8 +262,8 @@ class V8_EXPORT_PRIVATE RegExpMacroAssemblerARM64
262262

263263
void LoadRegExpStackPointerFromMemory(Register dst);
264264
void StoreRegExpStackPointerToMemory(Register src, Register scratch);
265-
void PushRegExpBasePointer(Register scratch1, Register scratch2);
266-
void PopRegExpBasePointer(Register scratch1, Register scratch2);
265+
void PushRegExpBasePointer(Register stack_pointer, Register scratch);
266+
void PopRegExpBasePointer(Register stack_pointer_out, Register scratch);
267267

268268
Isolate* isolate() const { return masm_->isolate(); }
269269

0 commit comments

Comments
 (0)