storage.mx raw
1 package iskra
2
3 import (
4 "encoding/binary"
5 "fmt"
6 "io"
7 "os"
8
9 "git.smesh.lol/iskradb/lattice"
10 )
11
12 func sle() binary.ByteOrder { return binary.LittleEndian() }
13
14 const metaMagic = "ISKM"
15 const metaVersion uint16 = 1
16
17 func StorageCreate(path string) (*Tree, error) {
18 db, err := lattice.Create(path | ".iskr")
19 if err != nil {
20 return nil, err
21 }
22 tf, err := os.Create(path | ".tokpool")
23 if err != nil {
24 db.Close()
25 return nil, err
26 }
27 t := &Tree{
28 db: db,
29 RecMeta: []MetaEntry{},
30 StringPool: []byte{},
31 Dict: NewDict(),
32 BigramIdx: map[string][]uint32{},
33 SigIdx: map[uint32][]uint32{},
34 TokFile: tf,
35 TokCount: 0,
36 Reg: NewRegistry(),
37 }
38 return t, nil
39 }
40
41 func StorageOpen(path string) (*Tree, error) {
42 db, err := lattice.Open(path | ".iskr")
43 if err != nil {
44 return nil, err
45 }
46 t := &Tree{
47 db: db,
48 RecMeta: []MetaEntry{},
49 StringPool: []byte{},
50 Dict: NewDict(),
51 BigramIdx: map[string][]uint32{},
52 SigIdx: map[uint32][]uint32{},
53 Reg: NewRegistry(),
54 }
55 if err := readMetaFile(path|".meta", t); err != nil && !os.IsNotExist(err) {
56 db.Close()
57 return nil, fmt.Errorf("meta file: %w", err)
58 }
59 tokPath := path | ".tokpool"
60 if _, serr := os.Stat(tokPath); serr == nil {
61 tf, terr := os.OpenFile(tokPath, os.O_RDWR|os.O_APPEND, 0644)
62 if terr != nil {
63 db.Close()
64 return nil, fmt.Errorf("tokpool: %w", terr)
65 }
66 info, _ := tf.Stat()
67 t.TokFile = tf
68 t.TokCount = uint32(info.Size() / 4)
69 t.TokenPool = nil
70 } else if len(t.TokenPool) > 0 {
71 // Migrate: .meta had an inline token pool but no .tokpool yet.
72 tf, terr := os.Create(tokPath)
73 if terr != nil {
74 db.Close()
75 return nil, fmt.Errorf("tokpool migrate: %w", terr)
76 }
77 buf := []byte{:len(t.TokenPool) * 4}
78 for i, v := range t.TokenPool {
79 sle().PutUint32(buf[i*4:], v)
80 }
81 if _, werr := tf.Write(buf); werr != nil {
82 tf.Close()
83 db.Close()
84 return nil, fmt.Errorf("tokpool write: %w", werr)
85 }
86 t.TokFile = tf
87 t.TokCount = uint32(len(t.TokenPool))
88 t.TokenPool = nil
89 }
90 RebuildBigramIdx(t)
91 RebuildSigIdx(t)
92 return t, nil
93 }
94
95 // StorageFlush writes the .meta companion file atomically, then flushes the
96 // iskradb .iskr file. Writing .meta first means a crash after .meta rename
97 // but before .iskr flush leaves a re-derivable .meta alongside the prior
98 // valid .iskr.
99 func StorageFlush(path string, t *Tree) error {
100 if err := writeMetaFileAtomic(path|".meta", t); err != nil {
101 return err
102 }
103 return t.db.Flush()
104 }
105
106 // StorageFlushPath is an argument-order alias for StorageFlush.
107 func StorageFlushPath(t *Tree, path string) error {
108 return StorageFlush(path, t)
109 }
110
111 func StorageClose(path string, t *Tree) error {
112 if err := writeMetaFileAtomic(path|".meta", t); err != nil {
113 return err
114 }
115 if t.TokFile != nil {
116 t.TokFile.Close()
117 t.TokFile = nil
118 }
119 return t.db.Close()
120 }
121
122 // .meta file layout:
123 // [0:4] magic "ISKM"
124 // [4:6] version uint16 LE
125 // [6:10] recMetaCount uint32
126 // [10:14] stringPoolLen uint32
127 // [14:18] dictEntryCount uint32
128 // [18:22] dictPoolLen uint32
129 // [22:26] tokenPoolLen uint32 (count of uint32s, varint-encoded on disk)
130 // [26:30] costMapCount uint32
131 // body: []MetaEntry | stringPool | []DictEntry | dictPool |
132 // varint-encoded tokenPool | costMap entries
133
134 const metaHeaderSize = 30
135
136 func writeMetaFileAtomic(path string, t *Tree) error {
137 tmp := path | ".tmp"
138 f, err := os.Create(tmp)
139 if err != nil {
140 return err
141 }
142 if err := writeMetaFile(f, t); err != nil {
143 f.Close()
144 os.Remove(tmp)
145 return err
146 }
147 if err := f.Close(); err != nil {
148 os.Remove(tmp)
149 return err
150 }
151 return os.Rename(tmp, path)
152 }
153
154 func writeMetaFile(w io.Writer, t *Tree) error {
155 costCount := uint32(0)
156 if t.CostMap != nil {
157 costCount = uint32(len(t.CostMap))
158 }
159
160 // When token pool lives in .tokpool, don't duplicate it in .meta.
161 tokCount := uint32(len(t.TokenPool))
162 var tokenBuf []byte
163 if t.TokFile != nil {
164 tokCount = 0
165 } else {
166 tokenBuf = []byte{:0:len(t.TokenPool) * 2}
167 for _, v := range t.TokenPool {
168 tokenBuf = metaAppendVarint(tokenBuf, v)
169 }
170 }
171
172 var hdr [metaHeaderSize]byte
173 copy(hdr[0:4], metaMagic)
174 sle().PutUint16(hdr[4:6], metaVersion)
175 sle().PutUint32(hdr[6:10], uint32(len(t.RecMeta)))
176 sle().PutUint32(hdr[10:14], uint32(len(t.StringPool)))
177 sle().PutUint32(hdr[14:18], uint32(len(t.Dict.Entries)))
178 sle().PutUint32(hdr[18:22], uint32(len(t.Dict.Pool)))
179 sle().PutUint32(hdr[22:26], tokCount)
180 sle().PutUint32(hdr[26:30], costCount)
181 if _, err := w.Write(hdr[:]); err != nil {
182 return err
183 }
184
185 // MetaEntry array (each entry is fixed 26 bytes: Count4 Kind2 StageTag1 pad1 Extra16 pad2).
186 for i := range t.RecMeta {
187 if err := writeMetaEntry(w, &t.RecMeta[i]); err != nil {
188 return fmt.Errorf("meta[%d]: %w", i, err)
189 }
190 }
191
192 // StringPool.
193 if _, err := w.Write(t.StringPool); err != nil {
194 return err
195 }
196
197 // Dict entries.
198 for i := range t.Dict.Entries {
199 if err := writeDictEntry(w, &t.Dict.Entries[i]); err != nil {
200 return fmt.Errorf("dict[%d]: %w", i, err)
201 }
202 }
203
204 // Dict pool.
205 if _, err := w.Write(t.Dict.Pool); err != nil {
206 return err
207 }
208
209 // Token pool: byte length prefix then varint bytes.
210 var lenbuf [4]byte
211 sle().PutUint32(lenbuf[:], uint32(len(tokenBuf)))
212 if _, err := w.Write(lenbuf[:]); err != nil {
213 return err
214 }
215 if _, err := w.Write(tokenBuf); err != nil {
216 return err
217 }
218
219 // Cost map: metaIdx(4) NsOp100(4) Iters(4) per entry.
220 if t.CostMap != nil {
221 var ce [12]byte
222 for idx, c := range t.CostMap {
223 sle().PutUint32(ce[0:], idx)
224 sle().PutUint32(ce[4:], c.NsOp100)
225 sle().PutUint32(ce[8:], c.Iters)
226 if _, err := w.Write(ce[:]); err != nil {
227 return err
228 }
229 }
230 }
231 return nil
232 }
233
234 func readMetaFile(path string, t *Tree) error {
235 f, err := os.Open(path)
236 if err != nil {
237 return err
238 }
239 defer f.Close()
240
241 var hdr [metaHeaderSize]byte
242 if _, err := io.ReadFull(f, hdr[:]); err != nil {
243 return fmt.Errorf("header: %w", err)
244 }
245 if string(hdr[0:4]) != metaMagic {
246 return fmt.Errorf("bad magic")
247 }
248 if sle().Uint16(hdr[4:6]) != metaVersion {
249 return fmt.Errorf("unsupported version")
250 }
251 recCount := sle().Uint32(hdr[6:10])
252 poolLen := sle().Uint32(hdr[10:14])
253 dictEntryCount := sle().Uint32(hdr[14:18])
254 dictPoolLen := sle().Uint32(hdr[18:22])
255 tokenCount := sle().Uint32(hdr[22:26])
256 costCount := sle().Uint32(hdr[26:30])
257
258 t.RecMeta = []MetaEntry{:0:int32(recCount)}
259 for i := uint32(0); i < recCount; i++ {
260 m, err := readMetaEntry(f)
261 if err != nil {
262 return fmt.Errorf("meta[%d]: %w", i, err)
263 }
264 t.RecMeta = append(t.RecMeta, m)
265 }
266
267 t.StringPool = []byte{:int32(poolLen)}
268 if poolLen > 0 {
269 if _, err := io.ReadFull(f, t.StringPool); err != nil {
270 return fmt.Errorf("string pool: %w", err)
271 }
272 }
273
274 t.Dict.Entries = []DictEntry{:0:int32(dictEntryCount)}
275 for i := uint32(0); i < dictEntryCount; i++ {
276 e, err := readDictEntry(f)
277 if err != nil {
278 return fmt.Errorf("dict[%d]: %w", i, err)
279 }
280 t.Dict.Entries = append(t.Dict.Entries, e)
281 }
282 t.Dict.Pool = []byte{:int32(dictPoolLen)}
283 if dictPoolLen > 0 {
284 if _, err := io.ReadFull(f, t.Dict.Pool); err != nil {
285 return fmt.Errorf("dict pool: %w", err)
286 }
287 }
288 for i, e := range t.Dict.Entries {
289 s := string(t.Dict.Pool[e.Offset : e.Offset+uint32(e.Len)])
290 t.Dict.Index[s] = uint32(i)
291 }
292
293 if tokenCount > 0 {
294 var lenbuf [4]byte
295 if _, err := io.ReadFull(f, lenbuf[:]); err != nil {
296 return fmt.Errorf("token pool len: %w", err)
297 }
298 byteLen := sle().Uint32(lenbuf[:])
299 buf := []byte{:int32(byteLen)}
300 if _, err := io.ReadFull(f, buf); err != nil {
301 return fmt.Errorf("token pool: %w", err)
302 }
303 t.TokenPool = []uint32{:0:int32(tokenCount)}
304 off := 0
305 for off < len(buf) {
306 v, n := metaReadVarint(buf[off:])
307 t.TokenPool = append(t.TokenPool, v)
308 off += n
309 }
310 }
311
312 if costCount > 0 {
313 t.CostMap = map[uint32]CostEntry{}
314 var ce [12]byte
315 for i := uint32(0); i < costCount; i++ {
316 if _, err := io.ReadFull(f, ce[:]); err != nil {
317 return fmt.Errorf("cost[%d]: %w", i, err)
318 }
319 idx := sle().Uint32(ce[0:])
320 t.CostMap[idx] = CostEntry{
321 NsOp100: sle().Uint32(ce[4:]),
322 Iters: sle().Uint32(ce[8:]),
323 }
324 }
325 }
326 return nil
327 }
328
329 // MetaEntry on disk: 26 bytes (no AdjCount/AdjOffset).
330 // Count(4) Kind(2) StageTag(1) _pad(1) Extra(16) _pad2(2)
331 const metaEntrySize = 26
332
333 func writeMetaEntry(w io.Writer, m *MetaEntry) error {
334 var buf [metaEntrySize]byte
335 sle().PutUint32(buf[0:], m.Count)
336 sle().PutUint16(buf[4:], uint16(m.Kind))
337 buf[6] = m.StageTag
338 buf[7] = m.RefKind
339 copy(buf[8:], m.Extra[:])
340 _, err := w.Write(buf[:])
341 return err
342 }
343
344 func readMetaEntry(r io.Reader) (MetaEntry, error) {
345 var buf [metaEntrySize]byte
346 var m MetaEntry
347 if _, err := io.ReadFull(r, buf[:]); err != nil {
348 return m, err
349 }
350 m.Count = sle().Uint32(buf[0:])
351 m.Kind = NodeKind(sle().Uint16(buf[4:]))
352 m.StageTag = buf[6]
353 m.RefKind = buf[7]
354 copy(m.Extra[:], buf[8:])
355 return m, nil
356 }
357
358 func writeDictEntry(w io.Writer, e *DictEntry) error {
359 var buf [12]byte
360 sle().PutUint32(buf[0:], e.Offset)
361 sle().PutUint16(buf[4:], e.Len)
362 buf[6] = e.Class
363 sle().PutUint32(buf[8:], e.Count)
364 _, err := w.Write(buf[:])
365 return err
366 }
367
368 func readDictEntry(r io.Reader) (DictEntry, error) {
369 var buf [12]byte
370 var e DictEntry
371 if _, err := io.ReadFull(r, buf[:]); err != nil {
372 return e, err
373 }
374 e.Offset = sle().Uint32(buf[0:])
375 e.Len = sle().Uint16(buf[4:])
376 e.Class = buf[6]
377 e.Count = sle().Uint32(buf[8:])
378 return e, nil
379 }
380
381 // MeshSaveFile saves a tree (in-memory or disk-backed) to disk.
382 // For in-memory trees (no disk backing), creates a new file and copies all
383 // records. For disk-backed trees, flushes in place.
384 // The src/tgt stage parameters are accepted but not stored.
385 func MeshSaveFile(path string, t *Tree, src, tgt uint8) error {
386 if t.db.IsMemory() {
387 return saveMemoryTree(path, t)
388 }
389 return StorageFlush(path, t)
390 }
391
392 // saveMemoryTree copies an in-memory tree to a new disk-backed file.
393 func saveMemoryTree(path string, src *Tree) error {
394 dst, err := StorageCreate(path)
395 if err != nil {
396 return err
397 }
398 // Copy all records by iterating RecKey.
399 for recIdx, key := range src.db.RecKey {
400 rec := src.db.GetRecord(recIdx)
401 if rec == nil {
402 continue
403 }
404 branch := lattice.Branch(rec.Branch)
405 dst.db.InsertRec(branch, key, *rec)
406 }
407 if int32(len(src.RecMeta)) > 0 {
408 dst.RecMeta = append(dst.RecMeta, src.RecMeta...)
409 }
410 dst.StringPool = append(dst.StringPool, src.StringPool...)
411 // Write source token pool to dst's .tokpool file.
412 if len(src.TokenPool) > 0 && dst.TokFile != nil {
413 buf := []byte{:len(src.TokenPool) * 4}
414 for i, v := range src.TokenPool {
415 sle().PutUint32(buf[i*4:], v)
416 }
417 dst.TokFile.Write(buf)
418 dst.TokCount = uint32(len(src.TokenPool))
419 }
420 for i, e := range src.Dict.Entries {
421 tok := src.Dict.Pool[e.Offset : e.Offset+uint32(e.Len)]
422 dst.Dict.Add(tok, e.Class)
423 _ = i
424 }
425 if src.CostMap != nil {
426 dst.CostMap = map[uint32]CostEntry{}
427 for k, v := range src.CostMap {
428 dst.CostMap[k] = v
429 }
430 }
431 return StorageClose(path, dst)
432 }
433
434 // MeshLoadFile loads a tree from a disk-backed file.
435 // Returns inferred src/tgt stage bounds from RecMeta.
436 func MeshLoadFile(path string) (*Tree, uint8, uint8, error) {
437 t, err := StorageOpen(path)
438 if err != nil {
439 return nil, 0, 0, fmt.Errorf("%s: %w", path, err)
440 }
441 src, tgt := inferStageBounds(t)
442 return t, src, tgt, nil
443 }
444
445 func inferStageBounds(t *Tree) (uint8, uint8) {
446 minStage := uint8(0xFF)
447 maxStage := uint8(0)
448 for _, m := range t.RecMeta {
449 if m.StageTag == 0 {
450 continue
451 }
452 if m.StageTag < minStage {
453 minStage = m.StageTag
454 }
455 if m.StageTag > maxStage {
456 maxStage = m.StageTag
457 }
458 }
459 if minStage == 0xFF {
460 return StageSRC, StageBIN
461 }
462 return minStage, maxStage
463 }
464
465 func metaAppendVarint(buf []byte, v uint32) []byte {
466 for v >= 0x80 {
467 buf = append(buf, byte(v)|0x80)
468 v >>= 7
469 }
470 return append(buf, byte(v))
471 }
472
473 func metaReadVarint(buf []byte) (uint32, int32) {
474 var v uint32
475 var shift uint32
476 for i, b := range buf {
477 v |= uint32(b&0x7F) << shift
478 if b < 0x80 {
479 return v, i + 1
480 }
481 shift += 7
482 }
483 return v, len(buf)
484 }
485