1package kademlia
  2
  3import (
  4	"errors"
  5	"math/bits"
  6	"net/rpc"
  7	"strconv"
  8
  9	log "github.com/sirupsen/logrus"
 10)
 11
 12const (
 13	alpha       = 3  // 'alpha', max parallalel calls
 14	B           = 20 // 'B', 160 bits, ID length
 15	KBucketSize = 20 // 'K', bucket size
 16)
 17
 18type ListedNode struct {
 19	ID   ID
 20	Addr string
 21	Port string
 22}
 23
 24type Kademlia struct {
 25	// N is this node data
 26	N        ListedNode
 27	KBuckets [B][]ListedNode
 28}
 29
 30func NewKademliaTable(id ID, addr, port string) *Kademlia {
 31	return &Kademlia{
 32		N: ListedNode{
 33			ID:   id,
 34			Addr: addr,
 35			Port: port,
 36		},
 37	}
 38}
 39
 40func (kad Kademlia) String() string {
 41	r := "Node ID: " + kad.N.ID.String() + ", KBuckets:\n"
 42	for i, kb := range kad.KBuckets {
 43		if len(kb) > 0 {
 44			r += "	KBucket " + strconv.Itoa(i) + "\n"
 45			for _, e := range kb {
 46				r += "		" + e.ID.String() + "\n"
 47			}
 48		}
 49	}
 50	return r
 51}
 52
 53func (kad Kademlia) FindClosestKBucket(id ID) (int, error) {
 54	kb := kad.KBucket(id)
 55	if len(kad.KBuckets[kb]) != 0 {
 56		return kb, nil
 57	}
 58	for i := 0; kb-i > 0 || kb+i < 8; i++ {
 59		if len(kad.KBuckets[kb+i]) != 0 {
 60			return kb + i, nil
 61		}
 62		if len(kad.KBuckets[kb-i]) != 0 {
 63			return kb - i, nil
 64		}
 65	}
 66	return 0, errors.New("not found")
 67}
 68
 69func (kad Kademlia) KBucket(o ID) int {
 70	d := kad.N.ID.Distance(o)
 71	return kBucketByDistance(d[:])
 72
 73}
 74
 75func kBucketByDistance(b []byte) int {
 76	z := countZeroes(b)
 77	if z == 0 {
 78		return 0
 79	}
 80	for i := 0; i < 8; i++ {
 81		if z>>uint8(i) == 1 { // check until 1 instead of 0 to avoid one operation
 82			return i
 83		}
 84	}
 85	return 7
 86}
 87
 88func countZeroes(b []byte) int {
 89	for i := 0; i < B; i++ {
 90		for a := b[i] ^ 0; a != 0; a &= a - 1 {
 91			return (B * 8) - (i * 8) - (8 - bits.TrailingZeros8(bits.Reverse8(uint8(a))))
 92		}
 93	}
 94	return (B*8 - 1) - (B*8 - 1)
 95}
 96
 97func (kad *Kademlia) Update(o ListedNode) {
 98	k := kad.KBucket(o.ID)
 99	kb := kad.KBuckets[k]
100	if len(kb) >= KBucketSize {
101		// if n.KBuckets[k] is alrady full, perform ping of the first element
102		log.Debug("node.KBuckets[k] already full, performing ping to node.KBuckets[0]")
103		kad.PingOldNode(k, o)
104		return
105	}
106	// check that is not already in the list
107	exist, pos := existsInListedNodes(kad.KBuckets[k], o)
108	if exist {
109		// update position of o to the bottom
110		kad.KBuckets[k] = moveToBottom(kad.KBuckets[k], pos)
111		log.Debug("ListedNode (" + o.ID.String() + ") already exists, moved to bottom")
112		return
113	}
114	// not exists, add it to the kBucket
115	kad.KBuckets[k] = append(kad.KBuckets[k], o)
116	log.Debug("ListedNode (" + o.ID.String() + ") not exists, added to the bottom")
117	return
118}
119
120func (kad *Kademlia) PingOldNode(k int, o ListedNode) {
121	// TODO when rpc layer is done
122	// ping the n.KBuckets[k][0] (using goroutine)
123	// if no response (timeout), delete it and add 'o'
124	// n.KBuckets[k][0] = o
125}
126
127func (kad *Kademlia) CallPing(o ListedNode) error {
128	client, err := rpc.DialHTTP("tcp", o.Addr+":"+o.Port)
129	if err != nil {
130		return err
131	}
132	ln := ListedNode{
133		ID:   kad.N.ID,
134		Addr: kad.N.Addr,
135		Port: kad.N.Port,
136	}
137	var reply ListedNode
138	err = client.Call("Node.Ping", ln, &reply)
139	if err != nil {
140		return err
141	}
142	// TODO use reply as PONG
143	return nil
144}
145
146func (kad *Kademlia) CallPong(o ListedNode) error {
147	client, err := rpc.DialHTTP("tcp", o.Addr+":"+o.Port)
148	if err != nil {
149		return err
150	}
151	ln := ListedNode{
152		ID:   kad.N.ID,
153		Addr: kad.N.Addr,
154		Port: kad.N.Port,
155	}
156	var reply bool
157	err = client.Call("Node.Pong", ln, &reply)
158	if err != nil {
159		return err
160	}
161
162	return nil
163}
164
165func existsInListedNodes(lns []ListedNode, ln ListedNode) (bool, int) {
166	for i, v := range lns {
167		if v.ID.Equal(ln.ID) {
168			return true, i
169		}
170	}
171	return false, 0
172}
173
174func moveToBottom(kb []ListedNode, k int) []ListedNode {
175	e := kb[k]
176	kb = append(kb[:k], kb[k+1:]...)
177	kb = append(kb[:], e)
178	return kb
179}