vendor/github.com/btcsuite/btcd/addrmgr/addrmanager.go

   1 // Copyright (c) 2013-2016 The btcsuite developers
   2 // Use of this source code is governed by an ISC
   3 // license that can be found in the LICENSE file.
   4
   5 package addrmgr
   6
   7 import (
   8         "container/list"
   9         crand "crypto/rand" // for seeding
  10         "encoding/base32"
  11         "encoding/binary"
  12         "encoding/json"
  13         "fmt"
  14         "io"
  15         "math/rand"
  16         "net"
  17         "os"
  18         "path/filepath"
  19         "strconv"
  20         "strings"
  21         "sync"
  22         "sync/atomic"
  23         "time"
  24
  25         "github.com/btcsuite/btcd/chaincfg/chainhash"
  26         "github.com/btcsuite/btcd/wire"
  27 )
  28
  29 // AddrManager provides a concurrency safe address manager for caching potential
  30 // peers on the bitcoin network.
  31 type AddrManager struct {
  32         mtx            sync.Mutex
  33         peersFile      string
  34         lookupFunc     func(string) ([]net.IP, error)
  35         rand           *rand.Rand
  36         key            [32]byte
  37         addrIndex      map[string]*KnownAddress // address key to ka for all addrs.
  38         addrNew        [newBucketCount]map[string]*KnownAddress
  39         addrTried      [triedBucketCount]*list.List
  40         started        int32
  41         shutdown       int32
  42         wg             sync.WaitGroup
  43         quit           chan struct{}
  44         nTried         int
  45         nNew           int
  46         lamtx          sync.Mutex
  47         localAddresses map[string]*localAddress
  48 }
  49
  50 type serializedKnownAddress struct {
  51         Addr        string
  52         Src         string
  53         Attempts    int
  54         TimeStamp   int64
  55         LastAttempt int64
  56         LastSuccess int64
  57         // no refcount or tried, that is available from context.
  58 }
  59
  60 type serializedAddrManager struct {
  61         Version      int
  62         Key          [32]byte
  63         Addresses    []*serializedKnownAddress
  64         NewBuckets   [newBucketCount][]string // string is NetAddressKey
  65         TriedBuckets [triedBucketCount][]string
  66 }
  67
  68 type localAddress struct {
  69         na    *wire.NetAddress
  70         score AddressPriority
  71 }
  72
  73 // AddressPriority type is used to describe the hierarchy of local address
  74 // discovery methods.
  75 type AddressPriority int
  76
  77 const (
  78         // InterfacePrio signifies the address is on a local interface
  79         InterfacePrio AddressPriority = iota
  80
  81         // BoundPrio signifies the address has been explicitly bounded to.
  82         BoundPrio
  83
  84         // UpnpPrio signifies the address was obtained from UPnP.
  85         UpnpPrio
  86
  87         // HTTPPrio signifies the address was obtained from an external HTTP service.
  88         HTTPPrio
  89
  90         // ManualPrio signifies the address was provided by --externalip.
  91         ManualPrio
  92 )
  93
  94 const (
  95         // needAddressThreshold is the number of addresses under which the
  96         // address manager will claim to need more addresses.
  97         needAddressThreshold = 1000
  98
  99         // dumpAddressInterval is the interval used to dump the address
 100         // cache to disk for future use.
 101         dumpAddressInterval = time.Minute * 10
 102
 103         // triedBucketSize is the maximum number of addresses in each
 104         // tried address bucket.
 105         triedBucketSize = 256
 106
 107         // triedBucketCount is the number of buckets we split tried
 108         // addresses over.
 109         triedBucketCount = 64
 110
 111         // newBucketSize is the maximum number of addresses in each new address
 112         // bucket.
 113         newBucketSize = 64
 114
 115         // newBucketCount is the number of buckets that we spread new addresses
 116         // over.
 117         newBucketCount = 1024
 118
 119         // triedBucketsPerGroup is the number of tried buckets over which an
 120         // address group will be spread.
 121         triedBucketsPerGroup = 8
 122
 123         // newBucketsPerGroup is the number of new buckets over which an
 124         // source address group will be spread.
 125         newBucketsPerGroup = 64
 126
 127         // newBucketsPerAddress is the number of buckets a frequently seen new
 128         // address may end up in.
 129         newBucketsPerAddress = 8
 130
 131         // numMissingDays is the number of days before which we assume an
 132         // address has vanished if we have not seen it announced  in that long.
 133         numMissingDays = 30
 134
 135         // numRetries is the number of tried without a single success before
 136         // we assume an address is bad.
 137         numRetries = 3
 138
 139         // maxFailures is the maximum number of failures we will accept without
 140         // a success before considering an address bad.
 141         maxFailures = 10
 142
 143         // minBadDays is the number of days since the last success before we
 144         // will consider evicting an address.
 145         minBadDays = 7
 146
 147         // getAddrMax is the most addresses that we will send in response
 148         // to a getAddr (in practise the most addresses we will return from a
 149         // call to AddressCache()).
 150         getAddrMax = 2500
 151
 152         // getAddrPercent is the percentage of total addresses known that we
 153         // will share with a call to AddressCache.
 154         getAddrPercent = 23
 155
 156         // serialisationVersion is the current version of the on-disk format.
 157         serialisationVersion = 1
 158 )
 159
 160 // updateAddress is a helper function to either update an address already known
 161 // to the address manager, or to add the address if not already known.
 162 func (a *AddrManager) updateAddress(netAddr, srcAddr *wire.NetAddress) {
 163         // Filter out non-routable addresses. Note that non-routable
 164         // also includes invalid and local addresses.
 165         if !IsRoutable(netAddr) {
 166                 return
 167         }
 168
 169         addr := NetAddressKey(netAddr)
 170         ka := a.find(netAddr)
 171         if ka != nil {
 172                 // TODO: only update addresses periodically.
 173                 // Update the last seen time and services.
 174                 // note that to prevent causing excess garbage on getaddr
 175                 // messages the netaddresses in addrmaanger are *immutable*,
 176                 // if we need to change them then we replace the pointer with a
 177                 // new copy so that we don't have to copy every na for getaddr.
 178                 if netAddr.Timestamp.After(ka.na.Timestamp) ||
 179                         (ka.na.Services&netAddr.Services) !=
 180                                 netAddr.Services {
 181
 182                         naCopy := *ka.na
 183                         naCopy.Timestamp = netAddr.Timestamp
 184                         naCopy.AddService(netAddr.Services)
 185                         ka.na = &naCopy
 186                 }
 187
 188                 // If already in tried, we have nothing to do here.
 189                 if ka.tried {
 190                         return
 191                 }
 192
 193                 // Already at our max?
 194                 if ka.refs == newBucketsPerAddress {
 195                         return
 196                 }
 197
 198                 // The more entries we have, the less likely we are to add more.
 199                 // likelihood is 2N.
 200                 factor := int32(2 * ka.refs)
 201                 if a.rand.Int31n(factor) != 0 {
 202                         return
 203                 }
 204         } else {
 205                 // Make a copy of the net address to avoid races since it is
 206                 // updated elsewhere in the addrmanager code and would otherwise
 207                 // change the actual netaddress on the peer.
 208                 netAddrCopy := *netAddr
 209                 ka = &KnownAddress{na: &netAddrCopy, srcAddr: srcAddr}
 210                 a.addrIndex[addr] = ka
 211                 a.nNew++
 212                 // XXX time penalty?
 213         }
 214
 215         bucket := a.getNewBucket(netAddr, srcAddr)
 216
 217         // Already exists?
 218         if _, ok := a.addrNew[bucket][addr]; ok {
 219                 return
 220         }
 221
 222         // Enforce max addresses.
 223         if len(a.addrNew[bucket]) > newBucketSize {
 224                 log.Tracef("new bucket is full, expiring old")
 225                 a.expireNew(bucket)
 226         }
 227
 228         // Add to new bucket.
 229         ka.refs++
 230         a.addrNew[bucket][addr] = ka
 231
 232         log.Tracef("Added new address %s for a total of %d addresses", addr,
 233                 a.nTried+a.nNew)
 234 }
 235
 236 // expireNew makes space in the new buckets by expiring the really bad entries.
 237 // If no bad entries are available we look at a few and remove the oldest.
 238 func (a *AddrManager) expireNew(bucket int) {
 239         // First see if there are any entries that are so bad we can just throw
 240         // them away. otherwise we throw away the oldest entry in the cache.
 241         // Bitcoind here chooses four random and just throws the oldest of
 242         // those away, but we keep track of oldest in the initial traversal and
 243         // use that information instead.
 244         var oldest *KnownAddress
 245         for k, v := range a.addrNew[bucket] {
 246                 if v.isBad() {
 247                         log.Tracef("expiring bad address %v", k)
 248                         delete(a.addrNew[bucket], k)
 249                         v.refs--
 250                         if v.refs == 0 {
 251                                 a.nNew--
 252                                 delete(a.addrIndex, k)
 253                         }
 254                         continue
 255                 }
 256                 if oldest == nil {
 257                         oldest = v
 258                 } else if !v.na.Timestamp.After(oldest.na.Timestamp) {
 259                         oldest = v
 260                 }
 261         }
 262
 263         if oldest != nil {
 264                 key := NetAddressKey(oldest.na)
 265                 log.Tracef("expiring oldest address %v", key)
 266
 267                 delete(a.addrNew[bucket], key)
 268                 oldest.refs--
 269                 if oldest.refs == 0 {
 270                         a.nNew--
 271                         delete(a.addrIndex, key)
 272                 }
 273         }
 274 }
 275
 276 // pickTried selects an address from the tried bucket to be evicted.
 277 // We just choose the eldest. Bitcoind selects 4 random entries and throws away
 278 // the older of them.
 279 func (a *AddrManager) pickTried(bucket int) *list.Element {
 280         var oldest *KnownAddress
 281         var oldestElem *list.Element
 282         for e := a.addrTried[bucket].Front(); e != nil; e = e.Next() {
 283                 ka := e.Value.(*KnownAddress)
 284                 if oldest == nil || oldest.na.Timestamp.After(ka.na.Timestamp) {
 285                         oldestElem = e
 286                         oldest = ka
 287                 }
 288
 289         }
 290         return oldestElem
 291 }
 292
 293 func (a *AddrManager) getNewBucket(netAddr, srcAddr *wire.NetAddress) int {
 294         // bitcoind:
 295         // doublesha256(key + sourcegroup + int64(doublesha256(key + group + sourcegroup))%bucket_per_source_group) % num_new_buckets
 296
 297         data1 := []byte{}
 298         data1 = append(data1, a.key[:]...)
 299         data1 = append(data1, []byte(GroupKey(netAddr))...)
 300         data1 = append(data1, []byte(GroupKey(srcAddr))...)
 301         hash1 := chainhash.DoubleHashB(data1)
 302         hash64 := binary.LittleEndian.Uint64(hash1)
 303         hash64 %= newBucketsPerGroup
 304         var hashbuf [8]byte
 305         binary.LittleEndian.PutUint64(hashbuf[:], hash64)
 306         data2 := []byte{}
 307         data2 = append(data2, a.key[:]...)
 308         data2 = append(data2, GroupKey(srcAddr)...)
 309         data2 = append(data2, hashbuf[:]...)
 310
 311         hash2 := chainhash.DoubleHashB(data2)
 312         return int(binary.LittleEndian.Uint64(hash2) % newBucketCount)
 313 }
 314
 315 func (a *AddrManager) getTriedBucket(netAddr *wire.NetAddress) int {
 316         // bitcoind hashes this as:
 317         // doublesha256(key + group + truncate_to_64bits(doublesha256(key)) % buckets_per_group) % num_buckets
 318         data1 := []byte{}
 319         data1 = append(data1, a.key[:]...)
 320         data1 = append(data1, []byte(NetAddressKey(netAddr))...)
 321         hash1 := chainhash.DoubleHashB(data1)
 322         hash64 := binary.LittleEndian.Uint64(hash1)
 323         hash64 %= triedBucketsPerGroup
 324         var hashbuf [8]byte
 325         binary.LittleEndian.PutUint64(hashbuf[:], hash64)
 326         data2 := []byte{}
 327         data2 = append(data2, a.key[:]...)
 328         data2 = append(data2, GroupKey(netAddr)...)
 329         data2 = append(data2, hashbuf[:]...)
 330
 331         hash2 := chainhash.DoubleHashB(data2)
 332         return int(binary.LittleEndian.Uint64(hash2) % triedBucketCount)
 333 }
 334
 335 // addressHandler is the main handler for the address manager.  It must be run
 336 // as a goroutine.
 337 func (a *AddrManager) addressHandler() {
 338         dumpAddressTicker := time.NewTicker(dumpAddressInterval)
 339         defer dumpAddressTicker.Stop()
 340 out:
 341         for {
 342                 select {
 343                 case <-dumpAddressTicker.C:
 344                         a.savePeers()
 345
 346                 case <-a.quit:
 347                         break out
 348                 }
 349         }
 350         a.savePeers()
 351         a.wg.Done()
 352         log.Trace("Address handler done")
 353 }
 354
 355 // savePeers saves all the known addresses to a file so they can be read back
 356 // in at next run.
 357 func (a *AddrManager) savePeers() {
 358         a.mtx.Lock()
 359         defer a.mtx.Unlock()
 360
 361         // First we make a serialisable datastructure so we can encode it to
 362         // json.
 363         sam := new(serializedAddrManager)
 364         sam.Version = serialisationVersion
 365         copy(sam.Key[:], a.key[:])
 366
 367         sam.Addresses = make([]*serializedKnownAddress, len(a.addrIndex))
 368         i := 0
 369         for k, v := range a.addrIndex {
 370                 ska := new(serializedKnownAddress)
 371                 ska.Addr = k
 372                 ska.TimeStamp = v.na.Timestamp.Unix()
 373                 ska.Src = NetAddressKey(v.srcAddr)
 374                 ska.Attempts = v.attempts
 375                 ska.LastAttempt = v.lastattempt.Unix()
 376                 ska.LastSuccess = v.lastsuccess.Unix()
 377                 // Tried and refs are implicit in the rest of the structure
 378                 // and will be worked out from context on unserialisation.
 379                 sam.Addresses[i] = ska
 380                 i++
 381         }
 382         for i := range a.addrNew {
 383                 sam.NewBuckets[i] = make([]string, len(a.addrNew[i]))
 384                 j := 0
 385                 for k := range a.addrNew[i] {
 386                         sam.NewBuckets[i][j] = k
 387                         j++
 388                 }
 389         }
 390         for i := range a.addrTried {
 391                 sam.TriedBuckets[i] = make([]string, a.addrTried[i].Len())
 392                 j := 0
 393                 for e := a.addrTried[i].Front(); e != nil; e = e.Next() {
 394                         ka := e.Value.(*KnownAddress)
 395                         sam.TriedBuckets[i][j] = NetAddressKey(ka.na)
 396                         j++
 397                 }
 398         }
 399
 400         w, err := os.Create(a.peersFile)
 401         if err != nil {
 402                 log.Errorf("Error opening file %s: %v", a.peersFile, err)
 403                 return
 404         }
 405         enc := json.NewEncoder(w)
 406         defer w.Close()
 407         if err := enc.Encode(&sam); err != nil {
 408                 log.Errorf("Failed to encode file %s: %v", a.peersFile, err)
 409                 return
 410         }
 411 }
 412
 413 // loadPeers loads the known address from the saved file.  If empty, missing, or
 414 // malformed file, just don't load anything and start fresh
 415 func (a *AddrManager) loadPeers() {
 416         a.mtx.Lock()
 417         defer a.mtx.Unlock()
 418
 419         err := a.deserializePeers(a.peersFile)
 420         if err != nil {
 421                 log.Errorf("Failed to parse file %s: %v", a.peersFile, err)
 422                 // if it is invalid we nuke the old one unconditionally.
 423                 err = os.Remove(a.peersFile)
 424                 if err != nil {
 425                         log.Warnf("Failed to remove corrupt peers file %s: %v",
 426                                 a.peersFile, err)
 427                 }
 428                 a.reset()
 429                 return
 430         }
 431         log.Infof("Loaded %d addresses from file '%s'", a.numAddresses(), a.peersFile)
 432 }
 433
 434 func (a *AddrManager) deserializePeers(filePath string) error {
 435
 436         _, err := os.Stat(filePath)
 437         if os.IsNotExist(err) {
 438                 return nil
 439         }
 440         r, err := os.Open(filePath)
 441         if err != nil {
 442                 return fmt.Errorf("%s error opening file: %v", filePath, err)
 443         }
 444         defer r.Close()
 445
 446         var sam serializedAddrManager
 447         dec := json.NewDecoder(r)
 448         err = dec.Decode(&sam)
 449         if err != nil {
 450                 return fmt.Errorf("error reading %s: %v", filePath, err)
 451         }
 452
 453         if sam.Version != serialisationVersion {
 454                 return fmt.Errorf("unknown version %v in serialized "+
 455                         "addrmanager", sam.Version)
 456         }
 457         copy(a.key[:], sam.Key[:])
 458
 459         for _, v := range sam.Addresses {
 460                 ka := new(KnownAddress)
 461                 ka.na, err = a.DeserializeNetAddress(v.Addr)
 462                 if err != nil {
 463                         return fmt.Errorf("failed to deserialize netaddress "+
 464                                 "%s: %v", v.Addr, err)
 465                 }
 466                 ka.srcAddr, err = a.DeserializeNetAddress(v.Src)
 467                 if err != nil {
 468                         return fmt.Errorf("failed to deserialize netaddress "+
 469                                 "%s: %v", v.Src, err)
 470                 }
 471                 ka.attempts = v.Attempts
 472                 ka.lastattempt = time.Unix(v.LastAttempt, 0)
 473                 ka.lastsuccess = time.Unix(v.LastSuccess, 0)
 474                 a.addrIndex[NetAddressKey(ka.na)] = ka
 475         }
 476
 477         for i := range sam.NewBuckets {
 478                 for _, val := range sam.NewBuckets[i] {
 479                         ka, ok := a.addrIndex[val]
 480                         if !ok {
 481                                 return fmt.Errorf("newbucket contains %s but "+
 482                                         "none in address list", val)
 483                         }
 484
 485                         if ka.refs == 0 {
 486                                 a.nNew++
 487                         }
 488                         ka.refs++
 489                         a.addrNew[i][val] = ka
 490                 }
 491         }
 492         for i := range sam.TriedBuckets {
 493                 for _, val := range sam.TriedBuckets[i] {
 494                         ka, ok := a.addrIndex[val]
 495                         if !ok {
 496                                 return fmt.Errorf("Newbucket contains %s but "+
 497                                         "none in address list", val)
 498                         }
 499
 500                         ka.tried = true
 501                         a.nTried++
 502                         a.addrTried[i].PushBack(ka)
 503                 }
 504         }
 505
 506         // Sanity checking.
 507         for k, v := range a.addrIndex {
 508                 if v.refs == 0 && !v.tried {
 509                         return fmt.Errorf("address %s after serialisation "+
 510                                 "with no references", k)
 511                 }
 512
 513                 if v.refs > 0 && v.tried {
 514                         return fmt.Errorf("address %s after serialisation "+
 515                                 "which is both new and tried!", k)
 516                 }
 517         }
 518
 519         return nil
 520 }
 521
 522 // DeserializeNetAddress converts a given address string to a *wire.NetAddress
 523 func (a *AddrManager) DeserializeNetAddress(addr string) (*wire.NetAddress, error) {
 524         host, portStr, err := net.SplitHostPort(addr)
 525         if err != nil {
 526                 return nil, err
 527         }
 528         port, err := strconv.ParseUint(portStr, 10, 16)
 529         if err != nil {
 530                 return nil, err
 531         }
 532
 533         return a.HostToNetAddress(host, uint16(port), wire.SFNodeNetwork)
 534 }
 535
 536 // Start begins the core address handler which manages a pool of known
 537 // addresses, timeouts, and interval based writes.
 538 func (a *AddrManager) Start() {
 539         // Already started?
 540         if atomic.AddInt32(&a.started, 1) != 1 {
 541                 return
 542         }
 543
 544         log.Trace("Starting address manager")
 545
 546         // Load peers we already know about from file.
 547         a.loadPeers()
 548
 549         // Start the address ticker to save addresses periodically.
 550         a.wg.Add(1)
 551         go a.addressHandler()
 552 }
 553
 554 // Stop gracefully shuts down the address manager by stopping the main handler.
 555 func (a *AddrManager) Stop() error {
 556         if atomic.AddInt32(&a.shutdown, 1) != 1 {
 557                 log.Warnf("Address manager is already in the process of " +
 558                         "shutting down")
 559                 return nil
 560         }
 561
 562         log.Infof("Address manager shutting down")
 563         close(a.quit)
 564         a.wg.Wait()
 565         return nil
 566 }
 567
 568 // AddAddresses adds new addresses to the address manager.  It enforces a max
 569 // number of addresses and silently ignores duplicate addresses.  It is
 570 // safe for concurrent access.
 571 func (a *AddrManager) AddAddresses(addrs []*wire.NetAddress, srcAddr *wire.NetAddress) {
 572         a.mtx.Lock()
 573         defer a.mtx.Unlock()
 574
 575         for _, na := range addrs {
 576                 a.updateAddress(na, srcAddr)
 577         }
 578 }
 579
 580 // AddAddress adds a new address to the address manager.  It enforces a max
 581 // number of addresses and silently ignores duplicate addresses.  It is
 582 // safe for concurrent access.
 583 func (a *AddrManager) AddAddress(addr, srcAddr *wire.NetAddress) {
 584         a.mtx.Lock()
 585         defer a.mtx.Unlock()
 586
 587         a.updateAddress(addr, srcAddr)
 588 }
 589
 590 // AddAddressByIP adds an address where we are given an ip:port and not a
 591 // wire.NetAddress.
 592 func (a *AddrManager) AddAddressByIP(addrIP string) error {
 593         // Split IP and port
 594         addr, portStr, err := net.SplitHostPort(addrIP)
 595         if err != nil {
 596                 return err
 597         }
 598         // Put it in wire.Netaddress
 599         ip := net.ParseIP(addr)
 600         if ip == nil {
 601                 return fmt.Errorf("invalid ip address %s", addr)
 602         }
 603         port, err := strconv.ParseUint(portStr, 10, 0)
 604         if err != nil {
 605                 return fmt.Errorf("invalid port %s: %v", portStr, err)
 606         }
 607         na := wire.NewNetAddressIPPort(ip, uint16(port), 0)
 608         a.AddAddress(na, na) // XXX use correct src address
 609         return nil
 610 }
 611
 612 // NumAddresses returns the number of addresses known to the address manager.
 613 func (a *AddrManager) numAddresses() int {
 614         return a.nTried + a.nNew
 615 }
 616
 617 // NumAddresses returns the number of addresses known to the address manager.
 618 func (a *AddrManager) NumAddresses() int {
 619         a.mtx.Lock()
 620         defer a.mtx.Unlock()
 621
 622         return a.numAddresses()
 623 }
 624
 625 // NeedMoreAddresses returns whether or not the address manager needs more
 626 // addresses.
 627 func (a *AddrManager) NeedMoreAddresses() bool {
 628         a.mtx.Lock()
 629         defer a.mtx.Unlock()
 630
 631         return a.numAddresses() < needAddressThreshold
 632 }
 633
 634 // AddressCache returns the current address cache.  It must be treated as
 635 // read-only (but since it is a copy now, this is not as dangerous).
 636 func (a *AddrManager) AddressCache() []*wire.NetAddress {
 637         a.mtx.Lock()
 638         defer a.mtx.Unlock()
 639
 640         addrIndexLen := len(a.addrIndex)
 641         if addrIndexLen == 0 {
 642                 return nil
 643         }
 644
 645         allAddr := make([]*wire.NetAddress, 0, addrIndexLen)
 646         // Iteration order is undefined here, but we randomise it anyway.
 647         for _, v := range a.addrIndex {
 648                 allAddr = append(allAddr, v.na)
 649         }
 650
 651         numAddresses := addrIndexLen * getAddrPercent / 100
 652         if numAddresses > getAddrMax {
 653                 numAddresses = getAddrMax
 654         }
 655
 656         // Fisher-Yates shuffle the array. We only need to do the first
 657         // `numAddresses' since we are throwing the rest.
 658         for i := 0; i < numAddresses; i++ {
 659                 // pick a number between current index and the end
 660                 j := rand.Intn(addrIndexLen-i) + i
 661                 allAddr[i], allAddr[j] = allAddr[j], allAddr[i]
 662         }
 663
 664         // slice off the limit we are willing to share.
 665         return allAddr[0:numAddresses]
 666 }
 667
 668 // reset resets the address manager by reinitialising the random source
 669 // and allocating fresh empty bucket storage.
 670 func (a *AddrManager) reset() {
 671
 672         a.addrIndex = make(map[string]*KnownAddress)
 673
 674         // fill key with bytes from a good random source.
 675         io.ReadFull(crand.Reader, a.key[:])
 676         for i := range a.addrNew {
 677                 a.addrNew[i] = make(map[string]*KnownAddress)
 678         }
 679         for i := range a.addrTried {
 680                 a.addrTried[i] = list.New()
 681         }
 682 }
 683
 684 // HostToNetAddress returns a netaddress given a host address.  If the address
 685 // is a Tor .onion address this will be taken care of.  Else if the host is
 686 // not an IP address it will be resolved (via Tor if required).
 687 func (a *AddrManager) HostToNetAddress(host string, port uint16, services wire.ServiceFlag) (*wire.NetAddress, error) {
 688         // Tor address is 16 char base32 + ".onion"
 689         var ip net.IP
 690         if len(host) == 22 && host[16:] == ".onion" {
 691                 // go base32 encoding uses capitals (as does the rfc
 692                 // but Tor and bitcoind tend to user lowercase, so we switch
 693                 // case here.
 694                 data, err := base32.StdEncoding.DecodeString(
 695                         strings.ToUpper(host[:16]))
 696                 if err != nil {
 697                         return nil, err
 698                 }
 699                 prefix := []byte{0xfd, 0x87, 0xd8, 0x7e, 0xeb, 0x43}
 700                 ip = net.IP(append(prefix, data...))
 701         } else if ip = net.ParseIP(host); ip == nil {
 702                 ips, err := a.lookupFunc(host)
 703                 if err != nil {
 704                         return nil, err
 705                 }
 706                 if len(ips) == 0 {
 707                         return nil, fmt.Errorf("no addresses found for %s", host)
 708                 }
 709                 ip = ips[0]
 710         }
 711
 712         return wire.NewNetAddressIPPort(ip, port, services), nil
 713 }
 714
 715 // ipString returns a string for the ip from the provided NetAddress. If the
 716 // ip is in the range used for Tor addresses then it will be transformed into
 717 // the relevant .onion address.
 718 func ipString(na *wire.NetAddress) string {
 719         if IsOnionCatTor(na) {
 720                 // We know now that na.IP is long enough.
 721                 base32 := base32.StdEncoding.EncodeToString(na.IP[6:])
 722                 return strings.ToLower(base32) + ".onion"
 723         }
 724
 725         return na.IP.String()
 726 }
 727
 728 // NetAddressKey returns a string key in the form of ip:port for IPv4 addresses
 729 // or [ip]:port for IPv6 addresses.
 730 func NetAddressKey(na *wire.NetAddress) string {
 731         port := strconv.FormatUint(uint64(na.Port), 10)
 732
 733         return net.JoinHostPort(ipString(na), port)
 734 }
 735
 736 // GetAddress returns a single address that should be routable.  It picks a
 737 // random one from the possible addresses with preference given to ones that
 738 // have not been used recently and should not pick 'close' addresses
 739 // consecutively.
 740 func (a *AddrManager) GetAddress() *KnownAddress {
 741         // Protect concurrent access.
 742         a.mtx.Lock()
 743         defer a.mtx.Unlock()
 744
 745         if a.numAddresses() == 0 {
 746                 return nil
 747         }
 748
 749         // Use a 50% chance for choosing between tried and new table entries.
 750         if a.nTried > 0 && (a.nNew == 0 || a.rand.Intn(2) == 0) {
 751                 // Tried entry.
 752                 large := 1 << 30
 753                 factor := 1.0
 754                 for {
 755                         // pick a random bucket.
 756                         bucket := a.rand.Intn(len(a.addrTried))
 757                         if a.addrTried[bucket].Len() == 0 {
 758                                 continue
 759                         }
 760
 761                         // Pick a random entry in the list
 762                         e := a.addrTried[bucket].Front()
 763                         for i :=
 764                                 a.rand.Int63n(int64(a.addrTried[bucket].Len())); i > 0; i-- {
 765                                 e = e.Next()
 766                         }
 767                         ka := e.Value.(*KnownAddress)
 768                         randval := a.rand.Intn(large)
 769                         if float64(randval) < (factor * ka.chance() * float64(large)) {
 770                                 log.Tracef("Selected %v from tried bucket",
 771                                         NetAddressKey(ka.na))
 772                                 return ka
 773                         }
 774                         factor *= 1.2
 775                 }
 776         } else {
 777                 // new node.
 778                 // XXX use a closure/function to avoid repeating this.
 779                 large := 1 << 30
 780                 factor := 1.0
 781                 for {
 782                         // Pick a random bucket.
 783                         bucket := a.rand.Intn(len(a.addrNew))
 784                         if len(a.addrNew[bucket]) == 0 {
 785                                 continue
 786                         }
 787                         // Then, a random entry in it.
 788                         var ka *KnownAddress
 789                         nth := a.rand.Intn(len(a.addrNew[bucket]))
 790                         for _, value := range a.addrNew[bucket] {
 791                                 if nth == 0 {
 792                                         ka = value
 793                                 }
 794                                 nth--
 795                         }
 796                         randval := a.rand.Intn(large)
 797                         if float64(randval) < (factor * ka.chance() * float64(large)) {
 798                                 log.Tracef("Selected %v from new bucket",
 799                                         NetAddressKey(ka.na))
 800                                 return ka
 801                         }
 802                         factor *= 1.2
 803                 }
 804         }
 805 }
 806
 807 func (a *AddrManager) find(addr *wire.NetAddress) *KnownAddress {
 808         return a.addrIndex[NetAddressKey(addr)]
 809 }
 810
 811 // Attempt increases the given address' attempt counter and updates
 812 // the last attempt time.
 813 func (a *AddrManager) Attempt(addr *wire.NetAddress) {
 814         a.mtx.Lock()
 815         defer a.mtx.Unlock()
 816
 817         // find address.
 818         // Surely address will be in tried by now?
 819         ka := a.find(addr)
 820         if ka == nil {
 821                 return
 822         }
 823         // set last tried time to now
 824         ka.attempts++
 825         ka.lastattempt = time.Now()
 826 }
 827
 828 // Connected Marks the given address as currently connected and working at the
 829 // current time.  The address must already be known to AddrManager else it will
 830 // be ignored.
 831 func (a *AddrManager) Connected(addr *wire.NetAddress) {
 832         a.mtx.Lock()
 833         defer a.mtx.Unlock()
 834
 835         ka := a.find(addr)
 836         if ka == nil {
 837                 return
 838         }
 839
 840         // Update the time as long as it has been 20 minutes since last we did
 841         // so.
 842         now := time.Now()
 843         if now.After(ka.na.Timestamp.Add(time.Minute * 20)) {
 844                 // ka.na is immutable, so replace it.
 845                 naCopy := *ka.na
 846                 naCopy.Timestamp = time.Now()
 847                 ka.na = &naCopy
 848         }
 849 }
 850
 851 // Good marks the given address as good.  To be called after a successful
 852 // connection and version exchange.  If the address is unknown to the address
 853 // manager it will be ignored.
 854 func (a *AddrManager) Good(addr *wire.NetAddress) {
 855         a.mtx.Lock()
 856         defer a.mtx.Unlock()
 857
 858         ka := a.find(addr)
 859         if ka == nil {
 860                 return
 861         }
 862
 863         // ka.Timestamp is not updated here to avoid leaking information
 864         // about currently connected peers.
 865         now := time.Now()
 866         ka.lastsuccess = now
 867         ka.lastattempt = now
 868         ka.attempts = 0
 869
 870         // move to tried set, optionally evicting other addresses if neeed.
 871         if ka.tried {
 872                 return
 873         }
 874
 875         // ok, need to move it to tried.
 876
 877         // remove from all new buckets.
 878         // record one of the buckets in question and call it the `first'
 879         addrKey := NetAddressKey(addr)
 880         oldBucket := -1
 881         for i := range a.addrNew {
 882                 // we check for existence so we can record the first one
 883                 if _, ok := a.addrNew[i][addrKey]; ok {
 884                         delete(a.addrNew[i], addrKey)
 885                         ka.refs--
 886                         if oldBucket == -1 {
 887                                 oldBucket = i
 888                         }
 889                 }
 890         }
 891         a.nNew--
 892
 893         if oldBucket == -1 {
 894                 // What? wasn't in a bucket after all.... Panic?
 895                 return
 896         }
 897
 898         bucket := a.getTriedBucket(ka.na)
 899
 900         // Room in this tried bucket?
 901         if a.addrTried[bucket].Len() < triedBucketSize {
 902                 ka.tried = true
 903                 a.addrTried[bucket].PushBack(ka)
 904                 a.nTried++
 905                 return
 906         }
 907
 908         // No room, we have to evict something else.
 909         entry := a.pickTried(bucket)
 910         rmka := entry.Value.(*KnownAddress)
 911
 912         // First bucket it would have been put in.
 913         newBucket := a.getNewBucket(rmka.na, rmka.srcAddr)
 914
 915         // If no room in the original bucket, we put it in a bucket we just
 916         // freed up a space in.
 917         if len(a.addrNew[newBucket]) >= newBucketSize {
 918                 newBucket = oldBucket
 919         }
 920
 921         // replace with ka in list.
 922         ka.tried = true
 923         entry.Value = ka
 924
 925         rmka.tried = false
 926         rmka.refs++
 927
 928         // We don't touch a.nTried here since the number of tried stays the same
 929         // but we decemented new above, raise it again since we're putting
 930         // something back.
 931         a.nNew++
 932
 933         rmkey := NetAddressKey(rmka.na)
 934         log.Tracef("Replacing %s with %s in tried", rmkey, addrKey)
 935
 936         // We made sure there is space here just above.
 937         a.addrNew[newBucket][rmkey] = rmka
 938 }
 939
 940 // AddLocalAddress adds na to the list of known local addresses to advertise
 941 // with the given priority.
 942 func (a *AddrManager) AddLocalAddress(na *wire.NetAddress, priority AddressPriority) error {
 943         if !IsRoutable(na) {
 944                 return fmt.Errorf("address %s is not routable", na.IP)
 945         }
 946
 947         a.lamtx.Lock()
 948         defer a.lamtx.Unlock()
 949
 950         key := NetAddressKey(na)
 951         la, ok := a.localAddresses[key]
 952         if !ok || la.score < priority {
 953                 if ok {
 954                         la.score = priority + 1
 955                 } else {
 956                         a.localAddresses[key] = &localAddress{
 957                                 na:    na,
 958                                 score: priority,
 959                         }
 960                 }
 961         }
 962         return nil
 963 }
 964
 965 // getReachabilityFrom returns the relative reachability of the provided local
 966 // address to the provided remote address.
 967 func getReachabilityFrom(localAddr, remoteAddr *wire.NetAddress) int {
 968         const (
 969                 Unreachable = 0
 970                 Default     = iota
 971                 Teredo
 972                 Ipv6Weak
 973                 Ipv4
 974                 Ipv6Strong
 975                 Private
 976         )
 977
 978         if !IsRoutable(remoteAddr) {
 979                 return Unreachable
 980         }
 981
 982         if IsOnionCatTor(remoteAddr) {
 983                 if IsOnionCatTor(localAddr) {
 984                         return Private
 985                 }
 986
 987                 if IsRoutable(localAddr) && IsIPv4(localAddr) {
 988                         return Ipv4
 989                 }
 990
 991                 return Default
 992         }
 993
 994         if IsRFC4380(remoteAddr) {
 995                 if !IsRoutable(localAddr) {
 996                         return Default
 997                 }
 998
 999                 if IsRFC4380(localAddr) {
1000                         return Teredo
1001                 }
1002
1003                 if IsIPv4(localAddr) {
1004                         return Ipv4
1005                 }
1006
1007                 return Ipv6Weak
1008         }
1009
1010         if IsIPv4(remoteAddr) {
1011                 if IsRoutable(localAddr) && IsIPv4(localAddr) {
1012                         return Ipv4
1013                 }
1014                 return Unreachable
1015         }
1016
1017         /* ipv6 */
1018         var tunnelled bool
1019         // Is our v6 is tunnelled?
1020         if IsRFC3964(localAddr) || IsRFC6052(localAddr) || IsRFC6145(localAddr) {
1021                 tunnelled = true
1022         }
1023
1024         if !IsRoutable(localAddr) {
1025                 return Default
1026         }
1027
1028         if IsRFC4380(localAddr) {
1029                 return Teredo
1030         }
1031
1032         if IsIPv4(localAddr) {
1033                 return Ipv4
1034         }
1035
1036         if tunnelled {
1037                 // only prioritise ipv6 if we aren't tunnelling it.
1038                 return Ipv6Weak
1039         }
1040
1041         return Ipv6Strong
1042 }
1043
1044 // GetBestLocalAddress returns the most appropriate local address to use
1045 // for the given remote address.
1046 func (a *AddrManager) GetBestLocalAddress(remoteAddr *wire.NetAddress) *wire.NetAddress {
1047         a.lamtx.Lock()
1048         defer a.lamtx.Unlock()
1049
1050         bestreach := 0
1051         var bestscore AddressPriority
1052         var bestAddress *wire.NetAddress
1053         for _, la := range a.localAddresses {
1054                 reach := getReachabilityFrom(la.na, remoteAddr)
1055                 if reach > bestreach ||
1056                         (reach == bestreach && la.score > bestscore) {
1057                         bestreach = reach
1058                         bestscore = la.score
1059                         bestAddress = la.na
1060                 }
1061         }
1062         if bestAddress != nil {
1063                 log.Debugf("Suggesting address %s:%d for %s:%d", bestAddress.IP,
1064                         bestAddress.Port, remoteAddr.IP, remoteAddr.Port)
1065         } else {
1066                 log.Debugf("No worthy address for %s:%d", remoteAddr.IP,
1067                         remoteAddr.Port)
1068
1069                 // Send something unroutable if nothing suitable.
1070                 var ip net.IP
1071                 if !IsIPv4(remoteAddr) && !IsOnionCatTor(remoteAddr) {
1072                         ip = net.IPv6zero
1073                 } else {
1074                         ip = net.IPv4zero
1075                 }
1076                 services := wire.SFNodeNetwork | wire.SFNodeWitness | wire.SFNodeBloom
1077                 bestAddress = wire.NewNetAddressIPPort(ip, 0, services)
1078         }
1079
1080         return bestAddress
1081 }
1082
1083 // New returns a new bitcoin address manager.
1084 // Use Start to begin processing asynchronous address updates.
1085 func New(dataDir string, lookupFunc func(string) ([]net.IP, error)) *AddrManager {
1086         am := AddrManager{
1087                 peersFile:      filepath.Join(dataDir, "peers.json"),
1088                 lookupFunc:     lookupFunc,
1089                 rand:           rand.New(rand.NewSource(time.Now().UnixNano())),
1090                 quit:           make(chan struct{}),
1091                 localAddresses: make(map[string]*localAddress),
1092         }
1093         am.reset()
1094         return &am
1095 }