symbolize/mapstore.go

// Copyright 2018 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

package symbolize

import (
	"sort"
)

// TODO (jakehehrlich): This whole file should be private.

type byVAddr []Segment

func (b byVAddr) Len() int {
	return len(b)
}

func (b byVAddr) Swap(i, j int) {
	b[i], b[j] = b[j], b[i]
}

func (b byVAddr) Less(i, j int) bool {
	return b[i].Vaddr < b[j].Vaddr
}

// TODO: replace with skip list
// I call it a "lazy flat map". It stores mapped regions of memory in a way that
// allows them to be efficentily looked up by an address within them.

// MappingStore quasi-efficently indexes segments by their start address.
type mappingStore struct {
	segments []Segment
	sorted   int
}

func merge(a []Segment, b []Segment) []Segment {
	out := []Segment{}
	for len(a) != 0 && len(b) != 0 {
		var min Segment
		if a[0].Vaddr < b[0].Vaddr {
			min = a[0]
			a = a[1:]
		} else {
			min = b[0]
			b = b[1:]
		}
		out = append(out, min)
	}
	out = append(out, a...)
	out = append(out, b...)
	return out
}

// sortAndFind is meant to be called if an element couldn't be found.
// sortAndFind sorts the unsorted range of segments, finds the missing element
// and then merges the two sorted ranges so that sortAndFind won't have to be
// called again for the same element.
func (m *mappingStore) sortAndFind(vaddr uint64) *Segment {
	sort.Sort(byVAddr(m.segments[m.sorted:]))
	seg := findSegment(m.segments[m.sorted:], vaddr)
	newMods := merge(m.segments[m.sorted:], m.segments[:m.sorted])
	m.segments = newMods
	m.sorted = len(newMods)
	return seg
}

// findSegment finds a segment in sorted slice of segments.
func findSegment(sorted []Segment, vaddr uint64) *Segment {
	idx := sort.Search(len(sorted), func(i int) bool {
		seg := sorted[i]
		return seg.Vaddr+seg.Size >= vaddr
	})
	if idx < len(sorted) && sorted[idx].Vaddr <= vaddr {
		return &sorted[idx]
	}
	return nil
}

// Find first trys to find the desired segment in the sorted segment. If the segment
// can't be found we consult the unsorted part and update the structure.
func (m *mappingStore) find(vaddr uint64) *Segment {
	out := findSegment(m.segments[:m.sorted], vaddr)
	if out == nil {
		out = m.sortAndFind(vaddr)
	}
	return out
}

// Add adds a segment to the segment.
func (m *mappingStore) add(seg Segment) {
	m.segments = append(m.segments, seg)
}

// Clear clears the mapping store of all previous information
func (m *mappingStore) clear() {
	m.segments = nil
	m.sorted = 0
}

// GetSegments returns a new slice containing all the segments
func (m *mappingStore) GetSegments() []Segment {
	out := make([]Segment, len(m.segments))
	copy(out, m.segments)
	return out
}