bvt's backtrace

I hope this will be one of the last updates to v.sh: I will add two vpatches, one for handling orphan vpatches, and an update of bundled SMG.Keccak to the latest version.

---

An orphaned vpatch (or orphan) is a vpatch that is missing some of its antecedents, and therefore cannot be pressed. Current behavior in this case is to crash hard via an exception in vflow, which v.sh does not handle gracefully. This is not helpful at all, since the user is stuck figuring out what went wrong manually. The intention of this vpatch is to correct this oversight.

    Vpatch_Dependencies: Vpatch_Relationship := (others => (others => False));
    Vpatch_Conflicts   : Vpatch_Relationship := (others => (others => False));
    Vpatch_Order       : Vpatch_List         := (others => 0);
+   Vpatch_Orphans     : Vpatch_Set          := (others => False);

    function Get_Hunk return Hunk is
       H: Hunk;

Vpatch_Orphans represents a set of orphan vpatches, initially empty.

 	    -- Looped through all vpatches, there are hunks without matched inputs:
 	    if not Finished then
-	       raise Constraint_Error with "Unsatisfied hunks.";
+	       Put_Line("O " & Integer'Image(I));
+	       Vpatch_Orphans(I) := True;
 	    end if;
 	 end;
       end loop;

Upon detecting an orphan vpatch, it is added to the set, and reported to the output with "O" prefix.

       -- Check if there are still free vpatches (there is a loop):
       for I in Free_Vpatches'Range loop
-	 if Free_Vpatches(I) then
+	 if Free_Vpatches(I) and not Vpatch_Orphans(I) then
 	    Put_Line("L " & Integer'Image(I));
 	    Has_Loops := True;
 	 end if;

Orphan vpatches may end up outside of the normal vpatch flow, where they could be mixed up with vpatches that form a loop. Print the looping vpatches separately from the orphans.

       procedure Add_Dependencies is
-	 Finish : Boolean := False;
       begin
-	 while not Finish loop
-	    Finish := True;
-	    for I in Selected_Vpatches'Range loop
-	       if Selected_Vpatches(I) then
-		  for J in Vpatch_Dependencies'Range(2) loop
-		     if Vpatch_Dependencies(I,J) and not Selected_Vpatches(J) then
-			Finish := False;
-			Selected_Vpatches(J) := True;
-		     end if;
-		  end loop;
-	       end if;
-	    end loop;
+	 -- loop forward propagating orphans
+	 for I in Vpatch_Order'Range loop
+	    declare
+	       V : Vpatch_Index := Vpatch_Order(I);
+	    begin
+	       for J in Vpatch_Dependencies'Range(2) loop
+		  if Vpatch_Dependencies(V,J) and Vpatch_Orphans(J) then
+		     Vpatch_Orphans(V) := True;
+		  end if;
+	       end loop;
+	    end;
+	 end loop;
+
+	 for I in reverse Vpatch_Order'Range loop
+	    declare
+	       V : Vpatch_Index := Vpatch_Order(I);
+	    begin
+	       for J in Vpatch_Dependencies'Range(1) loop
+		  if Vpatch_Dependencies(J,V) and Selected_Vpatches(J) then
+		     Selected_Vpatches(V) := True;
+		  end if;
+	       end loop;
+	    end;
 	 end loop;
       end Add_Dependencies;

Add_Dependencies added the antecendents of vpatches manually selected for pressing to the set of vpatches that will be pressed. Here, we first "propagate" the membership in the ophaned set to the descendants, then membership in the selected set to the antecedents. Because the flow is avalailable at this point, I also changed the backward propagation algorithm for selection to a simpler one.

+      procedure Print_Heads is
+      begin
+	 for I in Vpatch_Dependencies'Range(2) loop
+	    declare
+	       Is_Head : Boolean := not Vpatch_Orphans(I);
+	    begin
+	       for J in Vpatch_Dependencies'Range(1) loop
+		  Is_Head := Is_Head and
+		    (not Vpatch_Dependencies(J,I) or Vpatch_Orphans(J));
+	       end loop;
+	       if Is_Head then
+		  Put_Line("H " & Integer'Image(I));
+	       end if;
+	    end;
+	 end loop;
+      end Print_Heads;

When orphaned vpatches are in the tree, the naive heads calculation previously present in v.sh does not work, because a vpatch without descendants (which awk code would mark as head) may be orphaned, and correctly handling this case in awk would require reconstructing dependency table and orphan set there. It is actually simpler just do the calculation in vflow.

@@ -399,18 +429,27 @@
 	 end loop;

 	 for I in Vpatch_Order'Range loop
-	    if Selected_Vpatches(Vpatch_Order(I)) then
-	       Put_Line("P " & Integer'Image(Vpatch_Order(I)));
-	    else
-	       Put_Line("p " & Integer'Image(Vpatch_Order(I)));
-	    end if;
+	    declare
+	       V : Vpatch_Index := Vpatch_Order(I);
+	    begin
+	       if        Selected_Vpatches(V) and not Vpatch_Orphans(V) then
+		  Put_Line("P " & Integer'Image(V));
+	       elsif     Selected_Vpatches(V) and     Vpatch_Orphans(V) then
+		  Put_Line("E " & Integer'Image(V));
+	       elsif not Selected_Vpatches(V) and not Vpatch_Orphans(V) then
+		  Put_Line("p " & Integer'Image(V));
+	       else
+		  Put_Line("e " & Integer'Image(V));
+	       end if;
+	    end;
 	 end loop;
-      end Print_Flow_Or_Conflicts;
+      end Print_Flow_And_Conflicts;

When reporting the press order, orphaned vpatches are marked with "E" or "e" depending if they are selected for pressing or not.

v.sh is also updated accordingly:

 set -e

+[ -n "$VERBOSE" ] && set -x
+
 allkeyword="all"

 vgpgdir=""

Setting VERBOSE environment variable enables output of executed commands to stderr. This is ~unrelated functionality, however it is useful for debugging unexpected crashes -- and crashes due to an orphan vpatch were unexpected to me.

+report_vpatches() {
+    >&2 printf "$1"
+    awk -v L="$2" '$1 == L {print $2}' < "$topo" | vpatchnames >&2
+}

A new function for simplifying error reporting in vpatchflowerr.

 vpatchflowerr() {
     set +e
     awk 'BEGIN {err=0; ok=0;}
 err == 0 && $1 == "C" {err=1; ech=$1;}
 err == 0 && $1 == "L" {err=2; ech=$1;}
+err == 0 && $1 == "E" {err=3; ech=$1;}
 err == 0 && $1 == "P" {ok=1;}
-END {if (err != 0) exit err; if (ok != 1) exit 3; exit 0;}' <"$topo"
+END {if (err != 0) exit err; if (ok != 1) exit 4; exit 0;}' <"$topo"
     exitcode="$?"
     set -e
     if [ "$exitcode" -eq "1" ]; then
 	    >&2 printf "Conflicting leaves selected:\n"
 	    awk '$1 == "C" {print $2}' < "$topo" | vpatchnames | sort | uniq >&2
-	    >&2 printf "Available heads:\n"
-	    awk '
-($1 == "I" || $1 == "d" ) {non_terminals[$3]=1;}
-($1 == "P") {if (!($2 in non_terminals)) {print $2;}}' < "$topo" | vpatchnames >&2
+	    report_vpatches "Orphans:\n" "O"
+	    report_vpatches "Available heads:\n" "H"
 	    fail
     elif [ "$exitcode" -eq "2" ]; then
-	    >&2 printf "Loop among vpatches:\n"
-	    awk '{print $2}' < "$topo" | vpatchnames >&2
+	    report_vpatches "Loop among vpatches:\n" "L"
 	    fail
     elif [ "$exitcode" -eq "3" ]; then
+	    report_vpatches "Orphan vpatches selected:\n" "E"
+	    report_vpatches "Available heads:\n" "H"
+	    fail
+    elif [ "$exitcode" -eq "4" ]; then
 	    >&2 echo "Unknown error. Investigate in $vgpgdir:"
 	    >&2 cat "$topo"
 	    exit 1 # no cleanup

The error reporting code got updated, first to use the new report_vpatches function, second, to get heads using "H" prefixed lines instead of calculating them manually.

 	cat >"$dotfile" < \""a[$2]"\""}
 FILENAME=="-" && $1 == "d" {print "\""a[$3]"\" -> \""a[$2]"\""}
 ' "$vpatches" - <"$topo" >>"$dotfile"
 	echo "}" >> "$dotfile"

Also show orphans in the graph. They are shown as descendants of an invisible node.

 function max(a,b) { return (a > b) ? a : b;}
 function repeat(s,n) {i=0; while (i++ < n) {printf("%s",s);}}
 FILENAME==VF {names[$2]=$1}
-FILENAME=="-" && ($1 == "I" || $1 == "d" ) {non_terminals[$3]=1;}
+FILENAME=="-" && ($1 == "O") {print "Orphan:", names[$2]; orphans[$2]=1;}
+FILENAME=="-" && ($1 == "H" ) {heads[$2]=1;}
 FILENAME=="-" && ($1 == "d") {if (!($2 in n_ante)) n_ante[$2] = 0; dir_ante[$2][n_ante[$2]] = $3; n_ante[$2]++;}
-FILENAME=="-" && ($1 == "P" || $1 == "p") {
+FILENAME=="-" && ($1 == "P" || $1 == "p" || $1 == "E" || $1 == "e") {
    level[$2] = 0;
    if ($2 in n_ante) {
       for (i = 0; i < n_ante[$2]; i++) {
@@ -295,7 +307,8 @@
       }
    }
    repeat(" ", level[$2]);
-   printf("%s%s%s\n",names[$2], ($2 in non_terminals) ? "" : " (*)", ($1 == "P") ? " +" : "" );
+   if ($1 =="E" || $1 == "e") printf("O: ");
+   printf("%s%s%s\n",names[$2], ($2 in heads) ? " (*)" : "", ($1 == "P") ? " +" : "" );
 }' "$vpatches" - <"$topo"
 	exit_success
 fi

And an update to the "vtree" command, which now also reports orphans and gets the list of heads the new way.

---

The update to the latest code SMG.Keccak is much simpler, so I won't show the code, the only interesting bit was that I got confused with all the endianness conversion in bitwise and bytewise Keccak. As the sponge function output was previously an array of bits, the user had to reconstruct the byte value himself. In the new code, the value is in bytes, but it is not directly usable on little-endian machines, and must be reversed. I followed the advise of Diana and just removed the conversion to bit reversal in the smg_keccak.adb.

Another change that I did was to switch all binary vtools to compile with optimizations, like so:

project Ksum is
  for Languages use ("Ada");
  for Source_Dirs use ("src");
  for Object_Dir use "obj";
  for Exec_Dir use ".";
  for Main use ("ksum.adb");

  type Mode_Type is ("debug", "release");
  Mode : Mode_Type := external ("mode", "release");

  package Compiler is
      case Mode is
         when "debug" =>
            for Switches ("Ada")
                use ("-O2", "-ggdb3");
         when "release" =>
            for Switches ("Ada")
                use ("-O2");
      end case;
  end Compiler;

  package Binder is
     for Switches ("Ada") use ("-static");
  end Binder;

  package Linker is
     for Switches ("Ada") use ("-static");
  end Linker;
end Ksum;

The effects of these changes are rather nice, I was in the error previously when I thought that "noone will notice", as 2.5x speedup from this change is quite easy to notice:

$ time ksum.old ksum
08ffc69748db90b48fc2813abf40b6123798f4e99f7cddbe02f5547ec2e0504b1af5e2e8d87b108e1e18b128c21fc67c40f34facf73314d5a86cea8b2ce7d762  ksum
ksum.old ksum  1.41s user 0.01s system 90% cpu 1.566 total
$ time ksum.new ksum
08ffc69748db90b48fc2813abf40b6123798f4e99f7cddbe02f5547ec2e0504b1af5e2e8d87b108e1e18b128c21fc67c40f34facf73314d5a86cea8b2ce7d762  ksum
ksum.new ksum  0.50s user 0.00s system 94% cpu 0.532 total

OTOH, vdiff still spends ~90% CPU time in the Keccak code, so perhaps some more performance can be extracted. This would help working with e.g. Linux kernel or MPWP even more.

# Overhead  Command  Shared Object     Symbol
# ........  .......  ................  ........................................
#
    53.90%  vdiff    vdiff             [.] smg_keccak__rho
    18.08%  vdiff    vdiff             [.] smg_keccak__keccak_function
    12.65%  vdiff    vdiff             [.] smg_keccak__chi
    10.85%  vdiff    vdiff             [.] smg_keccak__theta
     1.81%  vdiff    vdiff             [.] keccak_hash
     0.90%  vdiff    vdiff             [.] bits__tobytestream
     0.90%  vdiff    [kernel.vmlinux]  [k] do_syscall_64
     0.90%  vdiff    [kernel.vmlinux]  [k] get_page_from_freelist
     0.00%  vdiff    vdiff             [.] read_files
     0.00%  vdiff    vdiff             [.] smg_keccak__absorbblock
     0.00%  vdiff    vdiff             [.] smg_keccak__keccakhash
     0.00%  vdiff    [kernel.vmlinux]  [k] copy_user_enhanced_fast_string
     0.00%  vdiff    vdiff             [.] memcpy
     0.00%  vdiff    vdiff             [.] memcmp
     0.00%  vdiff    vdiff             [.] diff_2_files
     0.00%  vdiff    [kernel.vmlinux]  [k] syscall_return_via_sysret
     0.00%  vdiff    [kernel.vmlinux]  [k] entry_SYSCALL_64
     0.00%  vdiff    vdiff             [.] memchr
     0.00%  vdiff    vdiff             [.] smg_keccak__squeezeblock
     0.00%  vdiff    vdiff             [.] free
     0.00%  vdiff    [kernel.vmlinux]  [k] __d_lookup_rcu

Vpatches and signatures:

curl 'http://bvt-trace.net/vpatches/vtools_vsh_orphans.vpatch' > vtools_vsh_orphans.vpatch
curl 'http://bvt-trace.net/vpatches/vtools_vsh_orphans.vpatch.bvt.sig' > vtools_vsh_orphans.vpatch.bvt.sig
curl 'http://bvt-trace.net/vpatches/vtools_update_keccak.vpatch' > vtools_update_keccak.vpatch
curl 'http://bvt-trace.net/vpatches/vtools_update_keccak.vpatch.bvt.sig' > vtools_update_keccak.vpatch.bvt.sig

This article was published on Friday, April 10th, 2020 at 16:43 and is filed under Ada. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.