t/t4216-log-bloom.sh

   1 #!/bin/sh
   2
   3 test_description='git log for a path with Bloom filters'
   4 GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main
   5 export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME
   6
   7 . ./test-lib.sh
   8 . "$TEST_DIRECTORY"/lib-chunk.sh
   9
  10 GIT_TEST_COMMIT_GRAPH=0
  11 GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=0
  12
  13 test_expect_success 'setup test - repo, commits, commit graph, log outputs' '
  14         git init &&
  15         mkdir A A/B A/B/C &&
  16         test_commit c1 A/file1 &&
  17         test_commit c2 A/B/file2 &&
  18         test_commit c3 A/B/C/file3 &&
  19         test_commit c4 A/file1 &&
  20         test_commit c5 A/B/file2 &&
  21         test_commit c6 A/B/C/file3 &&
  22         test_commit c7 A/file1 &&
  23         test_commit c8 A/B/file2 &&
  24         test_commit c9 A/B/C/file3 &&
  25         test_commit c10 file_to_be_deleted &&
  26         git checkout -b side HEAD~4 &&
  27         test_commit side-1 file4 &&
  28         git checkout main &&
  29         git merge side &&
  30         test_commit c11 file5 &&
  31         mv file5 file5_renamed &&
  32         git add file5_renamed &&
  33         git commit -m "rename" &&
  34         rm file_to_be_deleted &&
  35         git add . &&
  36         git commit -m "file removed" &&
  37         git commit --allow-empty -m "empty" &&
  38         git commit-graph write --reachable --changed-paths &&
  39
  40         test_oid_cache <<-EOF
  41         oid_version sha1:1
  42         oid_version sha256:2
  43         EOF
  44 '
  45
  46 graph_read_expect () {
  47         NUM_CHUNKS=6
  48         cat >expect <<- EOF
  49         header: 43475048 1 $(test_oid oid_version) $NUM_CHUNKS 0
  50         num_commits: $1
  51         chunks: oid_fanout oid_lookup commit_metadata generation_data bloom_indexes bloom_data
  52         options: bloom(1,10,7) read_generation_data
  53         EOF
  54         test-tool read-graph >actual &&
  55         test_cmp expect actual
  56 }
  57
  58 test_expect_success 'commit-graph write wrote out the bloom chunks' '
  59         graph_read_expect 16
  60 '
  61
  62 # Turn off any inherited trace2 settings for this test.
  63 sane_unset GIT_TRACE2 GIT_TRACE2_PERF GIT_TRACE2_EVENT
  64 sane_unset GIT_TRACE2_PERF_BRIEF
  65 sane_unset GIT_TRACE2_CONFIG_PARAMS
  66
  67 setup () {
  68         rm -f "$TRASH_DIRECTORY/trace.perf" &&
  69         git -c core.commitGraph=false log --pretty="format:%s" $1 >log_wo_bloom &&
  70         GIT_TRACE2_PERF="$TRASH_DIRECTORY/trace.perf" git -c core.commitGraph=true log --pretty="format:%s" $1 >log_w_bloom
  71 }
  72
  73 test_bloom_filters_used () {
  74         log_args=$1
  75         bloom_trace_prefix="statistics:{\"filter_not_present\":${2:-0},\"maybe\""
  76         setup "$log_args" &&
  77         grep -q "$bloom_trace_prefix" "$TRASH_DIRECTORY/trace.perf" &&
  78         test_cmp log_wo_bloom log_w_bloom &&
  79     test_path_is_file "$TRASH_DIRECTORY/trace.perf"
  80 }
  81
  82 test_bloom_filters_not_used () {
  83         log_args=$1
  84         setup "$log_args" &&
  85         ! grep -q "statistics:{\"filter_not_present\":" "$TRASH_DIRECTORY/trace.perf" &&
  86         test_cmp log_wo_bloom log_w_bloom
  87 }
  88
  89 for path in A A/B A/B/C A/file1 A/B/file2 A/B/C/file3 file4 file5 file5_renamed file_to_be_deleted
  90 do
  91         for option in "" \
  92               "--all" \
  93                       "--full-history" \
  94                       "--full-history --simplify-merges" \
  95                       "--simplify-merges" \
  96                       "--simplify-by-decoration" \
  97                       "--follow" \
  98                       "--first-parent" \
  99                       "--topo-order" \
 100                       "--date-order" \
 101                       "--author-date-order" \
 102                       "--ancestry-path side..main"
 103         do
 104                 test_expect_success "git log option: $option for path: $path" '
 105                         test_bloom_filters_used "$option -- $path" &&
 106                         test_config commitgraph.readChangedPaths false &&
 107                         test_bloom_filters_not_used "$option -- $path"
 108                 '
 109         done
 110 done
 111
 112 test_expect_success 'git log -- folder works with and without the trailing slash' '
 113         test_bloom_filters_used "-- A" &&
 114         test_bloom_filters_used "-- A/"
 115 '
 116
 117 test_expect_success 'git log for path that does not exist. ' '
 118         test_bloom_filters_used "-- path_does_not_exist"
 119 '
 120
 121 test_expect_success 'git log with --walk-reflogs does not use Bloom filters' '
 122         test_bloom_filters_not_used "--walk-reflogs -- A"
 123 '
 124
 125 test_expect_success 'git log -- multiple path specs does not use Bloom filters' '
 126         test_bloom_filters_not_used "-- file4 A/file1"
 127 '
 128
 129 test_expect_success 'git log -- "." pathspec at root does not use Bloom filters' '
 130         test_bloom_filters_not_used "-- ."
 131 '
 132
 133 test_expect_success 'git log with wildcard that resolves to a single path uses Bloom filters' '
 134         test_bloom_filters_used "-- *4" &&
 135         test_bloom_filters_used "-- *renamed"
 136 '
 137
 138 test_expect_success 'git log with wildcard that resolves to a multiple paths does not uses Bloom filters' '
 139         test_bloom_filters_not_used "-- *" &&
 140         test_bloom_filters_not_used "-- file*"
 141 '
 142
 143 test_expect_success 'setup - add commit-graph to the chain without Bloom filters' '
 144         test_commit c14 A/anotherFile2 &&
 145         test_commit c15 A/B/anotherFile2 &&
 146         test_commit c16 A/B/C/anotherFile2 &&
 147         git commit-graph write --reachable --split --no-changed-paths &&
 148         test_line_count = 2 .git/objects/info/commit-graphs/commit-graph-chain
 149 '
 150
 151 test_expect_success 'use Bloom filters even if the latest graph does not have Bloom filters' '
 152         # Ensure that the number of empty filters is equal to the number of
 153         # filters in the latest graph layer to prove that they are loaded (and
 154         # ignored).
 155         test_bloom_filters_used "-- A/B" 3
 156 '
 157
 158 test_expect_success 'setup - add commit-graph to the chain with Bloom filters' '
 159         test_commit c17 A/anotherFile3 &&
 160         git commit-graph write --reachable --changed-paths --split &&
 161         test_line_count = 3 .git/objects/info/commit-graphs/commit-graph-chain
 162 '
 163
 164 test_bloom_filters_used_when_some_filters_are_missing () {
 165         log_args=$1
 166         bloom_trace_prefix="statistics:{\"filter_not_present\":3,\"maybe\":6,\"definitely_not\":9"
 167         setup "$log_args" &&
 168         grep -q "$bloom_trace_prefix" "$TRASH_DIRECTORY/trace.perf" &&
 169         test_cmp log_wo_bloom log_w_bloom
 170 }
 171
 172 test_expect_success 'Use Bloom filters if they exist in the latest but not all commit graphs in the chain.' '
 173         test_bloom_filters_used_when_some_filters_are_missing "-- A/B"
 174 '
 175
 176 test_expect_success 'persist filter settings' '
 177         test_when_finished rm -rf .git/objects/info/commit-graph* &&
 178         rm -rf .git/objects/info/commit-graph* &&
 179         GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
 180                 GIT_TEST_BLOOM_SETTINGS_NUM_HASHES=9 \
 181                 GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY=15 \
 182                 git commit-graph write --reachable --changed-paths &&
 183         grep "{\"hash_version\":1,\"num_hashes\":9,\"bits_per_entry\":15,\"max_changed_paths\":512" trace2.txt &&
 184         GIT_TRACE2_EVENT="$(pwd)/trace2-auto.txt" \
 185                 git commit-graph write --reachable --changed-paths &&
 186         grep "{\"hash_version\":1,\"num_hashes\":9,\"bits_per_entry\":15,\"max_changed_paths\":512" trace2-auto.txt
 187 '
 188
 189 test_max_changed_paths () {
 190         grep "\"max_changed_paths\":$1" $2
 191 }
 192
 193 test_filter_not_computed () {
 194         grep "\"key\":\"filter-not-computed\",\"value\":\"$1\"" $2
 195 }
 196
 197 test_filter_computed () {
 198         grep "\"key\":\"filter-computed\",\"value\":\"$1\"" $2
 199 }
 200
 201 test_filter_trunc_empty () {
 202         grep "\"key\":\"filter-trunc-empty\",\"value\":\"$1\"" $2
 203 }
 204
 205 test_filter_trunc_large () {
 206         grep "\"key\":\"filter-trunc-large\",\"value\":\"$1\"" $2
 207 }
 208
 209 test_expect_success 'correctly report changes over limit' '
 210         git init limits &&
 211         (
 212                 cd limits &&
 213                 mkdir d &&
 214                 mkdir d/e &&
 215
 216                 for i in $(test_seq 1 2)
 217                 do
 218                         printf $i >d/file$i.txt &&
 219                         printf $i >d/e/file$i.txt || return 1
 220                 done &&
 221
 222                 mkdir mode &&
 223                 printf bash >mode/script.sh &&
 224
 225                 mkdir foo &&
 226                 touch foo/bar &&
 227                 touch foo.txt &&
 228
 229                 git add d foo foo.txt mode &&
 230                 git commit -m "files" &&
 231
 232                 # Commit has 7 file and 4 directory adds
 233                 GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS=10 \
 234                         GIT_TRACE2_EVENT="$(pwd)/trace" \
 235                         git commit-graph write --reachable --changed-paths &&
 236                 test_max_changed_paths 10 trace &&
 237                 test_filter_computed 1 trace &&
 238                 test_filter_trunc_large 1 trace &&
 239
 240                 for path in $(git ls-tree -r --name-only HEAD)
 241                 do
 242                         git -c commitGraph.readChangedPaths=false log \
 243                                 -- $path >expect &&
 244                         git log -- $path >actual &&
 245                         test_cmp expect actual || return 1
 246                 done &&
 247
 248                 # Make a variety of path changes
 249                 printf new1 >d/e/file1.txt &&
 250                 printf new2 >d/file2.txt &&
 251                 rm d/e/file2.txt &&
 252                 rm -r foo &&
 253                 printf text >foo &&
 254                 mkdir f &&
 255                 printf new1 >f/file1.txt &&
 256
 257                 # including a mode-only change (counts as modified)
 258                 git update-index --chmod=+x mode/script.sh &&
 259
 260                 git add foo d f &&
 261                 git commit -m "complicated" &&
 262
 263                 # start from scratch and rebuild
 264                 rm -f .git/objects/info/commit-graph &&
 265                 GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS=10 \
 266                         GIT_TRACE2_EVENT="$(pwd)/trace-edit" \
 267                         git commit-graph write --reachable --changed-paths &&
 268                 test_max_changed_paths 10 trace-edit &&
 269                 test_filter_computed 2 trace-edit &&
 270                 test_filter_trunc_large 2 trace-edit &&
 271
 272                 for path in $(git ls-tree -r --name-only HEAD)
 273                 do
 274                         git -c commitGraph.readChangedPaths=false log \
 275                                 -- $path >expect &&
 276                         git log -- $path >actual &&
 277                         test_cmp expect actual || return 1
 278                 done &&
 279
 280                 # start from scratch and rebuild
 281                 rm -f .git/objects/info/commit-graph &&
 282                 GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS=11 \
 283                         GIT_TRACE2_EVENT="$(pwd)/trace-update" \
 284                         git commit-graph write --reachable --changed-paths &&
 285                 test_max_changed_paths 11 trace-update &&
 286                 test_filter_computed 2 trace-update &&
 287                 test_filter_trunc_large 0 trace-update &&
 288
 289                 for path in $(git ls-tree -r --name-only HEAD)
 290                 do
 291                         git -c commitGraph.readChangedPaths=false log \
 292                                 -- $path >expect &&
 293                         git log -- $path >actual &&
 294                         test_cmp expect actual || return 1
 295                 done
 296         )
 297 '
 298
 299 test_expect_success 'correctly report commits with no changed paths' '
 300         git init empty &&
 301         test_when_finished "rm -fr empty" &&
 302         (
 303                 cd empty &&
 304
 305                 git commit --allow-empty -m "initial commit" &&
 306
 307                 GIT_TRACE2_EVENT="$(pwd)/trace.event" \
 308                         git commit-graph write --reachable --changed-paths &&
 309                 test_filter_computed 1 trace.event &&
 310                 test_filter_not_computed 0 trace.event &&
 311                 test_filter_trunc_empty 1 trace.event &&
 312                 test_filter_trunc_large 0 trace.event
 313         )
 314 '
 315
 316 test_expect_success 'Bloom generation is limited by --max-new-filters' '
 317         (
 318                 cd limits &&
 319                 test_commit c2 filter &&
 320                 test_commit c3 filter &&
 321                 test_commit c4 no-filter &&
 322
 323                 rm -f trace.event &&
 324                 GIT_TRACE2_EVENT="$(pwd)/trace.event" \
 325                         git commit-graph write --reachable --split=replace \
 326                                 --changed-paths --max-new-filters=2 &&
 327
 328                 test_filter_computed 2 trace.event &&
 329                 test_filter_not_computed 3 trace.event &&
 330                 test_filter_trunc_empty 0 trace.event &&
 331                 test_filter_trunc_large 0 trace.event
 332         )
 333 '
 334
 335 test_expect_success 'Bloom generation backfills previously-skipped filters' '
 336         # Check specifying commitGraph.maxNewFilters over "git config" works.
 337         test_config -C limits commitGraph.maxNewFilters 1 &&
 338         (
 339                 cd limits &&
 340
 341                 rm -f trace.event &&
 342                 GIT_TRACE2_EVENT="$(pwd)/trace.event" \
 343                         git commit-graph write --reachable --changed-paths \
 344                                 --split=replace &&
 345                 test_filter_computed 1 trace.event &&
 346                 test_filter_not_computed 4 trace.event &&
 347                 test_filter_trunc_empty 0 trace.event &&
 348                 test_filter_trunc_large 0 trace.event
 349         )
 350 '
 351
 352 test_expect_success '--max-new-filters overrides configuration' '
 353         git init override &&
 354         test_when_finished "rm -fr override" &&
 355         test_config -C override commitGraph.maxNewFilters 2 &&
 356         (
 357                 cd override &&
 358                 test_commit one &&
 359                 test_commit two &&
 360
 361                 rm -f trace.event &&
 362                 GIT_TRACE2_EVENT="$(pwd)/trace.event" \
 363                         git commit-graph write --reachable --changed-paths \
 364                                 --max-new-filters=1 &&
 365                 test_filter_computed 1 trace.event &&
 366                 test_filter_not_computed 1 trace.event &&
 367                 test_filter_trunc_empty 0 trace.event &&
 368                 test_filter_trunc_large 0 trace.event
 369         )
 370 '
 371
 372 test_expect_success 'Bloom generation backfills empty commits' '
 373         git init empty &&
 374         test_when_finished "rm -fr empty" &&
 375         (
 376                 cd empty &&
 377                 for i in $(test_seq 1 6)
 378                 do
 379                         git commit --allow-empty -m "$i" || return 1
 380                 done &&
 381
 382                 # Generate Bloom filters for empty commits 1-6, two at a time.
 383                 for i in $(test_seq 1 3)
 384                 do
 385                         rm -f trace.event &&
 386                         GIT_TRACE2_EVENT="$(pwd)/trace.event" \
 387                                 git commit-graph write --reachable \
 388                                         --changed-paths --max-new-filters=2 &&
 389                         test_filter_computed 2 trace.event &&
 390                         test_filter_not_computed 4 trace.event &&
 391                         test_filter_trunc_empty 2 trace.event &&
 392                         test_filter_trunc_large 0 trace.event || return 1
 393                 done &&
 394
 395                 # Finally, make sure that once all commits have filters, that
 396                 # none are subsequently recomputed.
 397                 rm -f trace.event &&
 398                 GIT_TRACE2_EVENT="$(pwd)/trace.event" \
 399                         git commit-graph write --reachable \
 400                                 --changed-paths --max-new-filters=2 &&
 401                 test_filter_computed 0 trace.event &&
 402                 test_filter_not_computed 6 trace.event &&
 403                 test_filter_trunc_empty 0 trace.event &&
 404                 test_filter_trunc_large 0 trace.event
 405         )
 406 '
 407
 408 corrupt_graph () {
 409         graph=.git/objects/info/commit-graph &&
 410         test_when_finished "rm -rf $graph" &&
 411         git commit-graph write --reachable --changed-paths &&
 412         corrupt_chunk_file $graph "$@"
 413 }
 414
 415 check_corrupt_graph () {
 416         corrupt_graph "$@" &&
 417         git -c core.commitGraph=false log -- A/B/file2 >expect.out &&
 418         git -c core.commitGraph=true log -- A/B/file2 >out 2>err &&
 419         test_cmp expect.out out
 420 }
 421
 422 test_expect_success 'Bloom reader notices too-small data chunk' '
 423         check_corrupt_graph BDAT clear 00000000 &&
 424         echo "warning: ignoring too-small changed-path chunk" \
 425                 "(4 < 12) in commit-graph file" >expect.err &&
 426         test_cmp expect.err err
 427 '
 428
 429 test_expect_success 'Bloom reader notices out-of-bounds filter offsets' '
 430         check_corrupt_graph BIDX 12 FFFFFFFF &&
 431         # use grep to avoid depending on exact chunk size
 432         grep "warning: ignoring out-of-range offset (4294967295) for changed-path filter at pos 3 of .git/objects/info/commit-graph" err
 433 '
 434
 435 test_expect_success 'Bloom reader notices too-small index chunk' '
 436         # replace the index with a single entry, making most
 437         # lookups out-of-bounds
 438         check_corrupt_graph BIDX clear 00000000 &&
 439         echo "warning: commit-graph changed-path index chunk" \
 440                 "is too small" >expect.err &&
 441         test_cmp expect.err err
 442 '
 443
 444 test_expect_success 'Bloom reader notices out-of-order index offsets' '
 445         # we do not know any real offsets, but we can pick
 446         # something plausible; we should not get to the point of
 447         # actually reading from the bogus offsets anyway.
 448         corrupt_graph BIDX 4 0000000c00000005 &&
 449         echo "warning: ignoring decreasing changed-path index offsets" \
 450                 "(12 > 5) for positions 1 and 2 of .git/objects/info/commit-graph" >expect.err &&
 451         git -c core.commitGraph=false log -- A/B/file2 >expect.out &&
 452         git -c core.commitGraph=true log -- A/B/file2 >out 2>err &&
 453         test_cmp expect.out out &&
 454         test_cmp expect.err err
 455 '
 456
 457 test_done