Debian Codegraph @

falloc/falloc.go

raw ◀ ▶
Source reconstructed at patch state 0 of 1 — not the installed (fully patched) source.
1 Debian patch touch this file
1 // Copyright (c) 2011 CZ.NIC z.s.p.o. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 // blame: jnml, labs.nic.cz
6
7 /*
8
9 This is an mostly (WIP) conforming implementation of the "specs" in docs.go.
10
11 The main incompletness is support for only one kind of FTL, though this table kind is still per "specs".
12
13 */
14
15 package falloc // import "modernc.org/fileutil/falloc"
16
17 import (
18 "bytes"
19 "modernc.org/fileutil/storage"
20 "sync"
21 )
22
23 // Handle is a reference to a block in a file/store.
24 // Handle is an uint56 wrapped in an in64, i.e. the most significant byte must be always zero.
25 type Handle int64
26
27 // Put puts the 7 least significant bytes of h into b. The MSB of h should be zero.
28 func (h Handle) Put(b []byte) {
29 for ofs := 6; ofs >= 0; ofs-- {
30 b[ofs] = byte(h)
31 h >>= 8
32 }
33 }
34
35 // Get gets the 7 least significant bytes of h from b. The MSB of h is zeroed.
36 func (h *Handle) Get(b []byte) {
37 var x Handle
38 for ofs := 0; ofs <= 6; ofs++ {
39 x = x<<8 | Handle(b[ofs])
40 }
41 *h = x
42 }
43
44 // File is a file/store with space allocation/deallocation support.
45 type File struct {
46 f storage.Accessor
47 atoms int64 // current file size in atom units
48 canfree int64 // only blocks >= canfree can be subject to Free()
49 freetab [3857]int64 // freetab[0] is unused, freetab[1] is size 1 ptr, freetab[2] is size 2 ptr, ...
50 rwm sync.RWMutex
51 }
52
53 func (f *File) read(b []byte, off int64) {
54 if n, err := f.f.ReadAt(b, off); n != len(b) {
55 panic(&ERead{f.f.Name(), off, err})
56 }
57 }
58
59 func (f *File) write(b []byte, off int64) {
60 if n, err := f.f.WriteAt(b, off); n != len(b) {
61 panic(&EWrite{f.f.Name(), off, err})
62 }
63 }
64
65 var ( // R/O
66 hdr = []byte{0x0f, 0xf1, 0xc1, 0xa1, 0xfe, 0xa5, 0x1b, 0x1e, 0, 0, 0, 0, 0, 0, 2, 0} // free lists table @2
67 empty = make([]byte, 16)
68 zero = []byte{0}
69 zero7 = make([]byte, 7)
70 )
71
72 // New returns a new File backed by store or an error if any.
73 // Any existing data in store are discarded.
74 func New(store storage.Accessor) (f *File, err error) {
75 f = &File{f: store}
76 return f, storage.Mutate(store, func() (err error) {
77 if err = f.f.Truncate(0); err != nil {
78 return &ECreate{f.f.Name(), err}
79 }
80
81 if _, err = f.Alloc(hdr[1:]); err != nil { //TODO internal panicking versions of the exported fns.
82 return
83 }
84
85 if _, err = f.Alloc(nil); err != nil { // (empty) root @1
86 return
87 }
88
89 b := make([]byte, 3856*14)
90 for i := 1; i <= 3856; i++ {
91 Handle(i).Put(b[(i-1)*14:])
92 }
93 if _, err = f.Alloc(b); err != nil {
94 return
95 }
96
97 f.canfree = f.atoms
98 return
99 })
100 }
101
102 // Open returns a new File backed by store or an error if any.
103 // Store already has to be in a valid format.
104 func Open(store storage.Accessor) (f *File, err error) {
105 defer func() {
106 if e := recover(); e != nil {
107 f = nil
108 err = e.(error)
109 }
110 }()
111
112 fi, err := store.Stat()
113 if err != nil {
114 panic(&EOpen{store.Name(), err})
115 }
116
117 fs := fi.Size()
118 if fs&0xf != 0 {
119 panic(&ESize{store.Name(), fi.Size()})
120 }
121
122 f = &File{f: store, atoms: fs >> 4}
123 b := make([]byte, len(hdr))
124 f.read(b, 0)
125 if !bytes.Equal(b, hdr) {
126 panic(&EHeader{store.Name(), b, append([]byte{}, hdr...)})
127 }
128
129 var atoms int64
130 b, atoms = f.readUsed(2)
131 f.canfree = atoms + 2
132 ofs := 0
133 var size, p Handle
134 for ofs < len(b) {
135 size.Get(b[ofs:])
136 ofs += 7
137 p.Get(b[ofs:])
138 ofs += 7
139 if sz, pp := int64(size), int64(p); size == 0 || size > 3856 || (pp != 0 && pp < f.canfree) || pp<<4 > fs-16 {
140 panic(&EFreeList{store.Name(), sz, pp})
141 }
142
143 f.freetab[size] = int64(p)
144 }
145 return
146 }
147
148 // Accessor returns the File's underlying Accessor.
149 func (f *File) Accessor() storage.Accessor {
150 return f.f
151 }
152
153 // Close closes f and returns an error if any.
154 func (f *File) Close() (err error) {
155 return storage.Mutate(f.Accessor(), func() (err error) {
156 if err = f.f.Close(); err != nil {
157 err = &EClose{f.f.Name(), err}
158 }
159 return
160 })
161 }
162
163 // Root returns the handle of the DB root (top level directory, ...).
164 func (f *File) Root() Handle {
165 return 1
166 }
167
168 func (f *File) readUsed(atom int64) (content []byte, atoms int64) {
169 b, redirected := make([]byte, 7), false
170 redir:
171 ofs := atom << 4
172 f.read(b[:1], ofs)
173 switch pre := b[0]; {
174 default:
175 panic(&ECorrupted{f.f.Name(), ofs})
176 case pre == 0x00: // Empty block
177 case pre >= 1 && pre <= 237: // Short
178 content = make([]byte, pre)
179 f.read(content, ofs+1)
180 case pre >= 0xee && pre <= 0xfb: // Short esc
181 content = make([]byte, 15+16*(pre-0xee))
182 f.read(content, ofs+1)
183 content[len(content)-1] += 0xfe
184 case pre == 0xfc: // Long
185 f.read(b[:2], ofs+1)
186 n := int(b[0])<<8 + int(b[1])
187 switch {
188 default:
189 panic(&ECorrupted{f.f.Name(), ofs + 1})
190 case n >= 238 && n <= 61680: // Long non esc
191 content = make([]byte, n)
192 f.read(content, ofs+3)
193 case n >= 61681: // Long esc
194 content = make([]byte, 13+16*(n-0xf0f1))
195 f.read(content, ofs+3)
196 content[len(content)-1] += 0xfe
197 }
198 case pre == 0xfd: // redir
199 if redirected {
200 panic(&ECorrupted{f.f.Name(), ofs})
201 }
202
203 f.read(b[:7], ofs+1)
204 (*Handle)(&atom).Get(b)
205 redirected = true
206 goto redir
207 }
208 return content, rq2Atoms(len(content))
209 }
210
211 func (f *File) writeUsed(b []byte, atom int64) {
212 n := len(b)
213 switch ofs, atoms, endmark := atom<<4, rq2Atoms(n), true; {
214 default:
215 panic("internal error")
216 case n == 0:
217 f.write(empty, ofs)
218 case n <= 237:
219 if (n+1)&0xf == 0 { // content end == atom end
220 if v := b[n-1]; v >= 0xfe { // escape
221 pre := []byte{byte((16*0xee + n - 15) >> 4)}
222 f.write(pre, ofs)
223 f.write(b[:n-1], ofs+1)
224 f.write([]byte{v - 0xfe}, ofs+atoms<<4-1)
225 return
226 }
227 endmark = false
228 }
229 // non esacpe
230 pre := []byte{byte(n)}
231 f.write(pre, ofs)
232 f.write(b, ofs+1)
233 if endmark {
234 f.write(zero, ofs+atoms<<4-1) // last block byte <- used block
235 }
236 case n > 237 && n <= 61680:
237 if (n+3)&0xf == 0 { // content end == atom end
238 if v := b[n-1]; v >= 0xfe { // escape
239 x := (16*0xf0f1 + n - 13) >> 4
240 pre := []byte{0xFC, byte(x >> 8), byte(x)}
241 f.write(pre, ofs)
242 f.write(b[:n-1], ofs+3)
243 f.write([]byte{v - 0xfe}, ofs+atoms<<4-1)
244 return
245 }
246 endmark = false
247 }
248 // non esacpe
249 pre := []byte{0xfc, byte(n >> 8), byte(n)}
250 f.write(pre, ofs)
251 f.write(b, ofs+3)
252 if endmark {
253 f.write(zero, ofs+atoms<<4-1) // last block byte <- used block
254 }
255 }
256 }
257
258 func rq2Atoms(rqbytes int) (rqatoms int64) {
259 if rqbytes > 237 {
260 rqbytes += 2
261 }
262 return int64(rqbytes>>4 + 1)
263 }
264
265 func (f *File) extend(b []byte) (handle int64) {
266 handle = f.atoms
267 f.writeUsed(b, handle)
268 f.atoms += rq2Atoms(len(b))
269 return
270 }
271
272 // Alloc stores b in a newly allocated space and returns its handle and an error if any.
273 func (f *File) Alloc(b []byte) (handle Handle, err error) {
274 err = storage.Mutate(f.Accessor(), func() (err error) {
275 rqAtoms := rq2Atoms(len(b))
276 if rqAtoms > 3856 {
277 return &EBadRequest{f.f.Name(), len(b)}
278 }
279
280 for foundsize, foundp := range f.freetab[rqAtoms:] {
281 if foundp != 0 {
282 // this works only for the current unique sizes list (except the last item!)
283 size := int64(foundsize) + rqAtoms
284 handle = Handle(foundp)
285 if size == 3856 {
286 buf := make([]byte, 7)
287 f.read(buf, int64(handle)<<4+15)
288 (*Handle)(&size).Get(buf)
289 }
290 f.delFree(int64(handle), size)
291 if rqAtoms < size {
292 f.addFree(int64(handle)+rqAtoms, size-rqAtoms)
293 }
294 f.writeUsed(b, int64(handle))
295 return
296 }
297 }
298
299 handle = Handle(f.extend(b))
300 return
301 })
302 return
303 }
304
305 // checkLeft returns the atom size of a free bleck left adjacent to block @atom.
306 // If that block is not free the returned size is 0.
307 func (f *File) checkLeft(atom int64) (size int64) {
308 if atom <= f.canfree {
309 return
310 }
311
312 b := make([]byte, 7)
313 fp := atom << 4
314 f.read(b[:1], fp-1)
315 switch last := b[0]; {
316 case last <= 0xfd:
317 // used block
318 case last == 0xfe:
319 f.read(b, fp-8)
320 (*Handle)(&size).Get(b)
321 case last == 0xff:
322 size = 1
323 }
324 return
325 }
326
327 // getInfo returns the block @atom type and size.
328 func (f *File) getInfo(atom int64) (pref byte, size int64) {
329 b := make([]byte, 7)
330 fp := atom << 4
331 f.read(b[:1], fp)
332 switch pref = b[0]; {
333 case pref == 0: // Empty used
334 size = 1
335 case pref >= 1 && pref <= 237: // Short
336 size = rq2Atoms(int(pref))
337 case pref >= 0xee && pref <= 0xfb: // Short esc
338 size = rq2Atoms(15 + 16*int(pref-0xee))
339 case pref == 0xfc: // Long
340 f.read(b[:2], fp+1)
341 n := int(b[0])<<8 + int(b[1])
342 switch {
343 default:
344 panic(&ECorrupted{f.f.Name(), fp + 1})
345 case n >= 238 && n <= 61680: // Long non esc
346 size = rq2Atoms(n)
347 case n >= 61681: // Long esc
348 size = rq2Atoms(13 + 16*(n-0xf0f1))
349 }
350 case pref == 0xfd: // reloc
351 size = 1
352 case pref == 0xfe:
353 f.read(b, fp+15)
354 (*Handle)(&size).Get(b)
355 case pref == 0xff:
356 size = 1
357 }
358 return
359 }
360
361 // getSize returns the atom size of the block @atom and wheter it is free.
362 func (f *File) getSize(atom int64) (size int64, isFree bool) {
363 var typ byte
364 typ, size = f.getInfo(atom)
365 isFree = typ >= 0xfe
366 return
367 }
368
369 // checkRight returns the atom size of a free bleck right adjacent to block @atom,atoms.
370 // If that block is not free the returned size is 0.
371 func (f *File) checkRight(atom, atoms int64) (size int64) {
372 if atom+atoms >= f.atoms {
373 return
374 }
375
376 if sz, free := f.getSize(atom + atoms); free {
377 size = sz
378 }
379 return
380 }
381
382 // delFree removes the atoms@atom free block from the free block list
383 func (f *File) delFree(atom, atoms int64) {
384 b := make([]byte, 15)
385 size := int(atoms)
386 if n := len(f.freetab); atoms >= int64(n) {
387 size = n - 1
388 }
389 fp := atom << 4
390 f.read(b[1:], fp+1)
391 var prev, next Handle
392 prev.Get(b[1:])
393 next.Get(b[8:])
394
395 switch {
396 case prev == 0 && next != 0:
397 next.Put(b)
398 f.write(b[:7], int64(32+3+7+(size-1)*14))
399 f.write(zero7, int64(next)<<4+1)
400 f.freetab[size] = int64(next)
401 case prev != 0 && next == 0:
402 f.write(zero7, int64(prev)<<4+8)
403 case prev != 0 && next != 0:
404 prev.Put(b)
405 f.write(b[:7], int64(next)<<4+1)
406 next.Put(b)
407 f.write(b[:7], int64(prev)<<4+8)
408 default: // prev == 0 && next == 0:
409 f.write(zero7, int64(32+3+7+(size-1)*14))
410 f.freetab[size] = 0
411 }
412 }
413
414 // addFree adds atoms@atom to the free block lists and marks it free.
415 func (f *File) addFree(atom, atoms int64) {
416 b := make([]byte, 7)
417 size := int(atoms)
418 if n := len(f.freetab); atoms >= int64(n) {
419 size = n - 1
420 }
421 head := f.freetab[size]
422 if head == 0 { // empty list
423 f.makeFree(0, atom, atoms, 0)
424 Handle(atom).Put(b)
425 f.write(b, int64(32+3+7+(size-1)*14))
426 f.freetab[size] = atom
427 return
428 }
429
430 Handle(atom).Put(b)
431 f.write(b, head<<4+1) // head.prev = atom
432 f.makeFree(0, atom, atoms, head) // atom.next = head
433 f.write(b, int64(32+3+7+(size-1)*14))
434 f.freetab[size] = atom
435 }
436
437 // makeFree sets up the content of a free block atoms@atom, fills the prev and next links.
438 func (f *File) makeFree(prev, atom, atoms, next int64) {
439 b := make([]byte, 23)
440 fp := atom << 4
441 if atoms == 1 {
442 b[0] = 0xff
443 Handle(prev).Put(b[1:])
444 Handle(next).Put(b[8:])
445 b[15] = 0xff
446 f.write(b[:16], fp)
447 return
448 }
449
450 b[0] = 0xfe
451 Handle(prev).Put(b[1:])
452 Handle(next).Put(b[8:])
453 Handle(atoms).Put(b[15:])
454 f.write(b[:22], fp)
455 b[22] = 0xfe
456 f.write(b[15:], fp+atoms<<4-8)
457 }
458
459 // Read reads and return the data associated with handle and an error if any.
460 // Passing an invalid handle to Read may return invalid data without error.
461 // It's like getting garbage via passing an invalid pointer to C.memcopy().
462 func (f *File) Read(handle Handle) (b []byte, err error) {
463 defer func() {
464 if e := recover(); e != nil {
465 b = nil
466 err = e.(error)
467 }
468 }()
469
470 switch handle {
471 case 0:
472 panic(ENullHandle(f.f.Name()))
473 case 2:
474 panic(&EHandle{f.f.Name(), handle})
475 default:
476 b, _ = f.readUsed(int64(handle))
477 }
478 return
479 }
480
481 // Free frees space associated with handle and returns an error if any. Passing an invalid
482 // handle to Free or reusing handle afterwards will probably corrupt the database or provide
483 // invalid data on Read. It's like corrupting memory via passing an invalid pointer to C.free()
484 // or reusing that pointer.
485 func (f *File) Free(handle Handle) (err error) {
486 return storage.Mutate(f.Accessor(), func() (err error) {
487 atom := int64(handle)
488 atoms, isFree := f.getSize(atom)
489 if isFree || atom < f.canfree {
490 return &EHandle{f.f.Name(), handle}
491 }
492
493 leftFree, rightFree := f.checkLeft(atom), f.checkRight(atom, atoms)
494 switch {
495 case leftFree != 0 && rightFree != 0:
496 f.delFree(atom-leftFree, leftFree)
497 f.delFree(atom+atoms, rightFree)
498 f.addFree(atom-leftFree, leftFree+atoms+rightFree)
499 case leftFree != 0 && rightFree == 0:
500 f.delFree(atom-leftFree, leftFree)
501 if atom+atoms == f.atoms { // the left free neighbour and this block together are an empy tail
502 f.atoms = atom - leftFree
503 f.f.Truncate(f.atoms << 4)
504 return
505 }
506
507 f.addFree(atom-leftFree, leftFree+atoms)
508 case leftFree == 0 && rightFree != 0:
509 f.delFree(atom+atoms, rightFree)
510 f.addFree(atom, atoms+rightFree)
511 default: // leftFree == 0 && rightFree == 0
512 if atom+atoms < f.atoms { // isolated inner block
513 f.addFree(atom, atoms)
514 return
515 }
516
517 f.f.Truncate(atom << 4) // isolated tail block, shrink file
518 f.atoms = atom
519 }
520 return
521 })
522 }
523
524 // Realloc reallocates space associted with handle to acomodate b, returns the newhandle
525 // newly associated with b and an error if any. If keepHandle == true then Realloc guarantees
526 // newhandle == handle even if the new data are larger then the previous content associated
527 // with handle. If !keepHandle && newhandle != handle then reusing handle will probably corrupt
528 // the database.
529 // The above effects are like corrupting memory/data via passing an invalid pointer to C.realloc().
530 func (f *File) Realloc(handle Handle, b []byte, keepHandle bool) (newhandle Handle, err error) {
531 err = storage.Mutate(f.Accessor(), func() (err error) {
532 switch handle {
533 case 0, 2:
534 return &EHandle{f.f.Name(), handle}
535 case 1:
536 keepHandle = true
537 }
538 newhandle = handle
539 atom, newatoms := int64(handle), rq2Atoms(len(b))
540 if newatoms > 3856 {
541 return &EBadRequest{f.f.Name(), len(b)}
542 }
543
544 typ, oldatoms := f.getInfo(atom)
545 switch {
546 default:
547 return &ECorrupted{f.f.Name(), atom << 4}
548 case typ <= 0xfc: // non relocated used block
549 switch {
550 case newatoms == oldatoms: // in place replace
551 f.writeUsed(b, atom)
552 case newatoms < oldatoms: // in place shrink
553 rightFree := f.checkRight(atom, oldatoms)
554 if rightFree > 0 { // right join
555 f.delFree(atom+oldatoms, rightFree)
556 }
557 f.addFree(atom+newatoms, oldatoms+rightFree-newatoms)
558 f.writeUsed(b, atom)
559 case newatoms > oldatoms:
560 if rightFree := f.checkRight(atom, oldatoms); rightFree > 0 && newatoms <= oldatoms+rightFree {
561 f.delFree(atom+oldatoms, rightFree)
562 if newatoms < oldatoms+rightFree {
563 f.addFree(atom+newatoms, oldatoms+rightFree-newatoms)
564 }
565 f.writeUsed(b, atom)
566 return
567 }
568
569 if !keepHandle {
570 f.Free(Handle(atom))
571 newhandle, err = f.Alloc(b)
572 return
573 }
574
575 // reloc
576 newatom, e := f.Alloc(b)
577 if e != nil {
578 return e
579 }
580
581 buf := make([]byte, 16)
582 buf[0] = 0xfd
583 Handle(newatom).Put(buf[1:])
584 f.Realloc(Handle(atom), buf[1:], true)
585 f.write(buf[:1], atom<<4)
586 }
587 case typ == 0xfd: // reloc
588 var target Handle
589 buf := make([]byte, 7)
590 f.read(buf, atom<<4+1)
591 target.Get(buf)
592 switch {
593 case newatoms == 1:
594 f.writeUsed(b, atom)
595 f.Free(target)
596 default:
597 if rightFree := f.checkRight(atom, 1); rightFree > 0 && newatoms <= 1+rightFree {
598 f.delFree(atom+1, rightFree)
599 if newatoms < 1+rightFree {
600 f.addFree(atom+newatoms, 1+rightFree-newatoms)
601 }
602 f.writeUsed(b, atom)
603 f.Free(target)
604 return
605 }
606
607 newtarget, e := f.Realloc(Handle(target), b, false)
608 if e != nil {
609 return e
610 }
611
612 if newtarget != target {
613 Handle(newtarget).Put(buf)
614 f.write(buf, atom<<4+1)
615 }
616 }
617 }
618 return
619 })
620 return
621 }
622
623 // Lock locks f for writing. If the lock is already locked for reading or writing,
624 // Lock blocks until the lock is available. To ensure that the lock eventually becomes available,
625 // a blocked Lock call excludes new readers from acquiring the lock.
626 func (f *File) Lock() {
627 f.rwm.Lock()
628 }
629
630 // RLock locks f for reading. If the lock is already locked for writing or there is a writer
631 // already waiting to release the lock, RLock blocks until the writer has released the lock.
632 func (f *File) RLock() {
633 f.rwm.RLock()
634 }
635
636 // Unlock unlocks f for writing. It is a run-time error if f is not locked for writing on entry to Unlock.
637 //
638 // As with Mutexes, a locked RWMutex is not associated with a particular goroutine.
639 // One goroutine may RLock (Lock) f and then arrange for another goroutine to RUnlock (Unlock) it.
640 func (f *File) Unlock() {
641 f.rwm.Unlock()
642 }
643
644 // RUnlock undoes a single RLock call; it does not affect other simultaneous readers.
645 // It is a run-time error if f is not locked for reading on entry to RUnlock.
646 func (f *File) RUnlock() {
647 f.rwm.RUnlock()
648 }
649
650 // LockedAlloc wraps Alloc in a Lock/Unlock pair.
651 func (f *File) LockedAlloc(b []byte) (handle Handle, err error) {
652 f.Lock()
653 defer f.Unlock()
654 return f.Alloc(b)
655 }
656
657 // LockedFree wraps Free in a Lock/Unlock pair.
658 func (f *File) LockedFree(handle Handle) (err error) {
659 f.Lock()
660 defer f.Unlock()
661 return f.Free(handle)
662 }
663
664 // LockedRead wraps Read in a RLock/RUnlock pair.
665 func (f *File) LockedRead(handle Handle) (b []byte, err error) {
666 f.RLock()
667 defer f.RUnlock()
668 return f.Read(handle)
669 }
670
671 // LockedRealloc wraps Realloc in a Lock/Unlock pair.
672 func (f *File) LockedRealloc(handle Handle, b []byte, keepHandle bool) (newhandle Handle, err error) {
673 f.Lock()
674 defer f.Unlock()
675 return f.Realloc(handle, b, keepHandle)
676 }