GopherSQL/freelist.go at master · VIDIT45AGARWAL/GopherSQL · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
package main

import (
	"encoding/binary"
)

const FREE_LIST_HEADER = 8
// Calculates how many 16-byte pairs (8 byte ptr + 8 byte version) fit in a page
const FREE_LIST_CAP = (BTREE_PAGE_SIZE - FREE_LIST_HEADER) / 16

type LNode []byte

// [0:8]    next page pointer
// [8:24]   slot 0: ptr(8) + ver(8)
// [24:40]  slot 1: ptr(8) + ver(8)
// [40:56]  slot 2: ptr(8) + ver(8)
// ...

// getNext returns the page ID of the next LNode in the linked list.
func (node LNode) getNext() uint64 {
	return binary.LittleEndian.Uint64(node[0:8])
}

// setNext updates the pointer to the next LNode.
func (node LNode) setNext(next uint64) {
	binary.LittleEndian.PutUint64(node[0:8], next)
}

// getItem retrieves a recycled page ID and its version from the array.
func (node LNode) getItem(idx int) (uint64, uint64) {
	pos := FREE_LIST_HEADER + 16*idx
	ptr := binary.LittleEndian.Uint64(node[pos:])
	ver := binary.LittleEndian.Uint64(node[pos+8:])
	return ptr, ver
}

// setItem writes a newly abandoned page ID and its transaction version.
func (node LNode) setItem(idx int, ptr uint64, ver uint64) {
	pos := FREE_LIST_HEADER + 16*idx
	binary.LittleEndian.PutUint64(node[pos:], ptr)
	binary.LittleEndian.PutUint64(node[pos+8:], ver)
}

// FreeList orchestrates the unrolled linked list on disk.
type FreeList struct {
	get func(uint64) []byte
	new func([]byte) uint64
	set func(uint64) []byte

	headPage uint64
	headSeq  uint64
	tailPage uint64
	tailSeq  uint64

	maxSeq uint64

	// --- Concurrency Fields ---
	maxVer uint64 // the oldest running reader version
	curVer uint64 // the current version number when committing
}

func seq2idx(seq uint64) int {
	return int(seq % FREE_LIST_CAP)
}

func (fl *FreeList) SetMaxSeq() {
	fl.maxSeq = fl.tailSeq
}

func flPop(fl *FreeList) (ptr uint64, head uint64) {
	if fl.headSeq == fl.maxSeq {
		return 0, 0
	}

	node := LNode(fl.get(fl.headPage))
	p, ver := node.getItem(seq2idx(fl.headSeq))

	// CONCURRENCY CHECK: Cannot consume this page if an active transaction might still be looking at it
	if ver > fl.maxVer {
		return 0, 0
	}

	ptr = p
	fl.headSeq++

	if seq2idx(fl.headSeq) == 0 {
		head = fl.headPage
		fl.headPage = node.getNext()

		if fl.headPage == 0 {
			panic("FreeList completely empty (which should be impossible)")
		}
	}
	return ptr, head
}

// PopHead gets 1 item from the list head. Returns 0 on failure.
func (fl *FreeList) PopHead() uint64 {
	ptr, head := flPop(fl)
	if head != 0 {
		fl.PushTail(head)
	}
	return ptr
}

// PushTail adds 1 item to the tail node, tracking the transaction version.
func (fl *FreeList) PushTail(ptr uint64) {
	LNode(fl.set(fl.tailPage)).setItem(seq2idx(fl.tailSeq), ptr, fl.curVer)
	fl.tailSeq++

	if seq2idx(fl.tailSeq) == 0 {
		next, head := flPop(fl)

		if next == 0 {
			next = fl.new(make([]byte, BTREE_PAGE_SIZE))
		}

		LNode(fl.set(fl.tailPage)).setNext(next)
		fl.tailPage = next

		if head != 0 {
			LNode(fl.set(fl.tailPage)).setItem(0, head, fl.curVer)
			fl.tailSeq++
		}
	}
}