// Copyright 2024 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package runtime

import (
	
	
	
)

// A synctestBubble is a set of goroutines started by synctest.Run.
type synctestBubble struct {
	mu      mutex
	timers  timers
	id      uint64 // unique id
	now     int64  // current fake time
	root    *g     // caller of synctest.Run
	waiter  *g     // caller of synctest.Wait
	main    *g     // goroutine started by synctest.Run
	waiting bool   // true if a goroutine is calling synctest.Wait
	done    bool   // true if main has exited

	// The bubble is active (not blocked) so long as running > 0 || active > 0.
	//
	// running is the number of goroutines which are not "durably blocked":
	// Goroutines which are either running, runnable, or non-durably blocked
	// (for example, blocked in a syscall).
	//
	// active is used to keep the bubble from becoming blocked,
	// even if all goroutines in the bubble are blocked.
	// For example, park_m can choose to immediately unpark a goroutine after parking it.
	// It increments the active count to keep the bubble active until it has determined
	// that the park operation has completed.
	total   int // total goroutines
	running int // non-blocked goroutines
	active  int // other sources of activity
}

// changegstatus is called when the non-lock status of a g changes.
// It is never called with a Gscanstatus.
func ( *synctestBubble) ( *g, ,  uint32) {
	// Determine whether this change in status affects the idleness of the bubble.
	// If this isn't a goroutine starting, stopping, durably blocking,
	// or waking up after durably blocking, then return immediately without
	// locking bubble.mu.
	//
	// For example, stack growth (newstack) will changegstatus
	// from _Grunning to _Gcopystack. This is uninteresting to synctest,
	// but if stack growth occurs while bubble.mu is held, we must not recursively lock.
	 := 0
	 := true
	switch  {
	case _Gdead:
		 = false
		++
	case _Gwaiting:
		if .waitreason.isIdleInSynctest() {
			 = false
		}
	}
	 := true
	switch  {
	case _Gdead:
		 = false
		--
		if  == .main {
			.done = true
		}
	case _Gwaiting:
		if .waitreason.isIdleInSynctest() {
			 = false
		}
	}
	// It's possible for wasRunning == isRunning while totalDelta != 0;
	// for example, if a new goroutine is created in a non-running state.
	if  ==  &&  == 0 {
		return
	}

	lock(&.mu)
	.total += 
	if  !=  {
		if  {
			.running++
		} else {
			.running--
			if raceenabled &&  != _Gdead {
				// Record that this goroutine parking happens before
				// any subsequent Wait.
				racereleasemergeg(, .raceaddr())
			}
		}
	}
	if .total < 0 {
		fatal("total < 0")
	}
	if .running < 0 {
		fatal("running < 0")
	}
	 := .maybeWakeLocked()
	unlock(&.mu)
	if  != nil {
		goready(, 0)
	}
}

// incActive increments the active-count for the bubble.
// A bubble does not become durably blocked while the active-count is non-zero.
func ( *synctestBubble) () {
	lock(&.mu)
	.active++
	unlock(&.mu)
}

// decActive decrements the active-count for the bubble.
func ( *synctestBubble) () {
	lock(&.mu)
	.active--
	if .active < 0 {
		throw("active < 0")
	}
	 := .maybeWakeLocked()
	unlock(&.mu)
	if  != nil {
		goready(, 0)
	}
}

// maybeWakeLocked returns a g to wake if the bubble is durably blocked.
func ( *synctestBubble) () *g {
	if .running > 0 || .active > 0 {
		return nil
	}
	// Increment the bubble active count, since we've determined to wake something.
	// The woken goroutine will decrement the count.
	// We can't just call goready and let it increment bubble.running,
	// since we can't call goready with bubble.mu held.
	//
	// Incrementing the active count here is only necessary if something has gone wrong,
	// and a goroutine that we considered durably blocked wakes up unexpectedly.
	// Two wakes happening at the same time leads to very confusing failure modes,
	// so we take steps to avoid it happening.
	.active++
	 := .timers.wakeTime()
	if  > 0 &&  <= .now {
		// A timer is scheduled to fire. Wake the root goroutine to handle it.
		return .root
	}
	if  := .waiter;  != nil {
		// A goroutine is blocked in Wait. Wake it.
		return 
	}
	// All goroutines in the bubble are durably blocked, and nothing has called Wait.
	// Wake the root goroutine.
	return .root
}

func ( *synctestBubble) () unsafe.Pointer {
	// Address used to record happens-before relationships created by the bubble.
	//
	// Wait creates a happens-before relationship between itself and
	// the blocking operations which caused other goroutines in the bubble to park.
	return unsafe.Pointer()
}

var bubbleGen atomic.Uint64 // bubble ID counter

//go:linkname synctestRun internal/synctest.Run
func synctestRun( func()) {
	if debug.asynctimerchan.Load() != 0 {
		panic("synctest.Run not supported with asynctimerchan!=0")
	}

	 := getg()
	if .bubble != nil {
		panic("synctest.Run called from within a synctest bubble")
	}
	 := &synctestBubble{
		id:      bubbleGen.Add(1),
		total:   1,
		running: 1,
		root:    ,
	}
	const  = 946684800000000000 // midnight UTC 2000-01-01
	.now = 
	lockInit(&.mu, lockRankSynctest)
	lockInit(&.timers.mu, lockRankTimers)

	.bubble = 
	defer func() {
		.bubble = nil
	}()

	// This is newproc, but also records the new g in bubble.main.
	 := sys.GetCallerPC()
	systemstack(func() {
		 := *(**funcval)(unsafe.Pointer(&))
		.main = newproc1(, , , false, waitReasonZero)
		 := getg().m.p.ptr()
		runqput(, .main, true)
		wakep()
	})

	lock(&.mu)
	.active++
	for {
		unlock(&.mu)
		systemstack(func() {
			// Clear gp.m.curg while running timers,
			// so timer goroutines inherit their child race context from g0.
			 := .m.curg
			.m.curg = nil
			.bubble.timers.check(.now, )
			.m.curg = 
		})
		gopark(synctestidle_c, nil, waitReasonSynctestRun, traceBlockSynctest, 0)
		lock(&.mu)
		if .active < 0 {
			throw("active < 0")
		}
		 := .timers.wakeTime()
		if  == 0 {
			break
		}
		if  < .now {
			throw("time went backwards")
		}
		if .done {
			// Time stops once the bubble's main goroutine has exited.
			break
		}
		.now = 
	}

	 := .total
	unlock(&.mu)
	if raceenabled {
		// Establish a happens-before relationship between bubbled goroutines exiting
		// and Run returning.
		raceacquireg(, .bubble.raceaddr())
	}
	if  != 1 {
		var  string
		if .done {
			 = "deadlock: main bubble goroutine has exited but blocked goroutines remain"
		} else {
			 = "deadlock: all goroutines in bubble are blocked"
		}
		panic(synctestDeadlockError{reason: , bubble: })
	}
	if .timer != nil && .timer.isFake {
		// Verify that we haven't marked this goroutine's sleep timer as fake.
		// This could happen if something in Run were to call timeSleep.
		throw("synctest root goroutine has a fake timer")
	}
}

type synctestDeadlockError struct {
	reason string
	bubble *synctestBubble
}

func ( synctestDeadlockError) () string {
	return .reason
}

func synctestidle_c( *g,  unsafe.Pointer) bool {
	lock(&.bubble.mu)
	 := true
	if .bubble.running == 0 && .bubble.active == 1 {
		// All goroutines in the bubble have blocked or exited.
		 = false
	} else {
		.bubble.active--
	}
	unlock(&.bubble.mu)
	return 
}

//go:linkname synctestWait internal/synctest.Wait
func synctestWait() {
	 := getg()
	if .bubble == nil {
		panic("goroutine is not in a bubble")
	}
	lock(&.bubble.mu)
	// We use a bubble.waiting bool to detect simultaneous calls to Wait rather than
	// checking to see if bubble.waiter is non-nil. This avoids a race between unlocking
	// bubble.mu and setting bubble.waiter while parking.
	if .bubble.waiting {
		unlock(&.bubble.mu)
		panic("wait already in progress")
	}
	.bubble.waiting = true
	unlock(&.bubble.mu)
	gopark(synctestwait_c, nil, waitReasonSynctestWait, traceBlockSynctest, 0)

	lock(&.bubble.mu)
	.bubble.active--
	if .bubble.active < 0 {
		throw("active < 0")
	}
	.bubble.waiter = nil
	.bubble.waiting = false
	unlock(&.bubble.mu)

	// Establish a happens-before relationship on the activity of the now-blocked
	// goroutines in the bubble.
	if raceenabled {
		raceacquireg(, .bubble.raceaddr())
	}
}

func synctestwait_c( *g,  unsafe.Pointer) bool {
	lock(&.bubble.mu)
	if .bubble.running == 0 && .bubble.active == 0 {
		// This shouldn't be possible, since gopark increments active during unlockf.
		throw("running == 0 && active == 0")
	}
	.bubble.waiter = 
	unlock(&.bubble.mu)
	return true
}

//go:linkname synctest_isInBubble internal/synctest.IsInBubble
func synctest_isInBubble() bool {
	return getg().bubble != nil
}

//go:linkname synctest_acquire internal/synctest.acquire
func synctest_acquire() any {
	if  := getg().bubble;  != nil {
		.incActive()
		return 
	}
	return nil
}

//go:linkname synctest_release internal/synctest.release
func synctest_release( any) {
	.(*synctestBubble).decActive()
}

//go:linkname synctest_inBubble internal/synctest.inBubble
func synctest_inBubble( any,  func()) {
	 := getg()
	if .bubble != nil {
		panic("goroutine is already bubbled")
	}
	.bubble = .(*synctestBubble)
	defer func() {
		.bubble = nil
	}()
	()
}

// specialBubble is a special used to associate objects with bubbles.
type specialBubble struct {
	_        sys.NotInHeap
	special  special
	bubbleid uint64
}

// Keep these in sync with internal/synctest.
const (
	bubbleAssocUnbubbled     = iota // not associated with any bubble
	bubbleAssocCurrentBubble        // associated with the current bubble
	bubbleAssocOtherBubble          // associated with a different bubble
)

// getOrSetBubbleSpecial checks the special record for p's bubble membership.
//
// If add is true and p is not associated with any bubble,
// it adds a special record for p associating it with bubbleid.
//
// It returns ok==true if p is associated with bubbleid
// (including if a new association was added),
// and ok==false if not.
func getOrSetBubbleSpecial( unsafe.Pointer,  uint64,  bool) ( int) {
	 := spanOfHeap(uintptr())
	if  == nil {
		// This is probably a package var.
		// We can't attach a special to it, so always consider it unbubbled.
		return bubbleAssocUnbubbled
	}

	// Ensure that the span is swept.
	// Sweeping accesses the specials list w/o locks, so we have
	// to synchronize with it. And it's just much safer.
	 := acquirem()
	.ensureSwept()

	 := uintptr() - .base()

	lock(&.speciallock)

	// Find splice point, check for existing record.
	,  := .specialFindSplicePoint(, _KindSpecialBubble)
	if  {
		// p is already associated with a bubble.
		// Return true iff it's the same bubble.
		 := (*specialBubble)((unsafe.Pointer)(*))
		if .bubbleid ==  {
			 = bubbleAssocCurrentBubble
		} else {
			 = bubbleAssocOtherBubble
		}
	} else if  {
		// p is not associated with a bubble,
		// and we've been asked to add an association.
		 := (*specialBubble)(mheap_.specialBubbleAlloc.alloc())
		.bubbleid = 
		.special.kind = _KindSpecialBubble
		.special.offset = 
		.special.next = *
		* = (*special)(unsafe.Pointer())
		spanHasSpecials()
		 = bubbleAssocCurrentBubble
	} else {
		// p is not associated with a bubble.
		 = bubbleAssocUnbubbled
	}

	unlock(&.speciallock)
	releasem()

	return 
}

// synctest_associate associates p with the current bubble.
// It returns false if p is already associated with a different bubble.
//
//go:linkname synctest_associate internal/synctest.associate
func synctest_associate( unsafe.Pointer) int {
	return getOrSetBubbleSpecial(, getg().bubble.id, true)
}

// synctest_disassociate disassociates p from its bubble.
//
//go:linkname synctest_disassociate internal/synctest.disassociate
func synctest_disassociate( unsafe.Pointer) {
	removespecial(, _KindSpecialBubble)
}

// synctest_isAssociated reports whether p is associated with the current bubble.
//
//go:linkname synctest_isAssociated internal/synctest.isAssociated
func synctest_isAssociated( unsafe.Pointer) bool {
	return getOrSetBubbleSpecial(, getg().bubble.id, false) == bubbleAssocCurrentBubble
}