aboutsummaryrefslogtreecommitdiffstats
path: root/swarm/storage/memstore.go
diff options
context:
space:
mode:
Diffstat (limited to 'swarm/storage/memstore.go')
-rw-r--r--swarm/storage/memstore.go316
1 files changed, 316 insertions, 0 deletions
diff --git a/swarm/storage/memstore.go b/swarm/storage/memstore.go
new file mode 100644
index 000000000..f133bd7d3
--- /dev/null
+++ b/swarm/storage/memstore.go
@@ -0,0 +1,316 @@
+// Copyright 2016 The go-ethereum Authors
+// This file is part of the go-ethereum library.
+//
+// The go-ethereum library is free software: you can redistribute it and/or modify
+// it under the terms of the GNU Lesser General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+//
+// The go-ethereum library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU Lesser General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
+
+// memory storage layer for the package blockhash
+
+package storage
+
+import (
+ "sync"
+)
+
+const (
+ memTreeLW = 2 // log2(subtree count) of the subtrees
+ memTreeFLW = 14 // log2(subtree count) of the root layer
+ dbForceUpdateAccessCnt = 1000
+ defaultCacheCapacity = 5000
+)
+
+type MemStore struct {
+ memtree *memTree
+ entryCnt, capacity uint // stored entries
+ accessCnt uint64 // access counter; oldest is thrown away when full
+ dbAccessCnt uint64
+ dbStore *DbStore
+ lock sync.Mutex
+}
+
+/*
+a hash prefix subtree containing subtrees or one storage entry (but never both)
+
+- access[0] stores the smallest (oldest) access count value in this subtree
+- if it contains more subtrees and its subtree count is at least 4, access[1:2]
+ stores the smallest access count in the first and second halves of subtrees
+ (so that access[0] = min(access[1], access[2])
+- likewise, if subtree count is at least 8,
+ access[1] = min(access[3], access[4])
+ access[2] = min(access[5], access[6])
+ (access[] is a binary tree inside the multi-bit leveled hash tree)
+*/
+
+func NewMemStore(d *DbStore, capacity uint) (m *MemStore) {
+ m = &MemStore{}
+ m.memtree = newMemTree(memTreeFLW, nil, 0)
+ m.dbStore = d
+ m.setCapacity(capacity)
+ return
+}
+
+type memTree struct {
+ subtree []*memTree
+ parent *memTree
+ parentIdx uint
+
+ bits uint // log2(subtree count)
+ width uint // subtree count
+
+ entry *Chunk // if subtrees are present, entry should be nil
+ lastDBaccess uint64
+ access []uint64
+}
+
+func newMemTree(b uint, parent *memTree, pidx uint) (node *memTree) {
+ node = new(memTree)
+ node.bits = b
+ node.width = 1 << uint(b)
+ node.subtree = make([]*memTree, node.width)
+ node.access = make([]uint64, node.width-1)
+ node.parent = parent
+ node.parentIdx = pidx
+ if parent != nil {
+ parent.subtree[pidx] = node
+ }
+
+ return node
+}
+
+func (node *memTree) updateAccess(a uint64) {
+ aidx := uint(0)
+ var aa uint64
+ oa := node.access[0]
+ for node.access[aidx] == oa {
+ node.access[aidx] = a
+ if aidx > 0 {
+ aa = node.access[((aidx-1)^1)+1]
+ aidx = (aidx - 1) >> 1
+ } else {
+ pidx := node.parentIdx
+ node = node.parent
+ if node == nil {
+ return
+ }
+ nn := node.subtree[pidx^1]
+ if nn != nil {
+ aa = nn.access[0]
+ } else {
+ aa = 0
+ }
+ aidx = (node.width + pidx - 2) >> 1
+ }
+
+ if (aa != 0) && (aa < a) {
+ a = aa
+ }
+ }
+}
+
+func (s *MemStore) setCapacity(c uint) {
+ s.lock.Lock()
+ defer s.lock.Unlock()
+
+ for c < s.entryCnt {
+ s.removeOldest()
+ }
+ s.capacity = c
+}
+
+func (s *MemStore) getEntryCnt() uint {
+ return s.entryCnt
+}
+
+// entry (not its copy) is going to be in MemStore
+func (s *MemStore) Put(entry *Chunk) {
+ if s.capacity == 0 {
+ return
+ }
+
+ s.lock.Lock()
+ defer s.lock.Unlock()
+
+ if s.entryCnt >= s.capacity {
+ s.removeOldest()
+ }
+
+ s.accessCnt++
+
+ node := s.memtree
+ bitpos := uint(0)
+ for node.entry == nil {
+ l := entry.Key.bits(bitpos, node.bits)
+ st := node.subtree[l]
+ if st == nil {
+ st = newMemTree(memTreeLW, node, l)
+ bitpos += node.bits
+ node = st
+ break
+ }
+ bitpos += node.bits
+ node = st
+ }
+
+ if node.entry != nil {
+
+ if node.entry.Key.isEqual(entry.Key) {
+ node.updateAccess(s.accessCnt)
+ if entry.SData == nil {
+ entry.Size = node.entry.Size
+ entry.SData = node.entry.SData
+ }
+ if entry.Req == nil {
+ entry.Req = node.entry.Req
+ }
+ entry.C = node.entry.C
+ node.entry = entry
+ return
+ }
+
+ for node.entry != nil {
+
+ l := node.entry.Key.bits(bitpos, node.bits)
+ st := node.subtree[l]
+ if st == nil {
+ st = newMemTree(memTreeLW, node, l)
+ }
+ st.entry = node.entry
+ node.entry = nil
+ st.updateAccess(node.access[0])
+
+ l = entry.Key.bits(bitpos, node.bits)
+ st = node.subtree[l]
+ if st == nil {
+ st = newMemTree(memTreeLW, node, l)
+ }
+ bitpos += node.bits
+ node = st
+
+ }
+ }
+
+ node.entry = entry
+ node.lastDBaccess = s.dbAccessCnt
+ node.updateAccess(s.accessCnt)
+ s.entryCnt++
+
+ return
+}
+
+func (s *MemStore) Get(hash Key) (chunk *Chunk, err error) {
+ s.lock.Lock()
+ defer s.lock.Unlock()
+
+ node := s.memtree
+ bitpos := uint(0)
+ for node.entry == nil {
+ l := hash.bits(bitpos, node.bits)
+ st := node.subtree[l]
+ if st == nil {
+ return nil, notFound
+ }
+ bitpos += node.bits
+ node = st
+ }
+
+ if node.entry.Key.isEqual(hash) {
+ s.accessCnt++
+ node.updateAccess(s.accessCnt)
+ chunk = node.entry
+ if s.dbAccessCnt-node.lastDBaccess > dbForceUpdateAccessCnt {
+ s.dbAccessCnt++
+ node.lastDBaccess = s.dbAccessCnt
+ if s.dbStore != nil {
+ s.dbStore.updateAccessCnt(hash)
+ }
+ }
+ } else {
+ err = notFound
+ }
+
+ return
+}
+
+func (s *MemStore) removeOldest() {
+ node := s.memtree
+
+ for node.entry == nil {
+
+ aidx := uint(0)
+ av := node.access[aidx]
+
+ for aidx < node.width/2-1 {
+ if av == node.access[aidx*2+1] {
+ node.access[aidx] = node.access[aidx*2+2]
+ aidx = aidx*2 + 1
+ } else if av == node.access[aidx*2+2] {
+ node.access[aidx] = node.access[aidx*2+1]
+ aidx = aidx*2 + 2
+ } else {
+ panic(nil)
+ }
+ }
+ pidx := aidx*2 + 2 - node.width
+ if (node.subtree[pidx] != nil) && (av == node.subtree[pidx].access[0]) {
+ if node.subtree[pidx+1] != nil {
+ node.access[aidx] = node.subtree[pidx+1].access[0]
+ } else {
+ node.access[aidx] = 0
+ }
+ } else if (node.subtree[pidx+1] != nil) && (av == node.subtree[pidx+1].access[0]) {
+ if node.subtree[pidx] != nil {
+ node.access[aidx] = node.subtree[pidx].access[0]
+ } else {
+ node.access[aidx] = 0
+ }
+ pidx++
+ } else {
+ panic(nil)
+ }
+
+ //fmt.Println(pidx)
+ node = node.subtree[pidx]
+
+ }
+
+ if node.entry.dbStored != nil {
+ <-node.entry.dbStored
+ }
+
+ if node.entry.SData != nil {
+ node.entry = nil
+ s.entryCnt--
+ }
+
+ node.access[0] = 0
+
+ //---
+
+ aidx := uint(0)
+ for {
+ aa := node.access[aidx]
+ if aidx > 0 {
+ aidx = (aidx - 1) >> 1
+ } else {
+ pidx := node.parentIdx
+ node = node.parent
+ if node == nil {
+ return
+ }
+ aidx = (node.width + pidx - 2) >> 1
+ }
+ if (aa != 0) && ((aa < node.access[aidx]) || (node.access[aidx] == 0)) {
+ node.access[aidx] = aa
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-27 12:20:40 +0800