p2p/addrbook.go

   1 // Modified for Tendermint
   2 // Originally Copyright (c) 2013-2014 Conformal Systems LLC.
   3 // https://github.com/conformal/btcd/blob/master/LICENSE
   4
   5 package p2p
   6
   7 import (
   8         "encoding/binary"
   9         "encoding/json"
  10         "math"
  11         "math/rand"
  12         "net"
  13         "os"
  14         "sync"
  15         "time"
  16
  17         log "github.com/sirupsen/logrus"
  18         crypto "github.com/tendermint/go-crypto"
  19         cmn "github.com/tendermint/tmlibs/common"
  20 )
  21
  22 const (
  23         // addresses under which the address manager will claim to need more addresses.
  24         needAddressThreshold = 1000
  25
  26         // interval used to dump the address cache to disk for future use.
  27         dumpAddressInterval = time.Minute * 2
  28
  29         // max addresses in each old address bucket.
  30         oldBucketSize = 64
  31
  32         // buckets we split old addresses over.
  33         oldBucketCount = 64
  34
  35         // max addresses in each new address bucket.
  36         newBucketSize = 64
  37
  38         // buckets that we spread new addresses over.
  39         newBucketCount = 256
  40
  41         // old buckets over which an address group will be spread.
  42         oldBucketsPerGroup = 4
  43
  44         // new buckets over which an source address group will be spread.
  45         newBucketsPerGroup = 32
  46
  47         // buckets a frequently seen new address may end up in.
  48         maxNewBucketsPerAddress = 4
  49
  50         // days before which we assume an address has vanished
  51         // if we have not seen it announced in that long.
  52         numMissingDays = 30
  53
  54         // tries without a single success before we assume an address is bad.
  55         numRetries = 3
  56
  57         // max failures we will accept without a success before considering an address bad.
  58         maxFailures = 10
  59
  60         // days since the last success before we will consider evicting an address.
  61         minBadDays = 7
  62
  63         // % of total addresses known returned by GetSelection.
  64         getSelectionPercent = 23
  65
  66         // min addresses that must be returned by GetSelection. Useful for bootstrapping.
  67         minGetSelection = 32
  68
  69         // max addresses returned by GetSelection
  70         // NOTE: this must match "maxPexMessageSize"
  71         maxGetSelection = 250
  72
  73         // current version of the on-disk format.
  74         serializationVersion = 1
  75 )
  76
  77 const (
  78         bucketTypeNew = 0x01
  79         bucketTypeOld = 0x02
  80 )
  81
  82 // AddrBook - concurrency safe peer address manager.
  83 type AddrBook struct {
  84         cmn.BaseService
  85
  86         mtx               sync.Mutex
  87         filePath          string
  88         routabilityStrict bool
  89         rand              *rand.Rand
  90         key               string
  91         ourAddrs          map[string]*NetAddress
  92         addrLookup        map[string]*knownAddress // new & old
  93         addrNew           []map[string]*knownAddress
  94         addrOld           []map[string]*knownAddress
  95         wg                sync.WaitGroup
  96         nOld              int
  97         nNew              int
  98 }
  99
 100 // NewAddrBook creates a new address book.
 101 // Use Start to begin processing asynchronous address updates.
 102 func NewAddrBook(filePath string, routabilityStrict bool) *AddrBook {
 103         am := &AddrBook{
 104                 rand:              rand.New(rand.NewSource(time.Now().UnixNano())),
 105                 ourAddrs:          make(map[string]*NetAddress),
 106                 addrLookup:        make(map[string]*knownAddress),
 107                 filePath:          filePath,
 108                 routabilityStrict: routabilityStrict,
 109         }
 110         am.init()
 111         am.BaseService = *cmn.NewBaseService(nil, "AddrBook", am)
 112         return am
 113 }
 114
 115 // When modifying this, don't forget to update loadFromFile()
 116 func (a *AddrBook) init() {
 117         a.key = crypto.CRandHex(24) // 24/2 * 8 = 96 bits
 118         // New addr buckets
 119         a.addrNew = make([]map[string]*knownAddress, newBucketCount)
 120         for i := range a.addrNew {
 121                 a.addrNew[i] = make(map[string]*knownAddress)
 122         }
 123         // Old addr buckets
 124         a.addrOld = make([]map[string]*knownAddress, oldBucketCount)
 125         for i := range a.addrOld {
 126                 a.addrOld[i] = make(map[string]*knownAddress)
 127         }
 128 }
 129
 130 // OnStart implements Service.
 131 func (a *AddrBook) OnStart() error {
 132         a.BaseService.OnStart()
 133         a.loadFromFile(a.filePath)
 134         a.wg.Add(1)
 135         go a.saveRoutine()
 136         return nil
 137 }
 138
 139 // OnStop implements Service.
 140 func (a *AddrBook) OnStop() {
 141         a.BaseService.OnStop()
 142 }
 143
 144 func (a *AddrBook) Wait() {
 145         a.wg.Wait()
 146 }
 147
 148 func (a *AddrBook) AddOurAddress(addr *NetAddress) {
 149         a.mtx.Lock()
 150         defer a.mtx.Unlock()
 151         log.WithField("addr", addr).Info("Add our address to book")
 152
 153         a.ourAddrs[addr.String()] = addr
 154 }
 155
 156 func (a *AddrBook) OurAddresses() []*NetAddress {
 157         addrs := []*NetAddress{}
 158         for _, addr := range a.ourAddrs {
 159                 addrs = append(addrs, addr)
 160         }
 161         return addrs
 162 }
 163
 164 // NOTE: addr must not be nil
 165 func (a *AddrBook) AddAddress(addr *NetAddress, src *NetAddress) {
 166         a.mtx.Lock()
 167         defer a.mtx.Unlock()
 168         log.WithFields(log.Fields{
 169                 "addr": addr,
 170                 "src":  src,
 171         }).Debug("Add address to book")
 172         a.addAddress(addr, src)
 173 }
 174
 175 func (a *AddrBook) NeedMoreAddrs() bool {
 176         return a.Size() < needAddressThreshold
 177 }
 178
 179 func (a *AddrBook) Size() int {
 180         a.mtx.Lock()
 181         defer a.mtx.Unlock()
 182         return a.size()
 183 }
 184
 185 func (a *AddrBook) size() int {
 186         return a.nNew + a.nOld
 187 }
 188
 189 // Pick an address to connect to with new/old bias.
 190 func (a *AddrBook) PickAddress(newBias int) *NetAddress {
 191         a.mtx.Lock()
 192         defer a.mtx.Unlock()
 193
 194         if a.size() == 0 {
 195                 return nil
 196         }
 197         if newBias > 100 {
 198                 newBias = 100
 199         }
 200         if newBias < 0 {
 201                 newBias = 0
 202         }
 203
 204         // Bias between new and old addresses.
 205         oldCorrelation := math.Sqrt(float64(a.nOld)) * (100.0 - float64(newBias))
 206         newCorrelation := math.Sqrt(float64(a.nNew)) * float64(newBias)
 207
 208         if (newCorrelation+oldCorrelation)*a.rand.Float64() < oldCorrelation {
 209                 // pick random Old bucket.
 210                 var bucket map[string]*knownAddress = nil
 211                 num := 0
 212                 for len(bucket) == 0 && num < oldBucketCount {
 213                         bucket = a.addrOld[a.rand.Intn(len(a.addrOld))]
 214                         num++
 215                 }
 216                 if num == oldBucketCount {
 217                         return nil
 218                 }
 219                 // pick a random ka from bucket.
 220                 randIndex := a.rand.Intn(len(bucket))
 221                 for _, ka := range bucket {
 222                         if randIndex == 0 {
 223                                 return ka.Addr
 224                         }
 225                         randIndex--
 226                 }
 227                 cmn.PanicSanity("Should not happen")
 228         } else {
 229                 // pick random New bucket.
 230                 var bucket map[string]*knownAddress = nil
 231                 num := 0
 232                 for len(bucket) == 0 && num < newBucketCount {
 233                         bucket = a.addrNew[a.rand.Intn(len(a.addrNew))]
 234                         num++
 235                 }
 236                 if num == newBucketCount {
 237                         return nil
 238                 }
 239                 // pick a random ka from bucket.
 240                 randIndex := a.rand.Intn(len(bucket))
 241                 for _, ka := range bucket {
 242                         if randIndex == 0 {
 243                                 return ka.Addr
 244                         }
 245                         randIndex--
 246                 }
 247                 cmn.PanicSanity("Should not happen")
 248         }
 249         return nil
 250 }
 251
 252 func (a *AddrBook) MarkGood(addr *NetAddress) {
 253         a.mtx.Lock()
 254         defer a.mtx.Unlock()
 255         ka := a.addrLookup[addr.String()]
 256         if ka == nil {
 257                 return
 258         }
 259         ka.markGood()
 260         if ka.isNew() {
 261                 a.moveToOld(ka)
 262         }
 263 }
 264
 265 func (a *AddrBook) MarkAttempt(addr *NetAddress) {
 266         a.mtx.Lock()
 267         defer a.mtx.Unlock()
 268         ka := a.addrLookup[addr.String()]
 269         if ka == nil {
 270                 return
 271         }
 272         ka.markAttempt()
 273 }
 274
 275 // MarkBad currently just ejects the address. In the future, consider
 276 // blacklisting.
 277 func (a *AddrBook) MarkBad(addr *NetAddress) {
 278         a.RemoveAddress(addr)
 279 }
 280
 281 // RemoveAddress removes the address from the book.
 282 func (a *AddrBook) RemoveAddress(addr *NetAddress) {
 283         a.mtx.Lock()
 284         defer a.mtx.Unlock()
 285         ka := a.addrLookup[addr.String()]
 286         if ka == nil {
 287                 return
 288         }
 289         log.WithField("addr", addr).Info("Remove address from book")
 290         a.removeFromAllBuckets(ka)
 291 }
 292
 293 /* Peer exchange */
 294
 295 // GetSelection randomly selects some addresses (old & new). Suitable for peer-exchange protocols.
 296 func (a *AddrBook) GetSelection() []*NetAddress {
 297         a.mtx.Lock()
 298         defer a.mtx.Unlock()
 299
 300         if a.size() == 0 {
 301                 return nil
 302         }
 303
 304         allAddr := make([]*NetAddress, a.size())
 305         i := 0
 306         for _, v := range a.addrLookup {
 307                 allAddr[i] = v.Addr
 308                 i++
 309         }
 310
 311         numAddresses := cmn.MaxInt(
 312                 cmn.MinInt(minGetSelection, len(allAddr)),
 313                 len(allAddr)*getSelectionPercent/100)
 314         numAddresses = cmn.MinInt(maxGetSelection, numAddresses)
 315
 316         // Fisher-Yates shuffle the array. We only need to do the first
 317         // `numAddresses' since we are throwing the rest.
 318         for i := 0; i < numAddresses; i++ {
 319                 // pick a number between current index and the end
 320                 j := rand.Intn(len(allAddr)-i) + i
 321                 allAddr[i], allAddr[j] = allAddr[j], allAddr[i]
 322         }
 323
 324         // slice off the limit we are willing to share.
 325         return allAddr[:numAddresses]
 326 }
 327
 328 /* Loading & Saving */
 329
 330 type addrBookJSON struct {
 331         Key   string
 332         Addrs []*knownAddress
 333 }
 334
 335 func (a *AddrBook) saveToFile(filePath string) {
 336         log.WithField("size", a.Size()).Info("Saving AddrBook to file")
 337
 338         a.mtx.Lock()
 339         defer a.mtx.Unlock()
 340         // Compile Addrs
 341         addrs := []*knownAddress{}
 342         for _, ka := range a.addrLookup {
 343                 addrs = append(addrs, ka)
 344         }
 345
 346         aJSON := &addrBookJSON{
 347                 Key:   a.key,
 348                 Addrs: addrs,
 349         }
 350
 351         jsonBytes, err := json.MarshalIndent(aJSON, "", "\t")
 352         if err != nil {
 353                 log.WithField("err", err).Error("Failed to save AddrBook to file")
 354                 return
 355         }
 356         err = cmn.WriteFileAtomic(filePath, jsonBytes, 0644)
 357         if err != nil {
 358                 log.WithFields(log.Fields{
 359                         "file": filePath,
 360                         "err":  err,
 361                 }).Error("Failed to save AddrBook to file")
 362         }
 363 }
 364
 365 // Returns false if file does not exist.
 366 // cmn.Panics if file is corrupt.
 367 func (a *AddrBook) loadFromFile(filePath string) bool {
 368         // If doesn't exist, do nothing.
 369         _, err := os.Stat(filePath)
 370         if os.IsNotExist(err) {
 371                 return false
 372         }
 373
 374         // Load addrBookJSON{}
 375         r, err := os.Open(filePath)
 376         if err != nil {
 377                 cmn.PanicCrisis(cmn.Fmt("Error opening file %s: %v", filePath, err))
 378         }
 379         defer r.Close()
 380         aJSON := &addrBookJSON{}
 381         dec := json.NewDecoder(r)
 382         err = dec.Decode(aJSON)
 383         if err != nil {
 384                 cmn.PanicCrisis(cmn.Fmt("Error reading file %s: %v", filePath, err))
 385         }
 386
 387         // Restore all the fields...
 388         // Restore the key
 389         a.key = aJSON.Key
 390         // Restore .addrNew & .addrOld
 391         for _, ka := range aJSON.Addrs {
 392                 for _, bucketIndex := range ka.Buckets {
 393                         bucket := a.getBucket(ka.BucketType, bucketIndex)
 394                         bucket[ka.Addr.String()] = ka
 395                 }
 396                 a.addrLookup[ka.Addr.String()] = ka
 397                 if ka.BucketType == bucketTypeNew {
 398                         a.nNew++
 399                 } else {
 400                         a.nOld++
 401                 }
 402         }
 403         return true
 404 }
 405
 406 // Save saves the book.
 407 func (a *AddrBook) Save() {
 408         log.WithField("size", a.Size()).Info("Saving AddrBook to file")
 409         a.saveToFile(a.filePath)
 410 }
 411
 412 /* Private methods */
 413
 414 func (a *AddrBook) saveRoutine() {
 415         dumpAddressTicker := time.NewTicker(dumpAddressInterval)
 416 out:
 417         for {
 418                 select {
 419                 case <-dumpAddressTicker.C:
 420                         a.saveToFile(a.filePath)
 421                 case <-a.Quit:
 422                         break out
 423                 }
 424         }
 425         dumpAddressTicker.Stop()
 426         a.saveToFile(a.filePath)
 427         a.wg.Done()
 428         log.Info("Address handler done")
 429 }
 430
 431 func (a *AddrBook) getBucket(bucketType byte, bucketIdx int) map[string]*knownAddress {
 432         switch bucketType {
 433         case bucketTypeNew:
 434                 return a.addrNew[bucketIdx]
 435         case bucketTypeOld:
 436                 return a.addrOld[bucketIdx]
 437         default:
 438                 cmn.PanicSanity("Should not happen")
 439                 return nil
 440         }
 441 }
 442
 443 // Adds ka to new bucket. Returns false if it couldn't do it cuz buckets full.
 444 // NOTE: currently it always returns true.
 445 func (a *AddrBook) addToNewBucket(ka *knownAddress, bucketIdx int) bool {
 446         // Sanity check
 447         if ka.isOld() {
 448                 log.Error(cmn.Fmt("Cannot add address already in old bucket to a new bucket: %v", ka))
 449                 return false
 450         }
 451
 452         addrStr := ka.Addr.String()
 453         bucket := a.getBucket(bucketTypeNew, bucketIdx)
 454
 455         // Already exists?
 456         if _, ok := bucket[addrStr]; ok {
 457                 return true
 458         }
 459
 460         // Enforce max addresses.
 461         if len(bucket) > newBucketSize {
 462                 log.Info("new bucket is full, expiring old ")
 463                 a.expireNew(bucketIdx)
 464         }
 465
 466         // Add to bucket.
 467         bucket[addrStr] = ka
 468         if ka.addBucketRef(bucketIdx) == 1 {
 469                 a.nNew++
 470         }
 471
 472         // Ensure in addrLookup
 473         a.addrLookup[addrStr] = ka
 474
 475         return true
 476 }
 477
 478 // Adds ka to old bucket. Returns false if it couldn't do it cuz buckets full.
 479 func (a *AddrBook) addToOldBucket(ka *knownAddress, bucketIdx int) bool {
 480         // Sanity check
 481         if ka.isNew() {
 482                 log.Error(cmn.Fmt("Cannot add new address to old bucket: %v", ka))
 483                 return false
 484         }
 485         if len(ka.Buckets) != 0 {
 486                 log.Error(cmn.Fmt("Cannot add already old address to another old bucket: %v", ka))
 487                 return false
 488         }
 489
 490         addrStr := ka.Addr.String()
 491         bucket := a.getBucket(bucketTypeNew, bucketIdx)
 492
 493         // Already exists?
 494         if _, ok := bucket[addrStr]; ok {
 495                 return true
 496         }
 497
 498         // Enforce max addresses.
 499         if len(bucket) > oldBucketSize {
 500                 return false
 501         }
 502
 503         // Add to bucket.
 504         bucket[addrStr] = ka
 505         if ka.addBucketRef(bucketIdx) == 1 {
 506                 a.nOld++
 507         }
 508
 509         // Ensure in addrLookup
 510         a.addrLookup[addrStr] = ka
 511
 512         return true
 513 }
 514
 515 func (a *AddrBook) removeFromBucket(ka *knownAddress, bucketType byte, bucketIdx int) {
 516         if ka.BucketType != bucketType {
 517                 log.Error(cmn.Fmt("Bucket type mismatch: %v", ka))
 518                 return
 519         }
 520         bucket := a.getBucket(bucketType, bucketIdx)
 521         delete(bucket, ka.Addr.String())
 522         if ka.removeBucketRef(bucketIdx) == 0 {
 523                 if bucketType == bucketTypeNew {
 524                         a.nNew--
 525                 } else {
 526                         a.nOld--
 527                 }
 528                 delete(a.addrLookup, ka.Addr.String())
 529         }
 530 }
 531
 532 func (a *AddrBook) removeFromAllBuckets(ka *knownAddress) {
 533         for _, bucketIdx := range ka.Buckets {
 534                 bucket := a.getBucket(ka.BucketType, bucketIdx)
 535                 delete(bucket, ka.Addr.String())
 536         }
 537         ka.Buckets = nil
 538         if ka.BucketType == bucketTypeNew {
 539                 a.nNew--
 540         } else {
 541                 a.nOld--
 542         }
 543         delete(a.addrLookup, ka.Addr.String())
 544 }
 545
 546 func (a *AddrBook) pickOldest(bucketType byte, bucketIdx int) *knownAddress {
 547         bucket := a.getBucket(bucketType, bucketIdx)
 548         var oldest *knownAddress
 549         for _, ka := range bucket {
 550                 if oldest == nil || ka.LastAttempt.Before(oldest.LastAttempt) {
 551                         oldest = ka
 552                 }
 553         }
 554         return oldest
 555 }
 556
 557 func (a *AddrBook) addAddress(addr, src *NetAddress) {
 558         if a.routabilityStrict && !addr.Routable() {
 559                 log.Error(cmn.Fmt("Cannot add non-routable address %v", addr))
 560                 return
 561         }
 562         if _, ok := a.ourAddrs[addr.String()]; ok {
 563                 // Ignore our own listener address.
 564                 return
 565         }
 566
 567         ka := a.addrLookup[addr.String()]
 568
 569         if ka != nil {
 570                 // Already old.
 571                 if ka.isOld() {
 572                         return
 573                 }
 574                 // Already in max new buckets.
 575                 if len(ka.Buckets) == maxNewBucketsPerAddress {
 576                         return
 577                 }
 578                 // The more entries we have, the less likely we are to add more.
 579                 factor := int32(2 * len(ka.Buckets))
 580                 if a.rand.Int31n(factor) != 0 {
 581                         return
 582                 }
 583         } else {
 584                 ka = newKnownAddress(addr, src)
 585         }
 586
 587         bucket := a.calcNewBucket(addr, src)
 588         a.addToNewBucket(ka, bucket)
 589
 590         log.Info("Added new address ", "address:", addr, " total:", a.size())
 591 }
 592
 593 // Make space in the new buckets by expiring the really bad entries.
 594 // If no bad entries are available we remove the oldest.
 595 func (a *AddrBook) expireNew(bucketIdx int) {
 596         for addrStr, ka := range a.addrNew[bucketIdx] {
 597                 // If an entry is bad, throw it away
 598                 if ka.isBad() {
 599                         log.Info(cmn.Fmt("expiring bad address %v", addrStr))
 600                         a.removeFromBucket(ka, bucketTypeNew, bucketIdx)
 601                         return
 602                 }
 603         }
 604
 605         // If we haven't thrown out a bad entry, throw out the oldest entry
 606         oldest := a.pickOldest(bucketTypeNew, bucketIdx)
 607         a.removeFromBucket(oldest, bucketTypeNew, bucketIdx)
 608 }
 609
 610 // Promotes an address from new to old.
 611 // TODO: Move to old probabilistically.
 612 // The better a node is, the less likely it should be evicted from an old bucket.
 613 func (a *AddrBook) moveToOld(ka *knownAddress) {
 614         // Sanity check
 615         if ka.isOld() {
 616                 log.Error(cmn.Fmt("Cannot promote address that is already old %v", ka))
 617                 return
 618         }
 619         if len(ka.Buckets) == 0 {
 620                 log.Error(cmn.Fmt("Cannot promote address that isn't in any new buckets %v", ka))
 621                 return
 622         }
 623
 624         // Remember one of the buckets in which ka is in.
 625         freedBucket := ka.Buckets[0]
 626         // Remove from all (new) buckets.
 627         a.removeFromAllBuckets(ka)
 628         // It's officially old now.
 629         ka.BucketType = bucketTypeOld
 630
 631         // Try to add it to its oldBucket destination.
 632         oldBucketIdx := a.calcOldBucket(ka.Addr)
 633         added := a.addToOldBucket(ka, oldBucketIdx)
 634         if !added {
 635                 // No room, must evict something
 636                 oldest := a.pickOldest(bucketTypeOld, oldBucketIdx)
 637                 a.removeFromBucket(oldest, bucketTypeOld, oldBucketIdx)
 638                 // Find new bucket to put oldest in
 639                 newBucketIdx := a.calcNewBucket(oldest.Addr, oldest.Src)
 640                 added := a.addToNewBucket(oldest, newBucketIdx)
 641                 // No space in newBucket either, just put it in freedBucket from above.
 642                 if !added {
 643                         added := a.addToNewBucket(oldest, freedBucket)
 644                         if !added {
 645                                 log.Error(cmn.Fmt("Could not migrate oldest %v to freedBucket %v", oldest, freedBucket))
 646                         }
 647                 }
 648                 // Finally, add to bucket again.
 649                 added = a.addToOldBucket(ka, oldBucketIdx)
 650                 if !added {
 651                         log.Error(cmn.Fmt("Could not re-add ka %v to oldBucketIdx %v", ka, oldBucketIdx))
 652                 }
 653         }
 654 }
 655
 656 // doublesha256(  key + sourcegroup +
 657 //                int64(doublesha256(key + group + sourcegroup))%bucket_per_group  ) % num_new_buckets
 658 func (a *AddrBook) calcNewBucket(addr, src *NetAddress) int {
 659         data1 := []byte{}
 660         data1 = append(data1, []byte(a.key)...)
 661         data1 = append(data1, []byte(a.groupKey(addr))...)
 662         data1 = append(data1, []byte(a.groupKey(src))...)
 663         hash1 := doubleSha256(data1)
 664         hash64 := binary.BigEndian.Uint64(hash1)
 665         hash64 %= newBucketsPerGroup
 666         var hashbuf [8]byte
 667         binary.BigEndian.PutUint64(hashbuf[:], hash64)
 668         data2 := []byte{}
 669         data2 = append(data2, []byte(a.key)...)
 670         data2 = append(data2, a.groupKey(src)...)
 671         data2 = append(data2, hashbuf[:]...)
 672
 673         hash2 := doubleSha256(data2)
 674         return int(binary.BigEndian.Uint64(hash2) % newBucketCount)
 675 }
 676
 677 // doublesha256(  key + group +
 678 //                int64(doublesha256(key + addr))%buckets_per_group  ) % num_old_buckets
 679 func (a *AddrBook) calcOldBucket(addr *NetAddress) int {
 680         data1 := []byte{}
 681         data1 = append(data1, []byte(a.key)...)
 682         data1 = append(data1, []byte(addr.String())...)
 683         hash1 := doubleSha256(data1)
 684         hash64 := binary.BigEndian.Uint64(hash1)
 685         hash64 %= oldBucketsPerGroup
 686         var hashbuf [8]byte
 687         binary.BigEndian.PutUint64(hashbuf[:], hash64)
 688         data2 := []byte{}
 689         data2 = append(data2, []byte(a.key)...)
 690         data2 = append(data2, a.groupKey(addr)...)
 691         data2 = append(data2, hashbuf[:]...)
 692
 693         hash2 := doubleSha256(data2)
 694         return int(binary.BigEndian.Uint64(hash2) % oldBucketCount)
 695 }
 696
 697 // Return a string representing the network group of this address.
 698 // This is the /16 for IPv6, the /32 (/36 for he.net) for IPv6, the string
 699 // "local" for a local address and the string "unroutable for an unroutable
 700 // address.
 701 func (a *AddrBook) groupKey(na *NetAddress) string {
 702         if a.routabilityStrict && na.Local() {
 703                 return "local"
 704         }
 705         if a.routabilityStrict && !na.Routable() {
 706                 return "unroutable"
 707         }
 708
 709         if ipv4 := na.IP.To4(); ipv4 != nil {
 710                 return (&net.IPNet{IP: na.IP, Mask: net.CIDRMask(16, 32)}).String()
 711         }
 712         if na.RFC6145() || na.RFC6052() {
 713                 // last four bytes are the ip address
 714                 ip := net.IP(na.IP[12:16])
 715                 return (&net.IPNet{IP: ip, Mask: net.CIDRMask(16, 32)}).String()
 716         }
 717
 718         if na.RFC3964() {
 719                 ip := net.IP(na.IP[2:7])
 720                 return (&net.IPNet{IP: ip, Mask: net.CIDRMask(16, 32)}).String()
 721
 722         }
 723         if na.RFC4380() {
 724                 // teredo tunnels have the last 4 bytes as the v4 address XOR
 725                 // 0xff.
 726                 ip := net.IP(make([]byte, 4))
 727                 for i, byte := range na.IP[12:16] {
 728                         ip[i] = byte ^ 0xff
 729                 }
 730                 return (&net.IPNet{IP: ip, Mask: net.CIDRMask(16, 32)}).String()
 731         }
 732
 733         // OK, so now we know ourselves to be a IPv6 address.
 734         // bitcoind uses /32 for everything, except for Hurricane Electric's
 735         // (he.net) IP range, which it uses /36 for.
 736         bits := 32
 737         heNet := &net.IPNet{IP: net.ParseIP("2001:470::"),
 738                 Mask: net.CIDRMask(32, 128)}
 739         if heNet.Contains(na.IP) {
 740                 bits = 36
 741         }
 742
 743         return (&net.IPNet{IP: na.IP, Mask: net.CIDRMask(bits, 128)}).String()
 744 }
 745
 746 //-----------------------------------------------------------------------------
 747
 748 /*
 749    knownAddress
 750
 751    tracks information about a known network address that is used
 752    to determine how viable an address is.
 753 */
 754 type knownAddress struct {
 755         Addr        *NetAddress
 756         Src         *NetAddress
 757         Attempts    int32
 758         LastAttempt time.Time
 759         LastSuccess time.Time
 760         BucketType  byte
 761         Buckets     []int
 762 }
 763
 764 func newKnownAddress(addr *NetAddress, src *NetAddress) *knownAddress {
 765         return &knownAddress{
 766                 Addr:        addr,
 767                 Src:         src,
 768                 Attempts:    0,
 769                 LastAttempt: time.Now(),
 770                 BucketType:  bucketTypeNew,
 771                 Buckets:     nil,
 772         }
 773 }
 774
 775 func (ka *knownAddress) isOld() bool {
 776         return ka.BucketType == bucketTypeOld
 777 }
 778
 779 func (ka *knownAddress) isNew() bool {
 780         return ka.BucketType == bucketTypeNew
 781 }
 782
 783 func (ka *knownAddress) markAttempt() {
 784         now := time.Now()
 785         ka.LastAttempt = now
 786         ka.Attempts += 1
 787 }
 788
 789 func (ka *knownAddress) markGood() {
 790         now := time.Now()
 791         ka.LastAttempt = now
 792         ka.Attempts = 0
 793         ka.LastSuccess = now
 794 }
 795
 796 func (ka *knownAddress) addBucketRef(bucketIdx int) int {
 797         for _, bucket := range ka.Buckets {
 798                 if bucket == bucketIdx {
 799                         // TODO refactor to return error?
 800                         // log.Warn(Fmt("Bucket already exists in ka.Buckets: %v", ka))
 801                         return -1
 802                 }
 803         }
 804         ka.Buckets = append(ka.Buckets, bucketIdx)
 805         return len(ka.Buckets)
 806 }
 807
 808 func (ka *knownAddress) removeBucketRef(bucketIdx int) int {
 809         buckets := []int{}
 810         for _, bucket := range ka.Buckets {
 811                 if bucket != bucketIdx {
 812                         buckets = append(buckets, bucket)
 813                 }
 814         }
 815         if len(buckets) != len(ka.Buckets)-1 {
 816                 // TODO refactor to return error?
 817                 // log.Warn(Fmt("bucketIdx not found in ka.Buckets: %v", ka))
 818                 return -1
 819         }
 820         ka.Buckets = buckets
 821         return len(ka.Buckets)
 822 }
 823
 824 /*
 825    An address is bad if the address in question has not been tried in the last
 826    minute and meets one of the following criteria:
 827
 828    1) It claims to be from the future
 829    2) It hasn't been seen in over a month
 830    3) It has failed at least three times and never succeeded
 831    4) It has failed ten times in the last week
 832
 833    All addresses that meet these criteria are assumed to be worthless and not
 834    worth keeping hold of.
 835 */
 836 func (ka *knownAddress) isBad() bool {
 837         // Has been attempted in the last minute --> good
 838         if ka.LastAttempt.After(time.Now().Add(-1 * time.Minute)) {
 839                 return true
 840         }
 841
 842         // Over a month old?
 843         if ka.LastAttempt.Before(time.Now().Add(-1 * numMissingDays * time.Hour * 24)) {
 844                 return true
 845         }
 846
 847         // Never succeeded?
 848         if ka.LastSuccess.IsZero() && ka.Attempts >= numRetries {
 849                 return true
 850         }
 851
 852         // Hasn't succeeded in too long?
 853         if ka.LastSuccess.Before(time.Now().Add(-1*minBadDays*time.Hour*24)) &&
 854                 ka.Attempts >= maxFailures {
 855                 return true
 856         }
 857
 858         return false
 859 }