go/src/thinfs/buddy/buddy_test.go

// Copyright 2016 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 buddy

import (
	"math/rand"
	"reflect"
	"testing"
	"time"

	"thinfs/bitops"
)

const (
	start    uint64 = 0
	size            = 4 * 1024 * 1024 * 1024 // 4G
	minAlloc        = 4 * 1024               // 4K
	maxAlloc        = 4 * 1024 * 1024        // 4M
)

const numIterations = 5000

func randomElem(m map[uint64]uint) uint64 {
	for k := range m {
		return k
	}

	return 0
}

func setUp(t *testing.T) (*Allocator, map[uint64]uint) {
	a, err := NewAllocator(start, size, minAlloc, maxAlloc)
	if err != nil {
		t.Error("Error creating binary buddy alocator: ", err)
		t.FailNow()
	}
	seed := time.Now().UTC().UnixNano()
	t.Log("seed is ", seed)
	r := rand.New(rand.NewSource(seed))

	alloc := make(map[uint64]uint)
	for i := 0; i < numIterations; i++ {
		if r.Int()&0x1 == 0 {
			// Free a chunk
			addr := randomElem(alloc)
			delete(alloc, addr)
			a.Free(addr)
			continue
		}

		// Allocate a chunk
		size := uint64(r.Intn(int(maxAlloc)))
		addr, err := a.Alloc(size)
		if err != nil {
			t.Errorf("Error allocating chunk of size %v: %v\n", size, err)
			t.FailNow()
		}
		if _, ok := alloc[addr]; ok {
			t.Errorf("Address %v has already been allocated\n", addr)
			t.FailNow()
		}

		var order uint
		if isPowerOfTwo(size) {
			order = bitops.FFS(size)
		} else {
			order = 64 - bitops.CLZ(size)
		}
		alloc[addr] = order
	}

	return a, alloc
}

func TestPolicy(t *testing.T) {
	_, alloc := setUp(t)

	for addr, expected := range alloc {
		// 0 is kind of a special address since it's always valid.
		if addr == 0 {
			continue
		}
		if actual := bitops.FFS(addr); actual < expected {
			t.Errorf("Address %#x has order %v; want order %v or larger\n", addr, actual, expected)
		}
	}
}

func TestMarshalUnmarshal(t *testing.T) {
	a, _ := setUp(t)

	buf, err := a.MarshalBinary()
	if err != nil {
		t.Error("error marshaling binary: ", err)
		t.FailNow()
	}

	a2 := new(Allocator)
	if err := a2.UnmarshalBinary(buf); err != nil {
		t.Error("error unmarshaling binary: ", err)
		t.FailNow()
	}

	if !reflect.DeepEqual(a, a2) {
		t.Error("a and a2 differ")
	}
}