falloc_test.go

// Copyright 2013 The Go 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 lldb

import (
	"bytes"
	"encoding/hex"
	"flag"
	"fmt"
	"math/rand"
	"os"
	"runtime"
	"sort"
	"strings"
	"testing"
	"time"

	"github.com/cznic/bufs"
	"github.com/cznic/sortutil"
	"github.com/cznic/zappy"
)

var (
	allocRndTestLimit     = flag.Uint("lim", 2*maxShort, "Allocator rnd test initial blocks size limit")
	allocRndTestHardLimit = flag.Uint("hlim", 0, "Allocator rnd test initial blocks size hard limit")
	testN                 = flag.Int("N", 128, "Allocator rnd test block count")
	allocRndDump          = flag.Bool("dump", false, "Produce dump files on TestAllocatorRnd crash")
	oKeep                 = flag.Bool("keep", false, "do not delete testing DB/WAL (where applicable)")
)

func init() {
	reallocTestHook = true
}

func mfBytes(f Filer) []byte {
	var b bytes.Buffer
	if _, err := f.(*MemFiler).WriteTo(&b); err != nil {
		panic(err)
	}

	return b.Bytes()
}

// Paranoid Allocator, automatically verifies whenever possible.
type pAllocator struct {
	*Allocator
	errors           []error
	logger           func(error) bool
	lastKnownGood    *MemFiler
	lastKnownGoodFLT flt
	lastOp           string
	stats            AllocStats
}

func newPAllocator(f Filer) (*pAllocator, error) {
	a, err := NewAllocator(f, &Options{})
	if err != nil {
		return nil, err
	}

	r := &pAllocator{Allocator: a, lastKnownGood: NewMemFiler()}
	r.logger = func(err error) bool {
		r.errors = append(r.errors, err)
		return len(r.errors) < 100
	}

	return r, nil
}

func (a *pAllocator) err() error {
	var n int
	if n = len(a.errors); n == 0 {
		return nil
	}

	s := make([]string, n)
	for i, e := range a.errors {
		s[i] = e.Error()
	}
	return fmt.Errorf("\n%s", strings.Join(s, "\n"))
}

func (a *pAllocator) preMortem(s string) {
	var e error
	if e := a.lastKnownGood.Truncate(0); e != nil {
		panic(e)
	}
	b := mfBytes(a.Allocator.f)
	if _, e = a.lastKnownGood.WriteAt(b, 0); e != nil {
		return
	}
	a.lastKnownGoodFLT = a.flt
	a.lastOp = s
}

func (a *pAllocator) Alloc(b []byte) (handle int64, err error) {
	if *allocRndDump {
		a.preMortem("")
		defer func() { a.lastOp = fmt.Sprintf("Alloc(%d bytes): h %#x", len(b), handle) }()
	}

	if handle, err = a.Allocator.Alloc(b); err != nil {
		return
	}

	if err = a.Allocator.Verify(NewMemFiler(), a.logger, &a.stats); err != nil {
		err = fmt.Errorf("'%s': %v", err, a.err())
		return
	}

	err = a.err()
	return
}

func (a *pAllocator) Free(handle int64) (err error) {
	if *allocRndDump {
		a.preMortem(fmt.Sprintf("Free(h %#x)", handle))
	}

	if err = a.Allocator.Free(handle); err != nil {
		return
	}

	if err = a.Allocator.Verify(NewMemFiler(), a.logger, &a.stats); err != nil {
		err = fmt.Errorf("'%s': %v", err, a.err())
		return
	}

	err = a.err()
	return
}

func (a *pAllocator) Realloc(handle int64, b []byte) (err error) {
	if *allocRndDump {
		a.preMortem(fmt.Sprintf("Realloc(h %#x, %d bytes)", handle, len(b)))
	}

	if err = a.Allocator.Realloc(handle, b); err != nil {
		return
	}

	if err = cacheAudit(a.Allocator.m, &a.Allocator.lru); err != nil {
		return
	}

	if err = a.Allocator.Verify(NewMemFiler(), a.logger, &a.stats); err != nil {
		err = fmt.Errorf("'%s': %v", err, a.err())
		return
	}

	err = a.err()
	return
}

func dump(a *pAllocator, t *testing.T) {
	m := a.f.(*MemFiler)
	sz, err := m.Size()
	if err != nil {
		t.Fatal(err)
	}

	t.Logf("MemFiler.Size() == %d(%#x)", sz, sz)
	if !*allocRndDump {
		return
	}

	fn := "good-dump"
	f, err := os.Create(fn)
	if err != nil {
		t.Fatal(err)
	}

	defer f.Close()
	sz, err = a.lastKnownGood.WriteTo(f)
	if err != nil {
		t.Error(err)
		return
	}

	t.Logf("%d(%#x) writen to %q", sz, sz, fn)

	fn = "bad-dump"
	g, err := os.Create(fn)
	if err != nil {
		t.Fatal(err)
	}

	defer g.Close()
	sz, err = m.WriteTo(g)
	if err != nil {
		t.Error(err)
		return
	}

	t.Logf("%d(%#x) writen to %q", sz, sz, fn)

	t.Log("Last known good FLT")
	for _, slot := range a.lastKnownGoodFLT {
		if h := slot.head; h != 0 {
			t.Logf("min %d head %#x off %#x", slot.minSize, h, h2off(h))
		}
	}

	t.Log("Current FLT")
	r := a.flt
	for _, slot := range r {
		if h := slot.head; h != 0 {
			t.Logf("min %d head %#x off %#x", slot.minSize, h, h2off(h))
		}
	}
	t.Logf("Last op: %q", a.lastOp)
}

func init() {
	if *testN <= 0 {
		*testN = 1
	}
}

func TestVerify0(t *testing.T) {
	// All must fail
	tab := []string{

		// 0: Reloc, links beyond EOF
		"" +
			"fd 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00",
		// 1: Reloc, links beyond EOF
		"" +
			"fd 00 00 00 00 00 00 03 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 2: Reloc, broken target
		"" +
			"fd 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 3: Free block at file tail
		"" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 00 fe",
		// 4: Free block at file tail
		"" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 00 fe",
		// 5: Reloc, invalid target 0xfe
		"" +
			"fd 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 00 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 6: Reloc, invalid target 0xfd
		"" +
			"fd 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00" +
			"fd 00 00 00 00 00 00 01 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 7: Lost free block @ 0x00
		"" +
			"fe 00 00 00 00 00 00 02 00 00 00 00 00 00 00 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 8: Lost free block @ 0x10
		"" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 02 00 00 00 00 00 00 00 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 9: Invalid padding
		"" +
			"00 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 10: Invalid padding
		"" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 00",
		// 11: Invalid padding
		"" +
			"01 00 01 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 12: Invalid padding
		"" +
			"01 00 00 00 00 00 00 00 00 00 00 00 00 00 01 00",
		// 13: Invalid padding
		"" +
			"0d 00 00 00 00 00 00 00 00 00 00 00 00 00 01 00",
		// 14: Invalid CC (tail tag)
		"" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 02",
		// 15: Invalid CC (tail tag)
		"" +
			"fd 00 00 00 00 00 00 02 00 00 00 00 00 00 00 01",
		// 16: Cannot decompress
		"" +
			"0e 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01",
		// 17: Invalid reloc target
		"" +
			"fd 00 00 00 00 00 00 03 00 00 00 00 00 00 00 00" +
			"ff 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 02 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 18: Invalid tail tag @1
		"" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 19: Invalid size @1
		"" +
			"ff 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 20: Invalid size @1
		"" +
			"ff 00 00 00 00 00 00 01 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 21: Invalid size @1
		"" +
			"ff 00 00 00 00 00 00 04 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 02 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 22: Invalid .next @1
		"" +
			"ff 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 04 00 00 00 00 00 00 00 00 02 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 23: Invalid .prev @1
		"" +
			"ff 00 00 00 00 00 00 02 00 00 00 00 00 00 04 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 02 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 24: Invalid tail tag @1
		"" +
			"ff 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 02 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 25: Invalid tail size @1
		"" +
			"ff 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 26: Invalid tail size @1
		"" +
			"ff 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 27: Invalid tail size @1
		"" +
			"ff 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 03 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		//       00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
	}

	for i, test := range tab {
		errors := []error{}

		f := NewMemFiler()
		b := s2b(test)
		b = append(make([]byte, fltSz), b...)
		n := len(b)
		if n == 0 {
			t.Fatal(n)
		}

		if m, err := f.ReadFrom(bytes.NewBuffer(b)); m != int64(n) || err != nil {
			t.Fatal(m, err)
		}

		sz, err := f.Size()
		if err != nil {
			t.Fatal(err)
		}

		if g, e := sz, int64(n); g != e {
			t.Fatal(g, e)
		}

		a, err := newPAllocator(f)
		if err != nil {
			t.Fatal(err)
		}

		err = a.Verify(
			NewMemFiler(),
			func(err error) bool {
				if err == nil {
					t.Fatal("nil error")
				}
				errors = append(errors, err)
				return false
			},
			nil,
		)
		if err == nil {
			t.Fatal(i, "unexpected success")
		}

		t.Log(i, err, errors)
	}
}

func TestVerify1(t *testing.T) {
	f := NewMemFiler()
	bitmap := NewMemFiler()
	if n, err := bitmap.WriteAt([]byte{0}, 0); n != 1 || err != nil {
		t.Fatal(n, err)
	}

	a, err := newPAllocator(f)
	if err != nil {
		t.Fatal(err)
	}

	if err := a.Verify(
		bitmap,
		func(error) bool {
			panic("intrnal error")
		},
		nil,
	); err == nil {
		t.Fatal("unexpected success")
	}
}

func repDump(a flt) string {
	b := []string{}
	for _, v := range a {
		if h := v.head; h != 0 {
			b = append(b, fmt.Sprintf("min:%d, h:%d", v.minSize, h))
		}
	}
	return strings.Join(b, ";")
}

func TestVerify2(t *testing.T) {
	// All must fail for the fixed (see bellow) FLT.Report()
	tab := []string{

		// 0: FLT broken linkage (missing free blocks @2,4)
		"" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 1: FLT broken linkage (missing free block @4)
		"" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 00 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		// 2: bad size @4
		"" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 00 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 00 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		//		// 3: bad size @4
		"" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 04 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"ff 00 00 00 00 00 00 01 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		//		// 4: bad .next @6 from @2
		"" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 06 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"ff 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 02 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 00 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		//		// 5: bad .prev @7
		"" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 07 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"ff 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 02 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 00 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		//		// 6: bad .next @7
		"" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 07 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"ff 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 02 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 02 00 00 00 00 00 00 07 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		//		// 7: bad .next @5
		"" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 07 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"ff 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 02 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 02 00 00 00 00 00 00 01 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		//		// 8: bad chaining
		"" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 07 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"ff 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 02 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 02 00 00 00 00 00 00 01 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		//		// 9: lost free block @8
		"" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 0f fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"ff 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 02 ff" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 00 00 00 00 00 00 00 00 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00" +
			"fe 00 00 00 00 00 00 02 00 00 00 00 00 00 00 fe" +
			"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
		//       00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
	}

	for i, test := range tab {
		errors := []error{}

		f := NewMemFiler()
		b := s2b(test)
		b = append(make([]byte, fltSz), b...)
		n := len(b)
		if n == 0 {
			t.Fatal(n)
		}

		if m, err := f.ReadFrom(bytes.NewBuffer(b)); m != int64(n) || err != nil {
			t.Fatal(m, err)
		}

		sz, err := f.Size()
		if err != nil {
			t.Fatal(err)
		}

		if g, e := sz, int64(n); g != e {
			t.Fatal(g, e)
		}

		a, err := newPAllocator(f)
		if err != nil {
			t.Fatal(err)
		}

		a.flt.setHead(2, 1, a.f)
		a.flt.setHead(4, 2, a.f)
		err = a.Verify(
			NewMemFiler(),
			func(err error) bool {
				if err == nil {
					t.Fatal("nil error")
				}
				t.Log(i, "logged: ", err)
				errors = append(errors, err)
				return true
			},
			nil,
		)
		if err == nil {
			t.Fatal(i, "unexpected success")
		}

		t.Log(i, err, errors)
	}
}

// Allocation in an empty DB.
func TestAllocatorAlloc0(t *testing.T) {
	tab := []struct {
		h        int64
		b, f, fc string
	}{
		{1, // len 0
			"" +
				"",
			"" +
				"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
			"" +
				"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"},
		{1, // len 1
			"" +
				"42",
			"" +
				"01 42 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
			"" +
				"01 42 00 00 00 00 00 00 00 00 00 00 00 00 00 00"},
		{1, // max single atom, not compressible
			"" +
				"01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e",
			"" +
				"0e 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 00",
			"" +
				"0e 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 00"},
		{1, // max single atom, compressible, but not eligible for it
			"" +
				"01 02 03 04 05 06 07 08 99 01 02 03 04 05",
			"" +
				"0e 01 02 03 04 05 06 07 08 99 01 02 03 04 05 00",
			"" +
				"0e 01 02 03 04 05 06 07 08 99 01 02 03 04 05 00"},
		{1, // > 1 atom, not compressible
			"" +
				"01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f",
			"" +
				"0f 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
			"" +
				"0f 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"},
		{1, // > 1 atom, compressible
			"" +
				"01 02 03 04 05 06 07 08 99 01 02 03 04 05 06 07" +
				"08",
			"" +
				"11 01 02 03 04 05 06 07 08 99 01 02 03 04 05 06" +
				"07 08 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
			"" +
				"0e 11 12 01 02 03 04 05 06 07 08 99 01 0d 09 01"},
		{1, // longest short
			"" +
				"00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"10 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"20 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"30 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"40 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"50 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"60 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"70 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"80 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"90 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"a0 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"b0 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"c0 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"d0 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"e0 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"f0 01 02 03 04 05 06 07 08 09 0a",
			"" +
				"" +
				"fb 00 01 02 03 04 05 06  07 08 09 0a 0b 0c 0d 0e" +
				"0f 10 01 02 03 04 05 06  07 08 09 0a 0b 0c 0d 0e" +
				"0f 20 01 02 03 04 05 06  07 08 09 0a 0b 0c 0d 0e" +
				"0f 30 01 02 03 04 05 06  07 08 09 0a 0b 0c 0d 0e" +
				"0f 40 01 02 03 04 05 06  07 08 09 0a 0b 0c 0d 0e" +
				"0f 50 01 02 03 04 05 06  07 08 09 0a 0b 0c 0d 0e" +
				"0f 60 01 02 03 04 05 06  07 08 09 0a 0b 0c 0d 0e" +
				"0f 70 01 02 03 04 05 06  07 08 09 0a 0b 0c 0d 0e" +
				"0f 80 01 02 03 04 05 06  07 08 09 0a 0b 0c 0d 0e" +
				"0f 90 01 02 03 04 05 06  07 08 09 0a 0b 0c 0d 0e" +
				"0f a0 01 02 03 04 05 06  07 08 09 0a 0b 0c 0d 0e" +
				"0f b0 01 02 03 04 05 06  07 08 09 0a 0b 0c 0d 0e" +
				"0f c0 01 02 03 04 05 06  07 08 09 0a 0b 0c 0d 0e" +
				"0f d0 01 02 03 04 05 06  07 08 09 0a 0b 0c 0d 0e" +
				"0f e0 01 02 03 04 05 06  07 08 09 0a 0b 0c 0d 0e" +
				"0f f0 01 02 03 04 05 06  07 08 09 0a 00 00 00 00",
			"" +
				"" +
				"4e fb 01 20 00 01 02 03  04 05 06 07 08 09 0a 0b" +
				"0c 0d 0e 0f 10 1d 10 00  20 1d 10 00 30 1d 10 00" +
				"40 1d 10 00 50 1d 10 00  60 1d 10 00 70 1d 10 00" +
				"80 1d 10 00 90 1d 10 00  a0 1d 10 00 b0 1d 10 00" +
				"c0 1d 10 00 d0 1d 10 00  e0 1d 10 00 f0 13 10 01"},

		{1, // shortest long
			"" +
				"00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"10 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"20 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"30 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"40 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"50 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"60 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"70 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"80 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"90 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"a0 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"b0 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"c0 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"d0 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"e0 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f" +
				"f0 01 02 03 04 05 06 07 08 09 0a 0b",
			"" +
				"" +
				"fc 00 fc 00 01 02 03 04  05 06 07 08 09 0a 0b 0c" +
				"0d 0e 0f 10 01 02 03 04  05 06 07 08 09 0a 0b 0c" +
				"0d 0e 0f 20 01 02 03 04  05 06 07 08 09 0a 0b 0c" +
				"0d 0e 0f 30 01 02 03 04  05 06 07 08 09 0a 0b 0c" +
				"0d 0e 0f 40 01 02 03 04  05 06 07 08 09 0a 0b 0c" +
				"0d 0e 0f 50 01 02 03 04  05 06 07 08 09 0a 0b 0c" +
				"0d 0e 0f 60 01 02 03 04  05 06 07 08 09 0a 0b 0c" +
				"0d 0e 0f 70 01 02 03 04  05 06 07 08 09 0a 0b 0c" +
				"0d 0e 0f 80 01 02 03 04  05 06 07 08 09 0a 0b 0c" +
				"0d 0e 0f 90 01 02 03 04  05 06 07 08 09 0a 0b 0c" +
				"0d 0e 0f a0 01 02 03 04  05 06 07 08 09 0a 0b 0c" +
				"0d 0e 0f b0 01 02 03 04  05 06 07 08 09 0a 0b 0c" +
				"0d 0e 0f c0 01 02 03 04  05 06 07 08 09 0a 0b 0c" +
				"0d 0e 0f d0 01 02 03 04  05 06 07 08 09 0a 0b 0c" +
				"0d 0e 0f e0 01 02 03 04  05 06 07 08 09 0a 0b 0c" +
				"0d 0e 0f f0 01 02 03 04  05 06 07 08 09 0a 0b 00",
			"" +
				"" +
				"4e fc 01 20 00 01 02 03  04 05 06 07 08 09 0a 0b" +
				"0c 0d 0e 0f 10 1d 10 00  20 1d 10 00 30 1d 10 00" +
				"40 1d 10 00 50 1d 10 00  60 1d 10 00 70 1d 10 00" +
				"80 1d 10 00 90 1d 10 00  a0 1d 10 00 b0 1d 10 00" +
				"c0 1d 10 00 d0 1d 10 00  e0 1d 10 00 f0 15 10 01"},
	}

	for i, test := range tab {
		f := func(compress bool, e []byte) {
			f := NewMemFiler()
			a, err := newPAllocator(f)
			if err != nil {
				t.Fatal(err)
			}

			a.Compress = compress
			h, err := a.Alloc(s2b(test.b))
			if err != nil {
				t.Fatalf("%d %#v\n%s", i, err, hex.Dump(mfBytes(f)))
			}

			if g, e := h, test.h; g != e {
				t.Fatal(i, g, e)
			}

			g := mfBytes(f)
			if g = g[fltSz:]; !bytes.Equal(g, e) {
				t.Fatalf("\ni: %d compress: %t\ng:\n%se:\n%s", i, compress, hex.Dump(g), hex.Dump(e))
			}
		}
		f(false, s2b(test.f))
		f(true, s2b(test.fc))
	}
}

func TestAllocatorMakeUsedBlock(t *testing.T) {
	f := NewMemFiler()
	a, err := NewAllocator(f, &Options{})
	if err != nil {
		t.Fatal(err)
	}

	dst := bufs.GCache.Get(zappy.MaxEncodedLen(maxRq + 1))
	defer bufs.GCache.Put(dst)
	if _, _, _, err := a.makeUsedBlock(dst, make([]byte, maxRq)); err != nil {
		t.Fatal(err)
	}

	if _, _, _, err := a.makeUsedBlock(dst, make([]byte, maxRq+1)); err == nil {
		t.Fatal("unexpected success")
	}
}

func stableRef(m map[int64][]byte) (r []struct {
	h int64
	b []byte
}) {
	a := make(sortutil.Int64Slice, 0, len(m))
	for k := range m {
		a = append(a, k)
	}
	sort.Sort(a)
	for _, v := range a {
		r = append(r, struct {
			h int64
			b []byte
		}{v, m[v]})
	}
	return
}

func TestAllocatorRnd(t *testing.T) {
	N := *testN

	for cc := 0; cc < 2; cc++ {
		rng := rand.New(rand.NewSource(42))
		f := NewMemFiler()
		a, err := newPAllocator(f)
		if err != nil {
			t.Fatal(err)
		}

		balance := 0

		bad := func() bool {
			if a.Compress {
				return false
			}

			actual := a.stats.TotalAtoms - a.stats.FreeAtoms - a.stats.Relocations
			if int64(balance) != actual {
				t.Logf("balance: %d, actual %d\n%#v", balance, actual, a.stats)
				return true
			}

			return false
		}

		if cc != 0 {
			a.Compress = true
		}
		ref := map[int64][]byte{}

		for pass := 0; pass < 2; pass++ {

			// A) Alloc N blocks
			for i := 0; i < N; i++ {
				rq := rng.Int31n(int32(*allocRndTestLimit))
				if rq%127 == 0 {
					rq = 3 * maxRq / 4
				}
				if rq%11 == 0 {
					rq %= 23
				}
				if hl := *allocRndTestHardLimit; hl != 0 {
					rq = rq % int32(hl)
				}
				b := make([]byte, rq)
				for j := range b {
					b[j] = byte(rng.Int())
				}
				if rq > 300 {
					for i := 100; i < 200; i++ {
						b[i] = 'A' // give compression a chance
					}
				}

				balance += n2atoms(len(b))
				h, err := a.Alloc(b)
				if err != nil || bad() {
					dump(a, t)
					t.Fatalf(
						"A) N %d, kind %d, pass %d, i:%d, len(b):%d(%#x), err %v",
						N, 0, pass, i, len(b), len(b), err,
					)
				}

				ref[h] = b
			}

			var rb []byte

			// B) Check them back
			for h, wb := range ref {
				if rb, err = a.Get(rb, h); err != nil {
					dump(a, t)
					t.Fatal("B)", err)
				}

				if !bytes.Equal(rb, wb) {
					dump(a, t)
					t.Fatalf("B) h %d", h)
				}
			}

			nf := 0
			// C) Free every third block
			for _, v := range stableRef(ref) {
				h, b := v.h, v.b
				if rng.Int()%3 != 0 {
					continue
				}

				balance -= n2atoms(len(b))
				if err = a.Free(h); err != nil || bad() {
					dump(a, t)
					t.Fatal(err)
				}

				delete(ref, h)
				nf++
			}

			// D) Check them back
			for h, wb := range ref {
				if rb, err = a.Get(rb, h); err != nil {
					dump(a, t)
					t.Fatal("D)", err)
				}

				if !bytes.Equal(rb, wb) {
					dump(a, t)
					t.Fatalf("D) h %d", h)
				}
			}

			// E) Resize every block remaining
			for _, v := range stableRef(ref) {
				h, wb := v.h, append([]byte(nil), v.b...)
				len0 := len(wb)
				switch rng.Int() & 1 {
				case 0:
					wb = wb[:len(wb)*3/4]
				case 1:
					wb = append(wb, wb...)
				}
				if len(wb) > maxRq {
					wb = wb[:maxRq]
				}

				for j := range wb {
					wb[j] = byte(rng.Int())
				}
				if len(wb) > 300 {
					for i := 100; i < 200; i++ {
						wb[i] = 'D' // give compression a chance
					}
				}
				a0, a1 := n2atoms(len0), n2atoms(len(wb))
				balance = balance - a0 + a1
				if err := a.Realloc(h, wb); err != nil || bad() {
					dump(a, t)
					t.Fatalf(
						"D) h:%#x, len(b):%#4x, len(wb): %#x, err %v",
						h, len0, len(wb), err,
					)
				}

				if err = cacheAudit(a.m, &a.lru); err != nil {
					t.Fatal(err)
				}

				ref[h] = wb
			}

			// F) Check them back
			for h, wb := range ref {
				if rb, err = a.Get(rb, h); err != nil {
					dump(a, t)
					t.Fatal("E)", err)
				}

				if !bytes.Equal(rb, wb) {
					dump(a, t)
					t.Fatalf("E) h %d", h)
				}
			}
		}

		if cc == 0 {
			sz, err := f.Size()
			if err != nil {
				t.Fatal(err)
			}

			t.Logf(
				"kind %d, AllocAtoms %7d, AllocBytes %7d, FreeAtoms %7d, Relocations %7d, TotalAtoms %7d, f.Size %7d, space eff %.2f%%",
				0, a.stats.AllocAtoms, a.stats.AllocBytes, a.stats.FreeAtoms, a.stats.Relocations, a.stats.TotalAtoms, sz, 100*float64(a.stats.AllocBytes)/float64(sz),
			)
		}
		// Free everything
		for h, b := range ref {
			balance -= n2atoms(len(b))
			if err = a.Free(h); err != nil || bad() {
				dump(a, t)
				t.Fatal(err)
			}
		}

		sz, err := a.f.Size()
		if err != nil {
			t.Fatal(err)
		}

		if g, e := sz, int64(fltSz); g != e {
			dump(a, t)
			t.Fatal(g, e)
		}
	}
}

func TestRollbackAllocator(t *testing.T) {
	f := NewMemFiler()
	var r *RollbackFiler
	r, err := NewRollbackFiler(f,
		func(sz int64) (err error) {
			if err = f.Truncate(sz); err != nil {
				return err
			}

			return f.Sync()
		},
		f,
	)
	if err != nil {
		t.Fatal(err)
	}

	if err := r.BeginUpdate(); err != nil { // BeginUpdate 0->1
		t.Fatal(err)
	}

	a, err := NewAllocator(r, &Options{})
	if err != nil {
		t.Fatal(err)
	}

	h, err := a.Alloc(nil)
	if err != nil {
		t.Fatal(err)
	}

	if h != 1 {
		t.Fatal(h)
	}

	// | 1 |

	h, err = a.Alloc(nil)
	if err != nil {
		t.Fatal(err)
	}

	if h != 2 {
		t.Fatal(h)
	}

	// | 1 | 2 |
	h, err = a.Alloc(nil)
	if err != nil {
		t.Fatal(err)
	}

	if h != 3 {
		t.Fatal(h)
	}

	// | 1 | 2 | 3 |
	if err = a.Free(2); err != nil {
		t.Fatal(err)
	}

	// | 1 | free | 3 |
	if err := r.BeginUpdate(); err != nil { // BeginUpdate 1->2
		t.Fatal(err)
	}

	h, err = a.Alloc(nil)
	if err != nil {
		t.Fatal(err)
	}

	if h != 2 {
		t.Fatal(h)
	}

	// | 1 | 2 | 3 |
	if err := r.Rollback(); err != nil { // Rollback 2->1
		t.Fatal(err)
	}

	// | 1 | free | 3 |
	h, err = a.Alloc(nil)
	if err != nil {
		t.Fatal(err)
	}

	if h != 2 {
		t.Fatal(h)
	}

	// | 1 | 2 | 3 |
	if err := a.Verify(NewMemFiler(), nil, nil); err != nil {
		t.Fatal(err)
	}
}

func benchmarkAllocatorAlloc(b *testing.B, f Filer, sz int) {
	b.SetBytes(int64(sz))

	if err := f.BeginUpdate(); err != nil {
		b.Error(err)
		return
	}

	a, err := NewAllocator(f, &Options{})
	if err != nil {
		b.Error(err)
		return
	}

	if err = f.EndUpdate(); err != nil {
		b.Error(err)
		return
	}

	v := make([]byte, sz)
	runtime.GC()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		if err = f.BeginUpdate(); err != nil {
			b.Error(err)
			return
		}

		if h, err := a.Alloc(v); h <= 0 || err != nil {
			f.EndUpdate()
			b.Error(h, err)
			return
		}

		if err = f.EndUpdate(); err != nil {
			b.Error(err)
			return
		}
	}
}

func benchmarkAllocatorAllocMemFiler(b *testing.B, sz int) {
	f := NewMemFiler()
	benchmarkAllocatorAlloc(b, f, sz)
}

func BenchmarkAllocatorAllocMemFiler1e0(b *testing.B) {
	benchmarkAllocatorAllocMemFiler(b, 0)
}

func BenchmarkAllocatorAllocMemFiler1e1(b *testing.B) {
	benchmarkAllocatorAllocMemFiler(b, 1e1)
}

func BenchmarkAllocatorAllocMemFiler1e2(b *testing.B) {
	benchmarkAllocatorAllocMemFiler(b, 1e2)
}

func BenchmarkAllocatorAllocMemFiler1e3(b *testing.B) {
	benchmarkAllocatorAllocMemFiler(b, 1e3)
}

func benchmarkAllocatorAllocSimpleFileFiler(b *testing.B, sz int) {
	os.Remove(testDbName)
	f, err := os.OpenFile(testDbName, os.O_CREATE|os.O_EXCL|os.O_RDWR, 0600)
	if err != nil {
		b.Fatal(err)
	}

	defer func() {
		f.Close()
		os.Remove(testDbName)
	}()

	benchmarkAllocatorAlloc(b, NewSimpleFileFiler(f), sz)
}

func BenchmarkAllocatorAllocSimpleFileFiler0(b *testing.B) {
	benchmarkAllocatorAllocSimpleFileFiler(b, 0)
}

func BenchmarkAllocatorAllocSimpleFileFiler1e1(b *testing.B) {
	benchmarkAllocatorAllocSimpleFileFiler(b, 1e1)
}

func BenchmarkAllocatorAllocSimpleFileFiler1e2(b *testing.B) {
	benchmarkAllocatorAllocSimpleFileFiler(b, 1e2)
}

func BenchmarkAllocatorAllocSimpleFileFiler1e3(b *testing.B) {
	benchmarkAllocatorAllocSimpleFileFiler(b, 1e3)
}

func benchmarkAllocatorAllocRollbackFiler(b *testing.B, sz int) {
	os.Remove(testDbName)
	f, err := os.OpenFile(testDbName, os.O_CREATE|os.O_EXCL|os.O_RDWR, 0600)
	if err != nil {
		b.Fatal(err)
	}

	defer func() {
		f.Close()
		os.Remove(testDbName)
	}()

	g := NewSimpleFileFiler(f)
	var filer *RollbackFiler
	if filer, err = NewRollbackFiler(
		g,
		func(sz int64) error {
			if err = g.Truncate(sz); err != nil {
				return err
			}

			return g.Sync()
		},
		g,
	); err != nil {
		b.Error(err)
		return
	}

	benchmarkAllocatorAlloc(b, filer, sz)
}

func BenchmarkAllocatorAllocRollbackFiler0(b *testing.B) {
	benchmarkAllocatorAllocRollbackFiler(b, 0)
}

func BenchmarkAllocatorAllocRollbackFiler1e1(b *testing.B) {
	benchmarkAllocatorAllocRollbackFiler(b, 1e1)
}

func BenchmarkAllocatorAllocRollbackFiler1e2(b *testing.B) {
	benchmarkAllocatorAllocRollbackFiler(b, 1e2)
}

func BenchmarkAllocatorAllocRollbackFiler1e3(b *testing.B) {
	benchmarkAllocatorAllocRollbackFiler(b, 1e3)
}

func benchmarkAllocatorAllocACIDFiler(b *testing.B, sz int) {
	os.Remove(testDbName)
	os.Remove(walName)
	f, err := os.OpenFile(testDbName, os.O_CREATE|os.O_EXCL|os.O_RDWR, 0600)
	if err != nil {
		b.Fatal(err)
	}

	defer func() {
		f.Close()
		os.Remove(testDbName)
	}()

	wal, err := os.OpenFile(walName, os.O_CREATE|os.O_EXCL|os.O_RDWR, 0600)
	if err != nil {
		b.Fatal(err)
	}

	defer func() {
		wal.Close()
		os.Remove(walName)
	}()

	filer, err := NewACIDFiler(NewSimpleFileFiler(f), wal)
	if err != nil {
		b.Error(err)
		return
	}

	benchmarkAllocatorAlloc(b, filer, sz)
}

func BenchmarkAllocatorAllocACIDFiler0(b *testing.B) {
	benchmarkAllocatorAllocACIDFiler(b, 0)
}

func BenchmarkAllocatorAllocACIDFiler1e1(b *testing.B) {
	benchmarkAllocatorAllocACIDFiler(b, 1e1)
}

func BenchmarkAllocatorAllocACIDFiler1e2(b *testing.B) {
	benchmarkAllocatorAllocACIDFiler(b, 1e2)
}

func BenchmarkAllocatorAllocACIDFiler1e3(b *testing.B) {
	benchmarkAllocatorAllocACIDFiler(b, 1e3)
}

func benchmarkAllocatorRndFree(b *testing.B, f Filer, sz int) {
	b.SetBytes(int64(sz))

	if err := f.BeginUpdate(); err != nil {
		b.Error(err)
		return
	}

	a, err := NewAllocator(f, &Options{})
	if err != nil {
		b.Error(err)
		return
	}

	if err = f.EndUpdate(); err != nil {
		b.Error(err)
		return
	}

	v := make([]byte, sz)
	ref := map[int64]struct{}{}
	for i := 0; i < b.N; i++ {
		if err = f.BeginUpdate(); err != nil {
			b.Error(err)
			return
		}

		h, err := a.Alloc(v)
		if h <= 0 || err != nil {
			f.EndUpdate()
			b.Error(h, err)
			return
		}

		ref[h] = struct{}{}

		if err = f.EndUpdate(); err != nil {
			b.Error(err)
			return
		}
	}
	runtime.GC()
	b.ResetTimer()
	for h := range ref {
		if err = f.BeginUpdate(); err != nil {
			b.Error(err)
			return
		}

		if err = a.Free(h); err != nil {
			f.EndUpdate()
			b.Error(h, err)
			return
		}

		if err = f.EndUpdate(); err != nil {
			b.Error(err)
			return
		}
	}
}

func benchmarkAllocatorRndFreeMemFiler(b *testing.B, sz int) {
	f := NewMemFiler()
	benchmarkAllocatorRndFree(b, f, sz)
}

func BenchmarkAllocatorRndFreeMemFiler0(b *testing.B) {
	benchmarkAllocatorRndFreeMemFiler(b, 0)
}

func BenchmarkAllocatorRndFreeMemFiler1e1(b *testing.B) {
	benchmarkAllocatorRndFreeMemFiler(b, 1e1)
}

func BenchmarkAllocatorRndFreeMemFiler1e2(b *testing.B) {
	benchmarkAllocatorRndFreeMemFiler(b, 1e2)
}

func BenchmarkAllocatorRndFreeMemFiler1e3(b *testing.B) {
	benchmarkAllocatorRndFreeMemFiler(b, 1e3)
}

func benchmarkAllocatorRndFreeSimpleFileFiler(b *testing.B, sz int) {
	os.Remove(testDbName)
	<-time.After(5 * time.Second)
	f, err := os.OpenFile(testDbName, os.O_CREATE|os.O_EXCL|os.O_RDWR, 0600)
	if err != nil {
		b.Fatal(err)
	}

	defer func() {
		f.Close()
		os.Remove(testDbName)
	}()

	benchmarkAllocatorRndFree(b, NewSimpleFileFiler(f), sz)
}

func BenchmarkAllocatorRndFreeSimpleFileFiler0(b *testing.B) {
	benchmarkAllocatorRndFreeSimpleFileFiler(b, 0)
}

func BenchmarkAllocatorRndFreeSimpleFileFiler1e1(b *testing.B) {
	benchmarkAllocatorRndFreeSimpleFileFiler(b, 1e1)
}

func BenchmarkAllocatorRndFreeSimpleFileFiler1e2(b *testing.B) {
	benchmarkAllocatorRndFreeSimpleFileFiler(b, 1e2)
}

func BenchmarkAllocatorRndFreeSimpleFileFiler1e3(b *testing.B) {
	benchmarkAllocatorRndFreeSimpleFileFiler(b, 1e3)
}

func benchmarkAllocatorRndFreeRollbackFiler(b *testing.B, sz int) {
	os.Remove(testDbName)
	<-time.After(5 * time.Second)
	f, err := os.OpenFile(testDbName, os.O_CREATE|os.O_EXCL|os.O_RDWR, 0600)
	if err != nil {
		b.Fatal(err)
	}

	defer func() {
		f.Close()
		os.Remove(testDbName)
	}()

	g := NewSimpleFileFiler(f)
	var filer *RollbackFiler
	if filer, err = NewRollbackFiler(
		g,
		func(sz int64) error {
			if err = g.Truncate(sz); err != nil {
				return err
			}

			return g.Sync()
		},
		g,
	); err != nil {
		b.Error(err)
		return
	}

	benchmarkAllocatorRndFree(b, filer, sz)
}

func BenchmarkAllocatorRndFreeRollbackFiler0(b *testing.B) {
	benchmarkAllocatorRndFreeRollbackFiler(b, 0)
}

func BenchmarkAllocatorRndFreeRollbackFiler1e1(b *testing.B) {
	benchmarkAllocatorRndFreeRollbackFiler(b, 1e1)
}

func BenchmarkAllocatorRndFreeRollbackFiler1e2(b *testing.B) {
	benchmarkAllocatorRndFreeRollbackFiler(b, 1e2)
}

func BenchmarkAllocatorRndFreeRollbackFiler1e3(b *testing.B) {
	benchmarkAllocatorRndFreeRollbackFiler(b, 1e3)
}

func benchmarkAllocatorRndFreeACIDFiler(b *testing.B, sz int) {
	os.Remove(testDbName)
	os.Remove(walName)
	<-time.After(5 * time.Second)
	f, err := os.OpenFile(testDbName, os.O_CREATE|os.O_EXCL|os.O_RDWR, 0600)
	if err != nil {
		b.Fatal(err)
	}

	defer func() {
		f.Close()
		os.Remove(testDbName)
	}()

	wal, err := os.OpenFile(walName, os.O_CREATE|os.O_EXCL|os.O_RDWR, 0600)
	if err != nil {
		b.Fatal(err)
	}

	defer func() {
		wal.Close()
		os.Remove(walName)
	}()

	filer, err := NewACIDFiler(NewSimpleFileFiler(f), wal)
	if err != nil {
		b.Error(err)
		return
	}

	benchmarkAllocatorRndFree(b, filer, sz)
}

func BenchmarkAllocatorRndFreeACIDFiler0(b *testing.B) {
	benchmarkAllocatorRndFreeACIDFiler(b, 0)
}

func BenchmarkAllocatorRndFreeACIDFiler1e1(b *testing.B) {
	benchmarkAllocatorRndFreeACIDFiler(b, 1e1)
}

func BenchmarkAllocatorRndFreeACIDFiler1e2(b *testing.B) {
	benchmarkAllocatorRndFreeACIDFiler(b, 1e2)
}

func BenchmarkAllocatorRndFreeACIDFiler1e3(b *testing.B) {
	benchmarkAllocatorRndFreeACIDFiler(b, 1e3)
}

func benchmarkAllocatorRndGet(b *testing.B, f Filer, sz int) {
	b.SetBytes(int64(sz))

	if err := f.BeginUpdate(); err != nil {
		b.Error(err)
		return
	}

	a, err := NewAllocator(f, &Options{})
	if err != nil {
		b.Error(err)
		return
	}

	if err = f.EndUpdate(); err != nil {
		b.Error(err)
		return
	}

	v := make([]byte, sz)
	ref := map[int64]struct{}{}
	if err = f.BeginUpdate(); err != nil {
		b.Error(err)
		return
	}

	for i := 0; i < b.N; i++ {
		h, err := a.Alloc(v)
		if h <= 0 || err != nil {
			f.EndUpdate()
			b.Error(h, err)
			return
		}

		ref[h] = struct{}{}

	}
	if err = f.EndUpdate(); err != nil {
		b.Error(err)
		return
	}

	runtime.GC()
	b.ResetTimer()
	for h := range ref {
		if err = f.BeginUpdate(); err != nil {
			b.Error(err)
			return
		}

		if _, err = a.Get(v, h); err != nil {
			f.EndUpdate()
			b.Error(h, err)
			return
		}

		if err = f.EndUpdate(); err != nil {
			b.Error(err)
			return
		}
	}
}

func benchmarkAllocatorRndGetMemFiler(b *testing.B, sz int) {
	f := NewMemFiler()
	benchmarkAllocatorRndGet(b, f, sz)
}

func BenchmarkAllocatorRndGetMemFiler0(b *testing.B) {
	benchmarkAllocatorRndGetMemFiler(b, 0)
}

func BenchmarkAllocatorRndGetMemFiler1e1(b *testing.B) {
	benchmarkAllocatorRndGetMemFiler(b, 1e1)
}

func BenchmarkAllocatorRndGetMemFiler1e2(b *testing.B) {
	benchmarkAllocatorRndGetMemFiler(b, 1e2)
}

func BenchmarkAllocatorRndGetMemFiler1e3(b *testing.B) {
	benchmarkAllocatorRndGetMemFiler(b, 1e3)
}

func benchmarkAllocatorRndGetSimpleFileFiler(b *testing.B, sz int) {
	os.Remove(testDbName)
	<-time.After(5 * time.Second)
	f, err := os.OpenFile(testDbName, os.O_CREATE|os.O_EXCL|os.O_RDWR, 0600)
	if err != nil {
		b.Fatal(err)
	}

	defer func() {
		f.Close()
		os.Remove(testDbName)
	}()

	benchmarkAllocatorRndGet(b, NewSimpleFileFiler(f), sz)
}

func BenchmarkAllocatorRndGetSimpleFileFiler0(b *testing.B) {
	benchmarkAllocatorRndGetSimpleFileFiler(b, 0)
}

func BenchmarkAllocatorRndGetSimpleFileFiler1e1(b *testing.B) {
	benchmarkAllocatorRndGetSimpleFileFiler(b, 1e1)
}

func BenchmarkAllocatorRndGetSimpleFileFiler1e2(b *testing.B) {
	benchmarkAllocatorRndGetSimpleFileFiler(b, 1e2)
}

func BenchmarkAllocatorRndGetSimpleFileFiler1e3(b *testing.B) {
	benchmarkAllocatorRndGetSimpleFileFiler(b, 1e3)
}

func benchmarkAllocatorRndGetRollbackFiler(b *testing.B, sz int) {
	os.Remove(testDbName)
	f, err := os.OpenFile(testDbName, os.O_CREATE|os.O_EXCL|os.O_RDWR, 0600)
	if err != nil {
		b.Fatal(err)
	}

	defer func() {
		f.Close()
		os.Remove(testDbName)
	}()

	g := NewSimpleFileFiler(f)
	var filer *RollbackFiler
	if filer, err = NewRollbackFiler(
		g,
		func(sz int64) error {
			if err = g.Truncate(sz); err != nil {
				return err
			}

			return g.Sync()
		},
		g,
	); err != nil {
		b.Error(err)
		return
	}

	benchmarkAllocatorRndGet(b, filer, sz)
}

func BenchmarkAllocatorRndGetRollbackFiler0(b *testing.B) {
	benchmarkAllocatorRndGetRollbackFiler(b, 0)
}

func BenchmarkAllocatorRndGetRollbackFiler1e1(b *testing.B) {
	benchmarkAllocatorRndGetRollbackFiler(b, 1e1)
}

func BenchmarkAllocatorRndGetRollbackFiler1e2(b *testing.B) {
	benchmarkAllocatorRndGetRollbackFiler(b, 1e2)
}

func BenchmarkAllocatorRndGetRollbackFiler1e3(b *testing.B) {
	benchmarkAllocatorRndGetRollbackFiler(b, 1e3)
}

func benchmarkAllocatorRndGetACIDFiler(b *testing.B, sz int) {
	os.Remove(testDbName)
	os.Remove(walName)
	f, err := os.OpenFile(testDbName, os.O_CREATE|os.O_EXCL|os.O_RDWR, 0600)
	if err != nil {
		b.Fatal(err)
	}

	defer func() {
		f.Close()
		os.Remove(testDbName)
	}()

	wal, err := os.OpenFile(walName, os.O_CREATE|os.O_EXCL|os.O_RDWR, 0600)
	if err != nil {
		b.Fatal(err)
	}

	defer func() {
		wal.Close()
		os.Remove(walName)
	}()

	filer, err := NewACIDFiler(NewSimpleFileFiler(f), wal)
	if err != nil {
		b.Error(err)
		return
	}

	benchmarkAllocatorRndGet(b, filer, sz)
}

func BenchmarkAllocatorRndGetACIDFiler0(b *testing.B) {
	benchmarkAllocatorRndGetACIDFiler(b, 0)
}

func BenchmarkAllocatorRndGetACIDFiler1e1(b *testing.B) {
	benchmarkAllocatorRndGetACIDFiler(b, 1e1)
}

func BenchmarkAllocatorRndGetACIDFiler1e2(b *testing.B) {
	benchmarkAllocatorRndGetACIDFiler(b, 1e2)
}

func BenchmarkAllocatorRndGetACIDFiler1e3(b *testing.B) {
	benchmarkAllocatorRndGetACIDFiler(b, 1e3)
}

func TestFltFind(t *testing.T) {
	var f flt

	f.init()
	if h := f.find(1); h != 0 {
		t.Fatal(h)
	}

	// [0]
	f.init()
	f[0].head = 1
	if h := f.find(1); h != 1 || f[0].head != 0 {
		t.Fatal(h)
	}

	f.init()
	f[0].head = 1
	if h := f.find(2); h != 0 || f[0].head == 0 {
		t.Fatal(h)
	}

	// [1]
	f.init()
	f[1].head = 1
	if h := f.find(1); h != 1 || f[1].head != 0 {
		t.Fatal("\n", f, h)
	}

	f.init()
	f[1].head = 1
	if h := f.find(2); h != 1 || f[1].head != 0 {
		t.Fatal(f, h)
	}

	f.init()
	f[1].head = 1
	if h := f.find(3); h != 0 || f[1].head == 0 {
		t.Fatal(h)
	}

	// [2]
	f.init()
	f[2].head = 1
	if h := f.find(1); h != 1 || f[2].head != 0 {
		t.Fatal(h)
	}

	f.init()
	f[2].head = 1
	if h := f.find(2); h != 1 || f[2].head != 0 {
		t.Fatal(h)
	}

	f.init()
	f[2].head = 1
	if h := f.find(3); h != 1 || f[2].head != 0 {
		t.Fatal(h)
	}

	f.init()
	f[2].head = 1
	if h := f.find(4); h != 1 || f[2].head != 0 {
		t.Fatal(h)
	}

	f.init()
	f[2].head = 1
	if h := f.find(5); h != 0 || f[2].head == 0 {
		t.Fatal(h)
	}
}

func TestFltHead(t *testing.T) {
	var f flt
	f.init()
	if h := f.head(1); h != 0 {
		t.Fatal(h)
	}

	// [0]
	f.init()
	f[0].head = 1
	if h := f.head(1); h != 1 {
		t.Fatal(h)
	}

	f.init()
	f[0].head = 1
	if h := f.head(2); h != 0 {
		t.Fatal(h)
	}

	// [1]
	f.init()
	f[1].head = 1
	if h := f.head(1); h != 0 {
		t.Fatal(h)
	}

	f.init()
	f[1].head = 1
	if h := f.head(2); h != 1 {
		t.Fatal(h)
	}

	f.init()
	f[1].head = 1
	if h := f.head(3); h != 1 {
		t.Fatal(h)
	}

	f.init()
	f[1].head = 1
	if h := f.head(4); h != 0 {
		t.Fatal(h)
	}

	// [2]
	f.init()
	f[2].head = 1
	if h := f.head(1); h != 0 {
		t.Fatal(h)
	}

	f.init()
	f[2].head = 1
	if h := f.head(2); h != 0 {
		t.Fatal(h)
	}

	f.init()
	f[2].head = 1
	if h := f.head(3); h != 0 {
		t.Fatal(h)
	}

	f.init()
	f[2].head = 1
	if h := f.head(4); h != 1 {
		t.Fatal(h)
	}

	f.init()
	f[2].head = 1
	if h := f.head(5); h != 1 {
		t.Fatal(h)
	}

	f.init()
	f[2].head = 1
	if h := f.head(6); h != 1 {
		t.Fatal(h)
	}

	f.init()
	f[2].head = 1
	if h := f.head(7); h != 1 {
		t.Fatal(h)
	}

	f.init()
	f[2].head = 1
	if h := f.head(8); h != 0 {
		t.Fatal(h)
	}

}