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