Generate .build-id directory tree after every build.

The .build-id directory tree is as described here:
https://fedoraproject.org/wiki/RolandMcGrath/BuildID

Tools such as llvm-symbolizer understand this tree and can use it
to look up symbols by build ID. This CL adds a post-build step that
updates the .build-id directory under symbols after every build if
necessary to contain symlinks to the corresponding symbols file.

I also considered adding this as a build step after copying the symbol
file to the symbols directory. However this would be complicated
by the fact that many binaries have the same build-id such as the
various copies of libc++ for the different APEXes. As a result it
would be difficult to implement a .build-id updater that produces a
correct symlink tree while taking into account concurrent updates to
the same symlink by different build steps. This situation is resolved
in the .build-id directory generator by having the symlink point to
the lexically smallest path out of all paths with the same build-id.

I measured the performance of the UpdateBuildIdDir function by writing
a standalone program that just calls the function and running it over
a copy of the symbols directory for a specific target. On my machine
the execution time of the program when simulating various scenarios
was as follows:

Null build [1]:             36.2 ms ±   3.4 ms
Initial build [2]:         162.3 ms ±   6.6 ms
Single update [3]:         128.0 ms ±   6.1 ms
Invalid .build-id dir [4]: 222.6 ms ±   8.6 ms

This is with some improvements that have been contributed to the Go
standard library [5,6]; without those improvements a null build is
37.9 ms ± 4.4 ms and a single update is 143.9 ms ± 4.5 ms.

[1] hyperfine './update-build-id ~/2/test-symbols2/'
[2] hyperfine -p 'rm -rf ~/2/test-symbols2/.build-id' './update-build-id ~/2/test-symbols2/'
[3] hyperfine -p 'dd if=/dev/urandom of=$HOME/2/test-symbols2/system/bin/init conv=notrunc seek=808 bs=1 count=16' './update-build-id ~/2/test-symbols2/'
[4] hyperfine -p 'touch ~/2/test-symbols2/.build-id/corrupt; sleep 0.1; touch ~/2/test-symbols2/system/bin/init' './update-build-id ~/2/test-symbols2/'
[5] https://go.dev/cl/570877
[6] https://go.dev/cl/571436

Bug: 328702178
Change-Id: I8fc0ea81bd31ec80d6b912ba477e2e24b6b05f68

2 files changed, 173 insertions, 0 deletions

diff --git a/elf/Android.bp b/elf/Android.bp
index 6450be137..6d3f4f0ed 100644
--- a/elf/Android.bp
+++ b/elf/Android.bp
@@ -20,6 +20,7 @@ bootstrap_go_package {
     name: "soong-elf",
     pkgPath: "android/soong/elf",
     srcs: [
+        "build_id_dir.go",
         "elf.go",
     ],
     testSrcs: [
diff --git a/elf/build_id_dir.go b/elf/build_id_dir.go
new file mode 100644
index 000000000..5fb7dda87
--- /dev/null
+++ b/elf/build_id_dir.go
@@ -0,0 +1,172 @@
+// Copyright 2024 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package elf
+
+import (
+	"io/fs"
+	"os"
+	"path/filepath"
+	"strings"
+	"sync"
+	"time"
+)
+
+func UpdateBuildIdDir(path string) error {
+	path = filepath.Clean(path)
+	buildIdPath := path + "/.build-id"
+
+	// Collect the list of files and build-id symlinks. If the symlinks are
+	// up to date (newer than the symbol files), there is nothing to do.
+	var buildIdFiles, symbolFiles []string
+	var buildIdMtime, symbolsMtime time.Time
+	filepath.WalkDir(path, func(path string, entry fs.DirEntry, err error) error {
+		if entry == nil || entry.IsDir() {
+			return nil
+		}
+		info, err := entry.Info()
+		if err != nil {
+			return err
+		}
+		mtime := info.ModTime()
+		if strings.HasPrefix(path, buildIdPath) {
+			if buildIdMtime.Compare(mtime) < 0 {
+				buildIdMtime = mtime
+			}
+			buildIdFiles = append(buildIdFiles, path)
+		} else {
+			if symbolsMtime.Compare(mtime) < 0 {
+				symbolsMtime = mtime
+			}
+			symbolFiles = append(symbolFiles, path)
+		}
+		return nil
+	})
+	if symbolsMtime.Compare(buildIdMtime) < 0 {
+		return nil
+	}
+
+	// Collect build-id -> file mapping from ELF files in the symbols directory.
+	concurrency := 8
+	done := make(chan error)
+	buildIdToFile := make(map[string]string)
+	var mu sync.Mutex
+	for i := 0; i != concurrency; i++ {
+		go func(paths []string) {
+			for _, path := range paths {
+				id, err := Identifier(path, true)
+				if err != nil {
+					done <- err
+					return
+				}
+				if id == "" {
+					continue
+				}
+				mu.Lock()
+				oldPath := buildIdToFile[id]
+				if oldPath == "" || oldPath > path {
+					buildIdToFile[id] = path
+				}
+				mu.Unlock()
+			}
+			done <- nil
+		}(symbolFiles[len(symbolFiles)*i/concurrency : len(symbolFiles)*(i+1)/concurrency])
+	}
+
+	// Collect previously generated build-id -> file mapping from the .build-id directory.
+	// We will use this for incremental updates. If we see anything in the .build-id
+	// directory that we did not expect, we'll delete it and start over.
+	prevBuildIdToFile := make(map[string]string)
+out:
+	for _, buildIdFile := range buildIdFiles {
+		if !strings.HasSuffix(buildIdFile, ".debug") {
+			prevBuildIdToFile = nil
+			break
+		}
+		buildId := buildIdFile[len(buildIdPath)+1 : len(buildIdFile)-6]
+		for i, ch := range buildId {
+			if i == 2 {
+				if ch != '/' {
+					prevBuildIdToFile = nil
+					break out
+				}
+			} else {
+				if (ch < '0' || ch > '9') && (ch < 'a' || ch > 'f') {
+					prevBuildIdToFile = nil
+					break out
+				}
+			}
+		}
+		target, err := os.Readlink(buildIdFile)
+		if err != nil || !strings.HasPrefix(target, "../../") {
+			prevBuildIdToFile = nil
+			break
+		}
+		prevBuildIdToFile[buildId[0:2]+buildId[3:]] = path + target[5:]
+	}
+	if prevBuildIdToFile == nil {
+		err := os.RemoveAll(buildIdPath)
+		if err != nil {
+			return err
+		}
+		prevBuildIdToFile = make(map[string]string)
+	}
+
+	// Wait for build-id collection from ELF files to finish.
+	for i := 0; i != concurrency; i++ {
+		err := <-done
+		if err != nil {
+			return err
+		}
+	}
+
+	// Delete old symlinks.
+	for id, _ := range prevBuildIdToFile {
+		if buildIdToFile[id] == "" {
+			symlinkDir := buildIdPath + "/" + id[:2]
+			symlinkPath := symlinkDir + "/" + id[2:] + ".debug"
+			if err := os.Remove(symlinkPath); err != nil {
+				return err
+			}
+		}
+	}
+
+	// Add new symlinks and update changed symlinks.
+	for id, path := range buildIdToFile {
+		prevPath := prevBuildIdToFile[id]
+		if prevPath == path {
+			continue
+		}
+		symlinkDir := buildIdPath + "/" + id[:2]
+		symlinkPath := symlinkDir + "/" + id[2:] + ".debug"
+		if prevPath == "" {
+			if err := os.MkdirAll(symlinkDir, 0755); err != nil {
+				return err
+			}
+		} else {
+			if err := os.Remove(symlinkPath); err != nil {
+				return err
+			}
+		}
+
+		target, err := filepath.Rel(symlinkDir, path)
+		if err != nil {
+			return err
+		}
+		if err := os.Symlink(target, symlinkPath); err != nil {
+			return err
+		}
+	}
+	return nil
+}