/
store.go
193 lines (175 loc) · 5.01 KB
/
store.go
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
package pmap
import (
"encoding/binary"
"errors"
"fmt"
"log"
"os"
"launchpad.net/gommap"
)
/*
A store is a dynamically growing array stored on a memory mapped file.
It manages additions and deletions, but it is indexed by store ids.
An additional data structure is needed to perform fast key-value look-ups.
deleted pairs are never freed.
*/
/*
Binary structure of the store
The store is composed of key-value pairs.
Each pair is represented this way:
4 bytes:
1 bit (MSB) is the pair present?
31 bits key length
4 bytes: value len
Key len bytes: key
Value len bytes: value
Metadata is not saved on the memory-mapped file.
*/
//store stores a list of pairs, in an *unordered* way
type store struct {
deleted uint64 //deleted number of bytes
length uint64 //Total length, index of new items
size uint64 //Allocated size, it remains constant, the store cannot expand itself
osFile *os.File //OS mapped file located at Path
file gommap.MMap //Memory mapped file located at Path
}
const (
headerKeyOffset = 0
headerValueOffset = 4
headerSize = 8
)
//Typical DB usage will access to random positions, this won't be true
//if it is used to store long (more bytes than the page size) pairs
var mmapAdviseFlags = gommap.MADV_RANDOM
//Creates a new Store, set path to "" to create an anonymous memory-mapped region (not FS backed)
func newStore(path string, size uint64) *store {
var err error
st := new(store)
st.size = size
if path != "" {
st.osFile, err = os.OpenFile(path, os.O_RDWR|os.O_CREATE|os.O_TRUNC, FilePerms)
if err != nil {
w, _ := os.Getwd()
fmt.Println(w)
panic(err)
}
err = st.osFile.Truncate(int64(st.size))
if err != nil {
panic(err)
}
st.file, err = gommap.Map(st.osFile.Fd(), gommap.PROT_READ|gommap.PROT_WRITE, gommap.MAP_SHARED)
if err != nil {
panic(err)
}
} else {
st.file, err = gommap.MapRegion(0, 0, int64(st.size), gommap.PROT_READ|gommap.PROT_WRITE, gommap.MAP_SHARED|gommap.MAP_ANONYMOUS)
if err != nil {
panic(err)
}
}
st.file.Advise(mmapAdviseFlags)
if err != nil {
panic(err)
}
return st
}
func openStore(path string) *store {
st := new(store)
var err error
st.osFile, err = os.OpenFile(path, os.O_RDWR, FilePerms)
if err != nil {
panic(err)
}
fi, err := st.osFile.Stat()
if err != nil {
panic("Could not obtain stat")
}
st.size = uint64(fi.Size())
st.file, err = gommap.Map(st.osFile.Fd(), gommap.PROT_READ|gommap.PROT_WRITE, gommap.MAP_SHARED)
if err != nil {
panic(err)
}
st.file.Advise(mmapAdviseFlags)
if err != nil {
panic(err)
}
return st
}
//Close the store unmmaping the file and syncing to disk
func (st *store) close() {
if st.file == nil {
panic("Already closed")
}
err := st.file.UnsafeUnmap()
if err != nil {
panic(err)
}
st.file = nil
if st.osFile != nil {
err = st.osFile.Close()
if err != nil {
panic(err)
}
}
}
//Close the store and delete associated files
func (st *store) deleteStore() {
if st.file != nil {
panic("Not closed")
}
if st.osFile != nil {
os.Remove(st.osFile.Name())
}
}
/*
Store access utility functions
*/
func (st *store) keyLen(index uint64) uint32 {
return binary.LittleEndian.Uint32(st.file[index+headerKeyOffset:])
}
func (st *store) valLen(index uint64) uint32 {
return binary.LittleEndian.Uint32(st.file[index+headerValueOffset:])
}
func (st *store) totalLen(index uint64) uint32 {
return st.keyLen(index) + st.valLen(index)
}
func (st *store) setKeyLen(index uint64, x uint32) {
binary.LittleEndian.PutUint32(st.file[index:], x)
}
func (st *store) setValLen(index uint64, x uint32) {
binary.LittleEndian.PutUint32(st.file[index+headerValueOffset:], x)
}
func (st *store) prev(index uint64) int64 {
if int64(index)-4 > 0 {
return int64(index) - 12 - int64(binary.LittleEndian.Uint32(st.file[index-4:index]))
}
return -1
}
//Returns a slice to the selected key
func (st *store) key(index uint64) []byte {
return st.file[index+headerSize : index+headerSize+uint64(st.keyLen(index))]
}
//Returns a slice to the selected value
func (st *store) val(index uint64) []byte { //TODO use uint32 instead of uint64
return st.file[index+headerSize+uint64(st.keyLen(index)) : index+headerSize+uint64(st.totalLen(index))]
}
//Inserts a new pair at the end of the store, it can fail (with a returning error) if the store size limit is reached
func (st *store) put(key, val []byte) (uint32, error) {
size := uint64(4 + 4 + 4 + len(key) + len(val))
//Cache-alignment
//if size <= 64 && st.length%64 >= 32 && (64-st.length%64) < size {
//st.length += 64 - st.length%64
//}
for st.length+size >= st.size {
log.Println("store size limit reached: denied put operation", st.length, st.size, size)
return 0, errors.New("store size limit reached: denied put operation")
}
index := st.length
st.length += size
st.setKeyLen(index, uint32(len(key)))
st.setValLen(index, uint32(len(val)))
copy(st.key(index), key)
copy(st.val(index), val)
binary.LittleEndian.PutUint32(st.file[int(index)+8+len(key)+len(val):], uint32(len(key)+len(val)))
return uint32(index), nil
}