[Bug Report] Orders are never freed: the price-level list holds `shared_ptr` in both directions (reference cycle)

[OPTIONPOOL]

Found while integrating timothewt/orderbook into an open matching-engine benchmark, the Matching Engine Performance Challenge — it cross-checks engines against the byte-identical consensus of other open-source engines. While driving the engine's Book API directly I noticed that orders placed into a price level are kept alive even after the level and every reference to them are gone, so I wanted to pass along a small reproducible note and a suggested fix. The matching results are correct — this is purely about memory reclamation.

Pinned at main (14ee65089c1ff4c4617d1a35f04214023057e4af); g++ 14, C++20, building the library translation units src/Book.cpp / src/Limit.cpp / src/Order.cpp.

What happens

Each Order stores both its prev and its next neighbour as a std::shared_ptr<Order> (src/Order.h:18-19). Two adjacent resting orders in a Limit's FIFO list therefore own each other (a.next → b, b.prev → a), which is a reference cycle std::shared_ptr cannot collect. As a result an order inserted into a price level is never destroyed even after the Limit and all external references to it have been released — its memory is held for the lifetime of the process by the neighbouring node's link.

Minimal reproduction

Pure Limit level — no Book, no id_to_order involved — so it isolates the list-node cycle:

#include "src/Limit.h"
#include "src/Order.h"
#include <cstdio>
#include <memory>

int main() {
    std::weak_ptr<Order> w1, w2, w3;
    {
        auto o1 = std::make_shared<Order>(1, 0, BUY, 100, 10);
        auto o2 = std::make_shared<Order>(2, 0, BUY, 100, 10);
        auto o3 = std::make_shared<Order>(3, 0, BUY, 100, 10);
        w1 = o1; w2 = o2; w3 = o3;
        Limit limit(100);
        limit.insert_order(o1);
        limit.insert_order(o2);
        limit.insert_order(o3);
        // o1..o3 and `limit` all leave scope here: every external strong
        // reference is gone and the level is destroyed.
    }
    printf("still alive: %d/3   use_count %ld/%ld/%ld\n",
           (!w1.expired()) + (!w2.expired()) + (!w3.expired()),
           w1.use_count(), w2.use_count(), w3.use_count());
}

# g++ -std=c++20 -I. repro.cpp src/Order.cpp src/Limit.cpp -o repro && ./repro
still alive: 3/3   use_count 1/2/1

Expected: still alive: 0/3 — once the Limit and the three local shared_ptrs are gone, nothing should keep the orders alive. Instead each is held by an adjacent node (o2.prev keeps o1, o1.next/o3.prev keep o2, o2.next keeps o3), so all three leak.

Mechanism / root cause

src/Order.h:18-19:

std::shared_ptr<Order> prev; /**< Previous order in the list */
std::shared_ptr<Order> next; /**< Next order in the list */

Limit::insert_order links them both ways (tail->set_next(order); order->set_prev(tail);), forming the prev/next ownership cycle. Limit::delete_order does break the links of an order it explicitly removes (order->get_prev().reset(); order->get_next().reset();), so orders that are cancelled or fully consumed mid-run are reclaimed — but any chain still linked when the Limit/Book is destroyed (e.g. a book that still holds resting depth at teardown, or a multi-order level that is dropped wholesale) leaks every node in it. A compounding factor in the same direction: id_to_order (declared in src/Book.h, written at src/Book.cpp:8) is only ever written, never erased, so it independently retains every order for the Book's lifetime; a small erase on the delete / full-fill paths would let that map track live book depth too.

Suggested fix

The canonical break for a shared_ptr doubly-linked list is to make the back-link non-owning. Minimal change, confined to Order plus the two link-clearing lines in Limit::delete_order:

--- a/src/Order.h
+++ b/src/Order.h
@@ private:
-	std::shared_ptr<Order> prev; /**< Previous order in the list */
+	std::weak_ptr<Order> prev;   /**< Previous order (weak: breaks the ownership cycle) */
 	std::shared_ptr<Order> next; /**< Next order in the list */
@@ ctor member-init
-			status(ACTIVE), prev(nullptr), next(nullptr) {}
+			status(ACTIVE), prev(), next(nullptr) {}
@@ public:
-	std::shared_ptr<Order> &get_prev();
-	void set_prev(std::shared_ptr<Order> &prev);
+	std::shared_ptr<Order> get_prev();
+	void set_prev(const std::shared_ptr<Order> &prev);
--- a/src/Order.cpp
+++ b/src/Order.cpp
-OrderPointer &Order::get_prev() { return prev; }
-void Order::set_prev(OrderPointer& prev) { this->prev = prev; }
+OrderPointer Order::get_prev() { return prev.lock(); }
+void Order::set_prev(const OrderPointer& prev) { this->prev = prev; }
--- a/src/Limit.cpp
+++ b/src/Limit.cpp
@@ Limit::delete_order — head-removal branch (order == head)
-		order->get_next()->get_prev().reset();
+		order->get_next()->set_prev({});
@@ Limit::delete_order — link cleanup at the end of the function
-	order->get_prev().reset();
+	order->set_prev({});
 	order->get_next().reset();

get_prev() now returns prev.lock() (a fresh strong handle for the brief moment a caller needs to walk backwards), so the read-side uses in delete_order — tail = order->get_prev();, order->get_prev()->set_next(...), order->get_next()->set_prev(order->get_prev()) — keep working unchanged (the locked temporary stays alive for the full statement). The two spots that clear a back-link both move from .reset() to set_prev({}), because get_prev() now hands back a temporary and a plain .reset() on it would silently compile to a no-op (it does so with no warning even under -Wall -Wextra): the head-removal branch and the link cleanup at the end of delete_order.

I built this and re-ran the repro above: it then prints still alive: 0/3 use_count 0/0/0, and the engine's matching behaviour is unchanged — the repository's own unit-test suite (20 tests) still passes.

I appreciate the clean, readable design of the book — this is just a time-stamped snapshot of one commit, offered back in case it is useful; it is not a comment on the project or its author.

Respectfully submitted.