From a59b2f7c527fc8591d8f373d7a278cca44754ccc Mon Sep 17 00:00:00 2001
From: "iguerNL@Functori" <iguer@functori.com>
Date: Thu, 12 May 2022 09:30:08 +0200
Subject: [PATCH] Proto/Scoru: Fix the sliding window mechanism in history
 remembering

---
 .../lib_protocol/sc_rollup_inbox_repr.ml      | 81 +++++++++++++------
 1 file changed, 57 insertions(+), 24 deletions(-)

diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml
index 5dbb4a844ce2..7220756c5cc3 100644
--- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml
+++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml
@@ -498,33 +498,66 @@ module MakeHashingScheme (Tree : TREE) :
       mapping from [ptr] to [cell]. If [history] is full, the
       oldest mapping is removed. If the history bound is less
       or equal to zero, then this function returns [history]
-      untouched. *)
-  let remember ptr cell history =
-    if Compare.Int64.(history.bound <= 0L) then history
-    else
-      let events = Context_hash.Map.add ptr cell history.events in
-      let counter = Int64.succ history.counter in
-      let history =
+      untouched.
+
+      This function assumes the following hypothesis on history:
+      - [bound] < Int64.max_int
+      - If [history.events] && [history.sequence], then counter = 0L
+  *)
+  let remember =
+    let normalize_counter history =
+      if Compare.Int64.(history.counter <> Int64.max_int) then history
+      else
+        let {counter; bound; sequence; events} = history in
+        assert (Compare.Int64.(bound < Int64.max_int)) ;
+        let delta = Int64.(sub counter bound) in
+        (* [counter] = Int64.max_int. To ovoid overflowing at the next
+           incrementation of [counter], we subtract [delta] from the [counter]
+           and from keys of [sequence] to avoid the overflow, while still having
+           the same ordering *)
         {
+          bound;
+          counter = bound (* = counter - delta *);
           events;
-          sequence = Int64_map.add history.counter ptr history.sequence;
-          bound = history.bound;
-          counter;
+          sequence =
+            (* keys will range from 1 to bound after the subtraction *)
+            Int64_map.(
+              fold (fun k v mp -> add Int64.(sub k delta) v mp) sequence empty);
         }
-      in
-      if Int64.(equal history.counter history.bound) then
-        match Int64_map.min_binding history.sequence with
-        | None -> history
-        | Some (l, h) ->
-            let sequence = Int64_map.remove l history.sequence in
-            let events = Context_hash.Map.remove h events in
-            {
-              counter = Int64.pred history.counter;
-              bound = history.bound;
-              sequence;
-              events;
-            }
-      else history
+    in
+    fun ptr cell history ->
+      if Compare.Int64.(history.bound <= 0L) then history
+      else
+        (* normalize counter and indexes in case the next counter++ overflows *)
+        let history = normalize_counter history in
+        let events = Context_hash.Map.add ptr cell history.events in
+        let counter = Int64.succ history.counter in
+        let history =
+          {
+            events;
+            sequence = Int64_map.add history.counter ptr history.sequence;
+            bound = history.bound;
+            counter;
+          }
+        in
+        if Compare.Int64.(history.counter < history.bound) then history
+        else
+          (* Assuming counter starts at 0L, if counter >= bound then history's
+             min element should be removed. *)
+          match Int64_map.min_binding history.sequence with
+          | None ->
+              (* Unreachable: since counter >= bound > 0, there is at least one
+                 element in [history.sequence] *)
+              assert false
+          | Some (l, h) ->
+              (* GC the min element to only keep the [bound] most recent elements
+                 in history. *)
+              {
+                counter = history.counter;
+                bound = history.bound;
+                sequence = Int64_map.remove l history.sequence;
+                events = Context_hash.Map.remove h events;
+              }
 
   let archive_if_needed history inbox target_level =
     let archive_level history inbox =
-- 
GitLab