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