• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

MinaProtocol / mina / 2841

30 Oct 2024 07:56AM UTC coverage: 33.412% (-27.7%) from 61.098%
2841

push

buildkite

web-flow
Merge pull request #16306 from MinaProtocol/dkijania/fix_promotion_to_gcr

Fix promotion job PUBLISH misuse

22273 of 66661 relevant lines covered (33.41%)

119594.1 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

20.74
/src/lib/staged_ledger_diff/bitswap_block.ml
1
open Core_kernel
5✔
2

3
let or_error_list_bind ls ~f =
4
  let open Or_error.Let_syntax in
×
5
  let rec loop ls acc =
6
    let%bind acc' = acc in
7
    match ls with
×
8
    | [] ->
×
9
        return acc'
10
    | h :: t ->
×
11
        let%bind r = f h in
×
12
        loop t (return (r :: acc'))
×
13
  in
14
  loop ls (return []) >>| List.rev >>| List.concat
×
15

16
type link = Blake2.t
17

18
let link_size = Blake2.digest_size_in_bytes
19

20
let absolute_max_links_per_block = Stdint.Uint16.(to_int max_int)
5✔
21

22
(** A bitswap block schema consists of a series of branch-blocks and leaf-blocks.
23
 *  A branch-block contains both links to successive blocks, as well as data. A
24
 *  leaf-block contains only data, and no links. Of the branch-blocks, there will
25
 *  be either 0 or 1 block that has less links than the rest of the branch-blocks.
26
 *  We refer to this block as the partial-branch-block, and the other branch-blocks
27
 *  ar referred to as full-branch-blocks.
28
 *)
29
type schema =
×
30
  { num_total_blocks : int  (** the total number of blocks *)
×
31
  ; num_full_branch_blocks : int
×
32
        (** the number of link-blocks which contain the maximum number of links *)
33
  ; num_links_in_partial_branch_block : int
×
34
        (** the number of links in the non-full link block (if it is 0, there is no non-full link block *)
35
  ; last_leaf_block_data_size : int
×
36
        (** the size of data (in bytes) contained in the last block *)
37
  ; max_block_data_size : int
×
38
        (** the maximum data size (in bytes) that a block contains *)
39
  ; max_links_per_block : int
×
40
        (** the maximum number of links that can be stored in a block (all link-blocks except the non-full-link-block will have this number of links) *)
41
  }
42
[@@deriving compare, eq, sexp]
43

44
let required_bitswap_block_count ~max_block_size data_length =
45
  if data_length <= max_block_size - 2 then 1
405✔
46
  else
47
    let n1 = data_length - link_size in
×
48
    let n2 = max_block_size - link_size - 2 in
49
    (n1 + n2 - 1) / n2
50

51
let max_links_per_block ~max_block_size =
52
  let links_per_block = (max_block_size - 2) / link_size in
405✔
53
  min links_per_block absolute_max_links_per_block
54

55
let create_schema ~max_block_size data_length =
56
  let num_total_blocks =
405✔
57
    required_bitswap_block_count ~max_block_size data_length
58
  in
59
  let last_leaf_block_data_size =
405✔
60
    data_length - ((max_block_size - link_size - 2) * (num_total_blocks - 1))
61
  in
62
  let max_links_per_block = max_links_per_block ~max_block_size in
63
  let num_full_branch_blocks = (num_total_blocks - 1) / max_links_per_block in
64
  let num_links_in_partial_branch_block =
65
    num_total_blocks - 1 - (num_full_branch_blocks * max_links_per_block)
66
  in
67
  { num_total_blocks
68
  ; num_full_branch_blocks
69
  ; last_leaf_block_data_size
70
  ; num_links_in_partial_branch_block
71
  ; max_block_data_size = max_block_size
72
  ; max_links_per_block
73
  }
74

75
let create_schema_length_prefixed ~max_block_size data_length =
76
  create_schema ~max_block_size (data_length + 4)
×
77

78
let blocks_of_data ~max_block_size data =
79
  if max_block_size <= 2 + link_size then failwith "Max block size too small" ;
×
80
  let max_data_chunk_size = max_block_size - 2 in
405✔
81
  let data_length = Bigstring.length data in
82
  let schema = create_schema ~max_block_size data_length in
405✔
83
  let remaining_data = ref data_length in
405✔
84
  let blocks = Blake2.Table.create () in
85
  let link_queue = Queue.create () in
405✔
86
  let dequeue_chunk chunk_size =
405✔
87
    assert (!remaining_data >= chunk_size) ;
405✔
88
    let chunk =
89
      Bigstring.sub_shared data
90
        ~pos:(!remaining_data - chunk_size)
91
        ~len:chunk_size
92
    in
93
    remaining_data := !remaining_data - chunk_size ;
405✔
94
    chunk
95
  in
96
  let dequeue_links num_links =
97
    assert (Queue.length link_queue >= num_links) ;
×
98
    let links = ref [] in
99
    for _ = 1 to num_links do
100
      links := Queue.dequeue_exn link_queue :: !links
×
101
    done ;
102
    !links
103
  in
104
  let create_block links chunk_size =
105
    let chunk = dequeue_chunk chunk_size in
405✔
106
    let num_links = List.length links in
405✔
107
    let size = 2 + (num_links * link_size) + chunk_size in
405✔
108
    if num_links > absolute_max_links_per_block || size > max_block_size then
×
109
      failwith "invalid block produced" ;
×
110
    let block = Bigstring.create size in
405✔
111
    Bigstring.set_uint16_le_exn block ~pos:0 num_links ;
405✔
112
    List.iteri links ~f:(fun i link ->
405✔
113
        let link_buf = Bigstring.of_string (Blake2.to_raw_string link) in
×
114
        Bigstring.blit ~src:link_buf ~src_pos:0 ~dst:block
×
115
          ~dst_pos:(2 + (i * link_size))
116
          ~len:link_size ) ;
117
    Bigstring.blit ~src:chunk ~src_pos:0 ~dst:block
405✔
118
      ~dst_pos:(2 + (num_links * link_size))
119
      ~len:chunk_size ;
120
    let hash = Blake2.digest_bigstring block in
121
    Hashtbl.set blocks ~key:hash ~data:block ;
405✔
122
    Queue.enqueue link_queue hash
405✔
123
  in
124
  (* create the last block *)
125
  create_block [] schema.last_leaf_block_data_size ;
126
  if schema.num_total_blocks > 1 then (
×
127
    (* create the data-only blocks *)
128
    let num_data_only_blocks =
129
      schema.num_total_blocks - schema.num_full_branch_blocks - 1
130
      - if schema.num_links_in_partial_branch_block > 0 then 1 else 0
×
131
    in
132
    for _ = 1 to num_data_only_blocks do
133
      create_block [] max_data_chunk_size
×
134
    done ;
135
    (* create the non max link block, if there is one *)
136
    ( if schema.num_links_in_partial_branch_block > 0 then
137
      let chunk_size =
×
138
        max_block_size - 2
139
        - (schema.num_links_in_partial_branch_block * link_size)
140
      in
141
      create_block
×
142
        (dequeue_links schema.num_links_in_partial_branch_block)
×
143
        chunk_size ) ;
144
    (* create the max link blocks *)
145
    let full_link_chunk_size =
×
146
      max_block_size - 2 - (schema.max_links_per_block * link_size)
147
    in
148
    for _ = 1 to schema.num_full_branch_blocks do
149
      create_block
×
150
        (dequeue_links schema.max_links_per_block)
×
151
        full_link_chunk_size
152
    done ) ;
153
  assert (!remaining_data = 0) ;
405✔
154
  assert (Queue.length link_queue = 1) ;
405✔
155
  ( Blake2.Map.of_alist_exn (Hashtbl.to_alist blocks)
405✔
156
  , Queue.dequeue_exn link_queue )
405✔
157

158
let parse_block ~hash block =
159
  let error =
×
160
    Fn.compose Or_error.error_string
161
    @@ sprintf "parsing block %s: %s" (Blake2.to_hex hash)
×
162
  in
163
  if Bigstring.length block < 2 then error "block too short"
×
164
  else
165
    let num_links = Bigstring.get_uint16_le block ~pos:0 in
×
166
    if Bigstring.length block < 2 + (num_links * link_size) then
×
167
      error "block has invalid number of links"
×
168
    else
169
      let links =
×
170
        List.init num_links ~f:(fun i ->
171
            block
×
172
            |> Bigstring.sub_shared ~pos:(2 + (i * link_size)) ~len:link_size
×
173
            |> Bigstring.to_string |> Blake2.of_raw_string )
×
174
      in
175
      let data =
×
176
        Bigstring.sub_shared block ~pos:(2 + (num_links * link_size))
177
      in
178
      Ok (links, data)
×
179

180
let iter_links ~find_block ~report_chunk link_queue =
181
  with_return (fun { return } ->
×
182
      while Queue.length link_queue > 0 do
×
183
        let hash = Queue.dequeue_exn link_queue in
×
184
        let block =
×
185
          match find_block hash with
186
          | None ->
×
187
              return
×
188
                ( Or_error.error_string
×
189
                @@ sprintf "required block %s not found"
×
190
                @@ Blake2.to_hex hash )
×
191
          | Some data ->
×
192
              data
193
        in
194
        let successive_links, chunk =
195
          match parse_block ~hash block with
196
          | Error error ->
×
197
              return (Error error)
×
198
          | Ok x ->
×
199
              x
200
        in
201
        Queue.enqueue_all link_queue successive_links ;
202
        report_chunk chunk
×
203
      done ;
204
      Ok () )
205

206
let data_of_blocks blocks root_hash =
207
  let links = Queue.of_list [ root_hash ] in
×
208
  let chunks = Queue.create () in
×
209
  let%map.Or_error () =
210
    iter_links links ~report_chunk:(Queue.enqueue chunks)
×
211
      ~find_block:(Map.find blocks)
×
212
  in
213
  let total_data_size = Queue.sum (module Int) chunks ~f:Bigstring.length in
×
214
  let data = Bigstring.create total_data_size in
×
215
  ignore
×
216
    ( Queue.fold chunks ~init:0 ~f:(fun dst_pos chunk ->
×
217
          Bigstring.blit ~src:chunk ~src_pos:0 ~dst:data ~dst_pos
×
218
            ~len:(Bigstring.length chunk) ;
×
219
          dst_pos + Bigstring.length chunk )
×
220
      : int ) ;
221
  data
222

223
module For_tests = struct
224
  let gen =
225
    let open Quickcheck.Generator.Let_syntax in
226
    let%bind max_block_size = Int.gen_uniform_incl 256 1024 in
5✔
227
    let%bind data_length = Int.gen_log_uniform_incl 1 (Int.pow 1024 2) in
×
228
    let%map data =
229
      String.gen_with_length data_length Char.quickcheck_generator
×
230
      >>| Bigstring.of_string
×
231
    in
232
    (max_block_size, data)
×
233
end
234

235
let%test_module "bitswap blocks" =
236
  ( module struct
237
    let schema_of_blocks ~max_block_size blocks root_hash =
238
      let num_total_blocks = Map.length blocks in
×
239
      let num_full_branch_blocks = ref 0 in
×
240
      let num_links_in_partial_branch_block = ref None in
241
      let last_leaf_block_data_size = ref 0 in
242
      let max_links_per_block = max_links_per_block ~max_block_size in
243
      let rec crawl hash =
244
        let block = Map.find_exn blocks hash in
×
245
        let links, chunk = Or_error.ok_exn (parse_block ~hash block) in
×
246
        ( match List.length links with
×
247
        | 0 ->
×
248
            let size = Bigstring.length chunk in
249
            last_leaf_block_data_size :=
×
250
              if !last_leaf_block_data_size = 0 then size
×
251
              else min !last_leaf_block_data_size size
×
252
        | n when n = max_links_per_block ->
×
253
            incr num_full_branch_blocks
×
254
        | n -> (
×
255
            match !num_links_in_partial_branch_block with
256
            | Some _ ->
×
257
                failwith
258
                  "invalid blocks: only expected one outlying block with \
259
                   differing number of links"
260
            | None ->
×
261
                num_links_in_partial_branch_block := Some n ) ) ;
262
        List.iter links ~f:crawl
263
      in
264
      crawl root_hash ;
265
      { num_total_blocks
×
266
      ; num_full_branch_blocks = !num_full_branch_blocks
267
      ; num_links_in_partial_branch_block =
268
          Option.value !num_links_in_partial_branch_block ~default:0
×
269
      ; last_leaf_block_data_size = !last_leaf_block_data_size
270
      ; max_block_data_size = max_block_size
271
      ; max_links_per_block
272
      }
273

274
    let%test_unit "forall x: data_of_blocks (blocks_of_data x) = x" =
275
      Quickcheck.test For_tests.gen ~trials:100
×
276
        ~f:(fun (max_block_size, data) ->
277
          let blocks, root_block_hash = blocks_of_data ~max_block_size data in
×
278
          let result =
×
279
            Or_error.ok_exn (data_of_blocks blocks root_block_hash)
×
280
          in
281
          [%test_eq: Bigstring.t] data result )
×
282

283
    let%test_unit "forall x: schema_of_blocks (blocks_of_data x) = \
284
                   create_schema x" =
285
      Quickcheck.test For_tests.gen ~trials:100
×
286
        ~f:(fun (max_block_size, data) ->
287
          let schema = create_schema ~max_block_size (Bigstring.length data) in
×
288
          let blocks, root_block_hash = blocks_of_data ~max_block_size data in
×
289
          [%test_eq: schema] schema
×
290
            (schema_of_blocks ~max_block_size blocks root_block_hash) )
×
291

292
    let%test_unit "when x is aligned (has no partial branch block): \
293
                   data_of_blocks (blocks_of_data x) = x" =
294
      let max_block_size = 100 in
×
295
      let data_length = max_block_size * 10 in
296
      let data =
297
        Quickcheck.Generator.generate ~size:1
×
298
          ~random:(Splittable_random.State.of_int 0)
×
299
          (String.gen_with_length data_length Char.quickcheck_generator)
×
300
        |> Bigstring.of_string
301
      in
302
      assert (Bigstring.length data = data_length) ;
×
303
      let blocks, root_block_hash = blocks_of_data ~max_block_size data in
304
      let result = Or_error.ok_exn (data_of_blocks blocks root_block_hash) in
×
305
      Out_channel.flush Out_channel.stdout ;
×
306
      [%test_eq: Bigstring.t] data result
×
307
  end )
10✔
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc