| package btf |
| |
| import ( |
| "bufio" |
| "bytes" |
| "errors" |
| "fmt" |
| "io" |
| "strings" |
| |
| "golang.org/x/exp/maps" |
| ) |
| |
| type stringTable struct { |
| base *stringTable |
| offsets []uint32 |
| strings []string |
| } |
| |
| // sizedReader is implemented by bytes.Reader, io.SectionReader, strings.Reader, etc. |
| type sizedReader interface { |
| io.Reader |
| Size() int64 |
| } |
| |
| func readStringTable(r sizedReader, base *stringTable) (*stringTable, error) { |
| // When parsing split BTF's string table, the first entry offset is derived |
| // from the last entry offset of the base BTF. |
| firstStringOffset := uint32(0) |
| if base != nil { |
| idx := len(base.offsets) - 1 |
| firstStringOffset = base.offsets[idx] + uint32(len(base.strings[idx])) + 1 |
| } |
| |
| // Derived from vmlinux BTF. |
| const averageStringLength = 16 |
| |
| n := int(r.Size() / averageStringLength) |
| offsets := make([]uint32, 0, n) |
| strings := make([]string, 0, n) |
| |
| offset := firstStringOffset |
| scanner := bufio.NewScanner(r) |
| scanner.Split(splitNull) |
| for scanner.Scan() { |
| str := scanner.Text() |
| offsets = append(offsets, offset) |
| strings = append(strings, str) |
| offset += uint32(len(str)) + 1 |
| } |
| if err := scanner.Err(); err != nil { |
| return nil, err |
| } |
| |
| if len(strings) == 0 { |
| return nil, errors.New("string table is empty") |
| } |
| |
| if firstStringOffset == 0 && strings[0] != "" { |
| return nil, errors.New("first item in string table is non-empty") |
| } |
| |
| return &stringTable{base, offsets, strings}, nil |
| } |
| |
| func splitNull(data []byte, atEOF bool) (advance int, token []byte, err error) { |
| i := bytes.IndexByte(data, 0) |
| if i == -1 { |
| if atEOF && len(data) > 0 { |
| return 0, nil, errors.New("string table isn't null terminated") |
| } |
| return 0, nil, nil |
| } |
| |
| return i + 1, data[:i], nil |
| } |
| |
| func (st *stringTable) Lookup(offset uint32) (string, error) { |
| if st.base != nil && offset <= st.base.offsets[len(st.base.offsets)-1] { |
| return st.base.lookup(offset) |
| } |
| return st.lookup(offset) |
| } |
| |
| func (st *stringTable) lookup(offset uint32) (string, error) { |
| i := search(st.offsets, offset) |
| if i == len(st.offsets) || st.offsets[i] != offset { |
| return "", fmt.Errorf("offset %d isn't start of a string", offset) |
| } |
| |
| return st.strings[i], nil |
| } |
| |
| func (st *stringTable) Marshal(w io.Writer) error { |
| for _, str := range st.strings { |
| _, err := io.WriteString(w, str) |
| if err != nil { |
| return err |
| } |
| _, err = w.Write([]byte{0}) |
| if err != nil { |
| return err |
| } |
| } |
| return nil |
| } |
| |
| // Num returns the number of strings in the table. |
| func (st *stringTable) Num() int { |
| return len(st.strings) |
| } |
| |
| // search is a copy of sort.Search specialised for uint32. |
| // |
| // Licensed under https://go.dev/LICENSE |
| func search(ints []uint32, needle uint32) int { |
| // Define f(-1) == false and f(n) == true. |
| // Invariant: f(i-1) == false, f(j) == true. |
| i, j := 0, len(ints) |
| for i < j { |
| h := int(uint(i+j) >> 1) // avoid overflow when computing h |
| // i ≤ h < j |
| if !(ints[h] >= needle) { |
| i = h + 1 // preserves f(i-1) == false |
| } else { |
| j = h // preserves f(j) == true |
| } |
| } |
| // i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i. |
| return i |
| } |
| |
| // stringTableBuilder builds BTF string tables. |
| type stringTableBuilder struct { |
| length uint32 |
| strings map[string]uint32 |
| } |
| |
| // newStringTableBuilder creates a builder with the given capacity. |
| // |
| // capacity may be zero. |
| func newStringTableBuilder(capacity int) *stringTableBuilder { |
| var stb stringTableBuilder |
| |
| if capacity == 0 { |
| // Use the runtime's small default size. |
| stb.strings = make(map[string]uint32) |
| } else { |
| stb.strings = make(map[string]uint32, capacity) |
| } |
| |
| // Ensure that the empty string is at index 0. |
| stb.append("") |
| return &stb |
| } |
| |
| // Add a string to the table. |
| // |
| // Adding the same string multiple times will only store it once. |
| func (stb *stringTableBuilder) Add(str string) (uint32, error) { |
| if strings.IndexByte(str, 0) != -1 { |
| return 0, fmt.Errorf("string contains null: %q", str) |
| } |
| |
| offset, ok := stb.strings[str] |
| if ok { |
| return offset, nil |
| } |
| |
| return stb.append(str), nil |
| } |
| |
| func (stb *stringTableBuilder) append(str string) uint32 { |
| offset := stb.length |
| stb.length += uint32(len(str)) + 1 |
| stb.strings[str] = offset |
| return offset |
| } |
| |
| // Lookup finds the offset of a string in the table. |
| // |
| // Returns an error if str hasn't been added yet. |
| func (stb *stringTableBuilder) Lookup(str string) (uint32, error) { |
| offset, ok := stb.strings[str] |
| if !ok { |
| return 0, fmt.Errorf("string %q is not in table", str) |
| } |
| |
| return offset, nil |
| } |
| |
| // Length returns the length in bytes. |
| func (stb *stringTableBuilder) Length() int { |
| return int(stb.length) |
| } |
| |
| // AppendEncoded appends the string table to the end of the provided buffer. |
| func (stb *stringTableBuilder) AppendEncoded(buf []byte) []byte { |
| n := len(buf) |
| buf = append(buf, make([]byte, stb.Length())...) |
| strings := buf[n:] |
| for str, offset := range stb.strings { |
| copy(strings[offset:], str) |
| } |
| return buf |
| } |
| |
| // Copy the string table builder. |
| func (stb *stringTableBuilder) Copy() *stringTableBuilder { |
| return &stringTableBuilder{ |
| stb.length, |
| maps.Clone(stb.strings), |
| } |
| } |