Merge branch 'autopar_rebase2' into autopar_develdevel/autopar_devel

Quickly commit changes in the rebase branch.

1 files changed, 192 insertions, 13 deletions

diff --git a/libgo/go/runtime/mranges.go b/libgo/go/runtime/mranges.go
index b133851..2c0eb2c 100644
--- a/libgo/go/runtime/mranges.go
+++ b/libgo/go/runtime/mranges.go
@@ -15,23 +15,41 @@ import (
 )
 
 // addrRange represents a region of address space.
+//
+// An addrRange must never span a gap in the address space.
 type addrRange struct {
 	// base and limit together represent the region of address space
 	// [base, limit). That is, base is inclusive, limit is exclusive.
-	base, limit uintptr
+	// These are address over an offset view of the address space on
+	// platforms with a segmented address space, that is, on platforms
+	// where arenaBaseOffset != 0.
+	base, limit offAddr
+}
+
+// makeAddrRange creates a new address range from two virtual addresses.
+//
+// Throws if the base and limit are not in the same memory segment.
+func makeAddrRange(base, limit uintptr) addrRange {
+	r := addrRange{offAddr{base}, offAddr{limit}}
+	if (base-arenaBaseOffset >= base) != (limit-arenaBaseOffset >= limit) {
+		throw("addr range base and limit are not in the same memory segment")
+	}
+	return r
 }
 
 // size returns the size of the range represented in bytes.
 func (a addrRange) size() uintptr {
-	if a.limit <= a.base {
+	if !a.base.lessThan(a.limit) {
 		return 0
 	}
-	return a.limit - a.base
+	// Subtraction is safe because limit and base must be in the same
+	// segment of the address space.
+	return a.limit.diff(a.base)
 }
 
 // contains returns whether or not the range contains a given address.
 func (a addrRange) contains(addr uintptr) bool {
-	return addr >= a.base && addr < a.limit
+	return a.base.lessEqual(offAddr{addr}) && (offAddr{addr}).lessThan(a.limit)
 }
 
 // subtract takes the addrRange toPrune and cuts out any overlap with
@@ -39,18 +57,90 @@ func (a addrRange) contains(addr uintptr) bool {
 // either don't overlap at all, only overlap on one side, or are equal.
 // If b is strictly contained in a, thus forcing a split, it will throw.
 func (a addrRange) subtract(b addrRange) addrRange {
-	if a.base >= b.base && a.limit <= b.limit {
+	if b.base.lessEqual(a.base) && a.limit.lessEqual(b.limit) {
 		return addrRange{}
-	} else if a.base < b.base && a.limit > b.limit {
+	} else if a.base.lessThan(b.base) && b.limit.lessThan(a.limit) {
 		throw("bad prune")
-	} else if a.limit > b.limit && a.base < b.limit {
+	} else if b.limit.lessThan(a.limit) && a.base.lessThan(b.limit) {
 		a.base = b.limit
-	} else if a.base < b.base && a.limit > b.base {
+	} else if a.base.lessThan(b.base) && b.base.lessThan(a.limit) {
 		a.limit = b.base
 	}
 	return a
 }
 
+// removeGreaterEqual removes all addresses in a greater than or equal
+// to addr and returns the new range.
+func (a addrRange) removeGreaterEqual(addr uintptr) addrRange {
+	if (offAddr{addr}).lessEqual(a.base) {
+		return addrRange{}
+	}
+	if a.limit.lessEqual(offAddr{addr}) {
+		return a
+	}
+	return makeAddrRange(a.base.addr(), addr)
+}
+
+var (
+	// minOffAddr is the minimum address in the offset space, and
+	// it corresponds to the virtual address arenaBaseOffset.
+	minOffAddr = offAddr{arenaBaseOffset}
+
+	// maxOffAddr is the maximum address in the offset address
+	// space. It corresponds to the highest virtual address representable
+	// by the page alloc chunk and heap arena maps.
+	maxOffAddr = offAddr{(((1 << heapAddrBits) - 1) + arenaBaseOffset) & uintptrMask}
+)
+
+// offAddr represents an address in a contiguous view
+// of the address space on systems where the address space is
+// segmented. On other systems, it's just a normal address.
+type offAddr struct {
+	// a is just the virtual address, but should never be used
+	// directly. Call addr() to get this value instead.
+	a uintptr
+}
+
+// add adds a uintptr offset to the offAddr.
+func (l offAddr) add(bytes uintptr) offAddr {
+	return offAddr{a: l.a + bytes}
+}
+
+// sub subtracts a uintptr offset from the offAddr.
+func (l offAddr) sub(bytes uintptr) offAddr {
+	return offAddr{a: l.a - bytes}
+}
+
+// diff returns the amount of bytes in between the
+// two offAddrs.
+func (l1 offAddr) diff(l2 offAddr) uintptr {
+	return l1.a - l2.a
+}
+
+// lessThan returns true if l1 is less than l2 in the offset
+// address space.
+func (l1 offAddr) lessThan(l2 offAddr) bool {
+	return (l1.a - arenaBaseOffset) < (l2.a - arenaBaseOffset)
+}
+
+// lessEqual returns true if l1 is less than or equal to l2 in
+// the offset address space.
+func (l1 offAddr) lessEqual(l2 offAddr) bool {
+	return (l1.a - arenaBaseOffset) <= (l2.a - arenaBaseOffset)
+}
+
+// equal returns true if the two offAddr values are equal.
+func (l1 offAddr) equal(l2 offAddr) bool {
+	// No need to compare in the offset space, it
+	// means the same thing.
+	return l1 == l2
+}
+
+// addr returns the virtual address for this offset address.
+func (l offAddr) addr() uintptr {
+	return l.a
+}
+
 // addrRanges is a data structure holding a collection of ranges of
 // address space.
 //
@@ -65,6 +155,10 @@ type addrRanges struct {
 	// ranges is a slice of ranges sorted by base.
 	ranges []addrRange
 
+	// totalBytes is the total amount of address space in bytes counted by
+	// this addrRanges.
+	totalBytes uintptr
+
 	// sysStat is the stat to track allocations by this type
 	sysStat *uint64
 }
@@ -75,23 +169,44 @@ func (a *addrRanges) init(sysStat *uint64) {
 	ranges.cap = 16
 	ranges.array = (*notInHeap)(persistentalloc(unsafe.Sizeof(addrRange{})*uintptr(ranges.cap), sys.PtrSize, sysStat))
 	a.sysStat = sysStat
+	a.totalBytes = 0
 }
 
 // findSucc returns the first index in a such that base is
 // less than the base of the addrRange at that index.
-func (a *addrRanges) findSucc(base uintptr) int {
+func (a *addrRanges) findSucc(addr uintptr) int {
 	// TODO(mknyszek): Consider a binary search for large arrays.
 	// While iterating over these ranges is potentially expensive,
 	// the expected number of ranges is small, ideally just 1,
 	// since Go heaps are usually mostly contiguous.
+	base := offAddr{addr}
 	for i := range a.ranges {
-		if base < a.ranges[i].base {
+		if base.lessThan(a.ranges[i].base) {
 			return i
 		}
 	}
 	return len(a.ranges)
 }
 
+// findAddrGreaterEqual returns the smallest address represented by a
+// that is >= addr. Thus, if the address is represented by a,
+// then it returns addr. The second return value indicates whether
+// such an address exists for addr in a. That is, if addr is larger than
+// any address known to a, the second return value will be false.
+func (a *addrRanges) findAddrGreaterEqual(addr uintptr) (uintptr, bool) {
+	i := a.findSucc(addr)
+	if i == 0 {
+		return a.ranges[0].base.addr(), true
+	}
+	if a.ranges[i-1].contains(addr) {
+		return addr, true
+	}
+	if i < len(a.ranges) {
+		return a.ranges[i].base.addr(), true
+	}
+	return 0, false
+}
+
 // contains returns true if a covers the address addr.
 func (a *addrRanges) contains(addr uintptr) bool {
 	i := a.findSucc(addr)
@@ -116,9 +231,9 @@ func (a *addrRanges) add(r addrRange) {
 
 	// Because we assume r is not currently represented in a,
 	// findSucc gives us our insertion index.
-	i := a.findSucc(r.base)
-	coalescesDown := i > 0 && a.ranges[i-1].limit == r.base
-	coalescesUp := i < len(a.ranges) && r.limit == a.ranges[i].base
+	i := a.findSucc(r.base.addr())
+	coalescesDown := i > 0 && a.ranges[i-1].limit.equal(r.base)
+	coalescesUp := i < len(a.ranges) && r.limit.equal(a.ranges[i].base)
 	if coalescesUp && coalescesDown {
 		// We have neighbors and they both border us.
 		// Merge a.ranges[i-1], r, and a.ranges[i] together into a.ranges[i-1].
@@ -158,4 +273,68 @@ func (a *addrRanges) add(r addrRange) {
 		}
 		a.ranges[i] = r
 	}
+	a.totalBytes += r.size()
+}
+
+// removeLast removes and returns the highest-addressed contiguous range
+// of a, or the last nBytes of that range, whichever is smaller. If a is
+// empty, it returns an empty range.
+func (a *addrRanges) removeLast(nBytes uintptr) addrRange {
+	if len(a.ranges) == 0 {
+		return addrRange{}
+	}
+	r := a.ranges[len(a.ranges)-1]
+	size := r.size()
+	if size > nBytes {
+		newEnd := r.limit.sub(nBytes)
+		a.ranges[len(a.ranges)-1].limit = newEnd
+		a.totalBytes -= nBytes
+		return addrRange{newEnd, r.limit}
+	}
+	a.ranges = a.ranges[:len(a.ranges)-1]
+	a.totalBytes -= size
+	return r
+}
+
+// removeGreaterEqual removes the ranges of a which are above addr, and additionally
+// splits any range containing addr.
+func (a *addrRanges) removeGreaterEqual(addr uintptr) {
+	pivot := a.findSucc(addr)
+	if pivot == 0 {
+		// addr is before all ranges in a.
+		a.totalBytes = 0
+		a.ranges = a.ranges[:0]
+		return
+	}
+	removed := uintptr(0)
+	for _, r := range a.ranges[pivot:] {
+		removed += r.size()
+	}
+	if r := a.ranges[pivot-1]; r.contains(addr) {
+		removed += r.size()
+		r = r.removeGreaterEqual(addr)
+		if r.size() == 0 {
+			pivot--
+		} else {
+			removed -= r.size()
+			a.ranges[pivot-1] = r
+		}
+	}
+	a.ranges = a.ranges[:pivot]
+	a.totalBytes -= removed
+}
+
+// cloneInto makes a deep clone of a's state into b, re-using
+// b's ranges if able.
+func (a *addrRanges) cloneInto(b *addrRanges) {
+	if len(a.ranges) > cap(b.ranges) {
+		// Grow the array.
+		ranges := (*notInHeapSlice)(unsafe.Pointer(&b.ranges))
+		ranges.len = 0
+		ranges.cap = cap(a.ranges)
+		ranges.array = (*notInHeap)(persistentalloc(unsafe.Sizeof(addrRange{})*uintptr(ranges.cap), sys.PtrSize, b.sysStat))
+	}
+	b.ranges = b.ranges[:len(a.ranges)]
+	b.totalBytes = a.totalBytes
+	copy(b.ranges, a.ranges)
 }