raquo / Airstream

State propagation and event streams with mandatory ownership and no glitches
MIT License
246 stars 28 forks source link

Transaction stack overflow caused by sibling transactions #115

Closed raquo closed 9 months ago

raquo commented 9 months ago

I expect the stack to blow when transactions are (very) deeply nested, but apparently it also happens if transactions go "wide", i.e. if there are many sibling transactions. Summary from @hoangdm. on discord:

  • For some reason my app created a transaction with many children (~5k) and each child transaction does not have any other child. So it looks like a tree with the depth of 2, 1 root which has ~5k leaves.
  • Now we Transaction.run() on first leaf. After that we call Transaction.pendingTransactions.done(), which putNextTransactionOnStack() (2nd leaf), and then call Transaction.run() recursively, and so on. We basically traversed 5k~ leaves recursively, because we don't yield or return in any of those steps.

So we actually don't need Transaction-tree's depth to reaches deep, we just need a tree with a lot of leaves to blow the stack. I will try to see why my app spams that much leaves. But I do think blowing the stack is much easier than we initially though (Unless I read the code wrong).

I can reproduce it on 17.x but previous versions are probably also affected. Reproduction:

    val bus = new EventBus[Unit]

    val num = 100000
    var ix = 0

    bus.events.foreach { _ =>
      new Transaction(_ =>
        for {
          i <- 1 to num
        } yield {
          new Transaction(_ =>
            ix += 1
          )
        }
      )
    }(unsafeWindowOwner)
    bus.emit(())
    println(s"Done without errors. $ix")

Looking into it...

raquo commented 9 months ago

Fixed in https://github.com/raquo/Airstream/commit/281f7b094fdb74ea3753912e6041cc8b5cc36db1 (based on 17.0.0-M1, so to be used with Laminar v16). I will release that as M3, and port it to M2 and release that as M4.

That commit makes transactions stack safe, both in breadth and in deep nesting.

I'm also planning to add a customizable transaction depth limit to detect that kind of accidental infinite loop: https://github.com/raquo/Laminar/issues/116 (otherwise that kind of bug in your code would pin the cpu and freeze the entire client app).

HollandDM commented 9 months ago

Thank you for your quick replies on discord.

In my opinions, if we can somehow traverse the graph in truly depth first order (siblings do not create new function calls, only children do), it’d be the best. Because I do think that creating a transaction tree that go too deep is more of a bug than a coding logic, and stack overflowing in that case is a very necessary indicator.

raquo commented 9 months ago

In my opinions, if we can somehow traverse the graph in truly depth first order (siblings do not create new function calls, only children do), it’d be the best.

I'm not sure if I understand what exactly you mean, but if you mean the internal mechanics of Transaction - how Transaction.run is called recursively even in case of sibling (not nested) transactions – then this is already fixed in that commit I linked. That recursion is now tail call optimized, @tailrec ensures that this recursion is rewritten into a while loop that does not blow the stack when it compiles to JS. I've added two tests, one with 20K sibling transactions, another with 20K nested transactions, that should catch any stack overflow regressions in this code.

raquo commented 9 months ago

Fixed in Airstream 17.0.0-M3 (binary compatible with Laminar 16) and 17.0.0-M6. See Discord #news channel for details of the releases.