swarm: plan bee for content storage and distribution on web3

This change imports the Swarm protocol codebase. Compared to the 'swarm'
branch, a few mostly cosmetic changes had to be made:

* The various redundant log message prefixes are gone.
* All files now have LGPLv3 license headers.
* Minor code changes were needed to please go vet and make the tests
  pass on Windows.
* Further changes were required to adapt to the go-ethereum develop
  branch and its new Go APIs.

Some code has not (yet) been brought over:

* swarm/cmd/bzzhash: will reappear as cmd/bzzhash later
* swarm/cmd/bzzup.sh: will be reimplemented in cmd/bzzup
* swarm/cmd/makegenesis: will reappear somehow
* swarm/examples/album: will move to a separate repository
* swarm/examples/filemanager: ditto
* swarm/examples/files: will not be merged
* swarm/test/*: will not be merged
* swarm/services/swear: will reappear as contracts/swear when needed

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
+		}
+	}
+}