https://gitlab.com/tezos/tezos
Tip revision: f9df9fefbf40630f214e88087904eddf1a76b169 authored by Albin Coquereau on 06 November 2023, 14:18:57 UTC
prevalidator: add a hashtable for operations already handled
prevalidator: add a hashtable for operations already handled
Tip revision: f9df9fe
game_helpers.ml
(*****************************************************************************)
(* *)
(* Open Source License *)
(* Copyright (c) 2022 Nomadic Labs, <contact@nomadic-labs.com> *)
(* *)
(* Permission is hereby granted, free of charge, to any person obtaining a *)
(* copy of this software and associated documentation files (the "Software"),*)
(* to deal in the Software without restriction, including without limitation *)
(* the rights to use, copy, modify, merge, publish, distribute, sublicense, *)
(* and/or sell copies of the Software, and to permit persons to whom the *)
(* Software is furnished to do so, subject to the following conditions: *)
(* *)
(* The above copyright notice and this permission notice shall be included *)
(* in all copies or substantial portions of the Software. *)
(* *)
(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*)
(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, *)
(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL *)
(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*)
(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING *)
(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER *)
(* DEALINGS IN THE SOFTWARE. *)
(* *)
(*****************************************************************************)
open Protocol.Alpha_context.Sc_rollup
let default_new_dissection ~default_number_of_sections
~(start_chunk : Game.dissection_chunk)
~(our_stop_chunk : Game.dissection_chunk) =
let max_number_of_sections = Z.of_int default_number_of_sections in
let trace_length = Tick.distance our_stop_chunk.tick start_chunk.tick in
let number_of_sections = Z.min max_number_of_sections trace_length in
let rem = Z.(rem trace_length number_of_sections) in
let first_section_length, section_length =
if Compare.Z.(trace_length <= max_number_of_sections) then
(* In this case, every section is of length one. *)
Z.(one, one)
else
let section_length = Z.(max one (div trace_length number_of_sections)) in
if Compare.Z.(section_length = Z.one) && not Compare.Z.(rem = Z.zero) then
(* If we put [section_length] in this situation, we will most likely
have a very long last section. *)
(rem, section_length)
else (section_length, section_length)
in
(* [k] is the number of sections in [rev_dissection]. *)
let rec make rev_dissection k tick =
if Z.(equal k number_of_sections) then List.rev rev_dissection
else
let next_tick = Tick.jump tick section_length in
make (tick :: rev_dissection) (Z.succ k) next_tick
in
make [] Z.one (Tick.jump start_chunk.tick first_section_length)
let make_dissection ~state_of_tick ~state_hash_of_eval_state ?start_state
~start_chunk ~our_stop_chunk ticks =
let rec make_dissection_aux start_state ticks acc =
let open Lwt_result_syntax in
match ticks with
| tick :: rst ->
let* eval_state = state_of_tick ?start_state tick in
let state_hash = Option.map state_hash_of_eval_state eval_state in
let chunk = Dissection_chunk.{tick; state_hash} in
make_dissection_aux eval_state rst (chunk :: acc)
| [] -> return @@ List.rev (our_stop_chunk :: acc)
in
make_dissection_aux start_state ticks [start_chunk]
module Wasm = struct
let new_dissection ~default_number_of_sections ~start_chunk ~our_stop_chunk =
let open Dissection_chunk in
let dist = Tick.distance start_chunk.tick our_stop_chunk.tick in
let ticks_per_snapshot = Wasm_2_0_0PVM.ticks_per_snapshot in
if Compare.Z.(dist <= ticks_per_snapshot) then
(*
There are two cases that require us to fall back to the
default behavior. Either [start_chunk] is not aligned on the
size of a snapshot (meaning the PVM is stuck) or the distance
between the start and stop chunk is lesser than a snapshot,
meaning we have already found the kernel_run invocation we
were looking for.
*)
default_new_dissection
~default_number_of_sections
~start_chunk
~our_stop_chunk
else
let is_stop_chunk_aligned =
Compare.Z.(
Z.rem (Tick.to_z our_stop_chunk.tick) ticks_per_snapshot = Z.zero)
in
let final_tick =
Tick.of_z
Z.(
div (Tick.to_z our_stop_chunk.tick) ticks_per_snapshot
* ticks_per_snapshot)
in
let dist = Tick.distance start_chunk.tick final_tick in
let max_number_of_sections = Z.(div dist ticks_per_snapshot) in
let number_of_sections =
Z.min
(Z.of_int
(* If [is_stop_chunk_aligned] is false, we allocate one
sections for the surplus. *)
(if is_stop_chunk_aligned then default_number_of_sections
else default_number_of_sections - 1))
max_number_of_sections
in
(* [go remaining_sections last_tick dist] tries to compute
[remaining_sections] sections as evenly as possible, starting
from [last_tick] and covering [dist] ticks. *)
let rec go remaining_sections last_tick dist rev_acc =
(* The last section is created by [make_dissection] when it
adds the [stop_chunk]. *)
if Z.(remaining_sections <= one) then
let rev_acc =
(* If [is_stop_chunk_aligned] is false, we insert the
last snapshot point. *)
if is_stop_chunk_aligned then rev_acc else final_tick :: rev_acc
in
List.rev rev_acc
else
(*
We compute the length of the next section of the
dissection as the maximum size such that if we would give
this number to all remaining sections, we would not
consume more than [dist] ticks. This is ensured by
[Z.div], which computes a lower rounding.
*)
let section_len =
Z.(
dist
/ (ticks_per_snapshot * remaining_sections)
* ticks_per_snapshot)
in
let next_tick = Tick.jump last_tick section_len in
let next_dist = Z.(dist - section_len) in
(*
There are two cases to consider here.
1. Either [dist] was a multiple of
[ticks_per_snapshot]. In that case, the same
[section_len] will be computed in all subsequent
calls of [go].
2. Or [dist] was not a multiple of
[ticks_per_snapshot]. In that case, the next
[section_len] in float will be slightly higher than
the previous one, because it will benefit from the
unconsumed reminder of the previous computation,
until enough is left that [dist] becomes a
multiplier of [ticks_per_snapshot]. In that case, we
will fall back to case 1.
Take case of dividing 60 into 32 chunks.
- [remaining_sections = 60], [remaining_sections = 32], and
[section_len = 1] (60 / 32 ~= 1.87)
- [remaining_sections = 59], [remaining_sections = 31], and
[section_len = 1] (59 / 31 ~= 1.90)
- [remaining_sections = 58], [remaining_sections = 30], and
[section_len = 1] (58 / 30 ~= 1.93)
- [remaining_sections = 57], [remaining_sections = 29], and
[section_len = 1] (57 / 29 ~= 1.97)
- [remaining_sections = 56], [remaining_sections = 28], and
[section_len = 2] (56 / 28 = 2)
All remaining sections will be of length 2.
*)
go
Z.(pred remaining_sections)
next_tick
next_dist
(next_tick :: rev_acc)
in
go number_of_sections start_chunk.tick dist []
end