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