geolocate gateways and kd-tree

during initialization, we fetch the eip-config.json file from the
configured provider. we geolocate the gateways (using a golang package
that has some cities missing, hence the workaround) and
initialize a KD-Tree with the gateways.

using the KD-Tree, it is very cheap to calculate the nearest gateway for
every request, which is provider as a filed in the json to the client -
as a suggestion to be used or not in the gateway selection process.

3 files changed, 203 insertions, 2 deletions

diff --git a/gateways.go b/gateways.go
new file mode 100644
index 0000000..404f40a
--- /dev/null
+++ b/gateways.go
@@ -0,0 +1,89 @@
+// Copyright (c) 2018 LEAP Encryption Access Project
+
+package main
+
+import (
+	"encoding/json"
+	"fmt"
+	"net/http"
+)
+
+const (
+	// yes, I am cheating. The config file is also exposed on the top-level
+	// domain, which is served behind a letsencrypt certificate. this saves passing
+	// the certificate for the ca etc.
+	eipAPI = "https://black.riseup.net/1/config/eip-service.json"
+)
+
+type bonafide struct {
+	client *http.Client
+	eip    *eipService
+}
+
+type eipService struct {
+	Gateways  []gateway
+	Locations map[string]struct {
+		CountryCode string
+		Hemisphere  string
+		Name        string
+		Timezone    string
+	}
+}
+
+type gateway struct {
+	Host        string
+	Location    string
+	IPAddress   string `json:"ip_address"`
+	Coordinates coordinates
+}
+
+type coordinates struct {
+	Latitude  float64
+	Longitude float64
+}
+
+func newBonafide() *bonafide {
+	client := &http.Client{}
+	return &bonafide{client, nil}
+}
+
+func (b *bonafide) getGateways() ([]gateway, error) {
+	if b.eip == nil {
+		err := b.fetchEipJSON()
+		if err != nil {
+			return nil, err
+		}
+	}
+	return b.eip.Gateways, nil
+}
+
+func (b *bonafide) fetchEipJSON() error {
+	resp, err := b.client.Post(eipAPI, "", nil)
+	if err != nil {
+		return err
+	}
+	defer resp.Body.Close()
+	if resp.StatusCode != 200 {
+		return fmt.Errorf("get eip json has failed with status: %s", resp.Status)
+	}
+	var eip eipService
+	decoder := json.NewDecoder(resp.Body)
+	err = decoder.Decode(&eip)
+	if err != nil {
+		return err
+	}
+	b.eip = &eip
+	return nil
+}
+
+func (b *bonafide) listGateways() error {
+	if b.eip == nil {
+		return fmt.Errorf("cannot list gateways, it is empty")
+	}
+
+	for i := 0; i < len(b.eip.Gateways); i++ {
+		fmt.Printf("\t%v\n", b.eip.Gateways[i])
+	}
+	return nil
+
+}
diff --git a/geo.go b/geo.go
new file mode 100644
index 0000000..e004fbb
--- /dev/null
+++ b/geo.go
@@ -0,0 +1,40 @@
+package main
+
+import (
+	"github.com/hongshibao/go-kdtree"
+)
+
+type EuclideanPoint struct {
+	kdtree.Point
+	Vec []float64
+}
+
+func (p EuclideanPoint) Dim() int {
+	return len(p.Vec)
+}
+
+func (p EuclideanPoint) GetValue(dim int) float64 {
+	return p.Vec[dim]
+}
+
+func (p EuclideanPoint) Distance(other kdtree.Point) float64 {
+	var ret float64
+	for i := 0; i < p.Dim(); i++ {
+		tmp := p.GetValue(i) - other.GetValue(i)
+		ret += tmp * tmp
+	}
+	return ret
+}
+
+func (p EuclideanPoint) PlaneDistance(val float64, dim int) float64 {
+	tmp := p.GetValue(dim) - val
+	return tmp * tmp
+}
+
+func NewEuclideanPoint(vals ...float64) *EuclideanPoint {
+	ret := &EuclideanPoint{}
+	for _, val := range vals {
+		ret.Vec = append(ret.Vec, val)
+	}
+	return ret
+}
diff --git a/main.go b/main.go
index 4b9b9cf..1767a7c 100644
--- a/main.go
+++ b/main.go
@@ -7,9 +7,14 @@ import (
 	"log"
 	"net"
 	"net/http"
+	"regexp"
 	"strconv"
+	"strings"
 
+	"github.com/StefanSchroeder/Golang-Ellipsoid/ellipsoid"
+	"github.com/hongshibao/go-kdtree"
 	"github.com/oschwald/geoip2-golang"
+	"github.com/tidwall/cities"
 )
 
 func floatToString(num float64) string {
@@ -33,7 +38,55 @@ func getRemoteIP(req *http.Request) string {
 }
 
 type geodb struct {
-	db *geoip2.Reader
+	db          *geoip2.Reader
+	Gateways    []gateway
+	GatewayTree *kdtree.KDTree
+	GatewayMap  map[[3]float64]gateway
+	earth       *ellipsoid.Ellipsoid
+}
+
+func geolocateCity(city string) coordinates {
+	// because some cities apparently are not good enough for the top 10k
+	missingCities := make(map[string]coordinates)
+	missingCities["hongkong"] = coordinates{22.319201099, 114.1696121}
+
+	re := regexp.MustCompile("-| ")
+	for i := 0; i < len(cities.Cities); i++ {
+		c := cities.Cities[i]
+		canonical := strings.ToLower(city)
+		canonical = re.ReplaceAllString(canonical, "")
+		if strings.ToLower(c.City) == canonical {
+			return coordinates{c.Latitude, c.Longitude}
+		}
+		v, ok := missingCities[canonical]
+		if ok == true {
+			return v
+		}
+
+	}
+	return coordinates{0, 0}
+}
+
+func (g *geodb) geolocateGateways(b *bonafide) {
+	g.GatewayMap = make(map[[3]float64]gateway)
+	gatewayPoints := make([]kdtree.Point, 0)
+
+	for i := 0; i < len(b.eip.Gateways); i++ {
+		gw := b.eip.Gateways[i]
+		coord := geolocateCity(gw.Location)
+		gw.Coordinates = coord
+		b.eip.Gateways[i] = gw
+
+		x, y, z := g.earth.ToECEF(coord.Latitude, coord.Longitude, 0)
+
+		p := NewEuclideanPoint(x, y, z)
+		gatewayPoints = append(gatewayPoints, *p)
+		var i [3]float64
+		copy(i[:], p.Vec)
+		g.GatewayMap[i] = gw
+	}
+	g.Gateways = b.eip.Gateways
+	g.GatewayTree = kdtree.NewKDTree(gatewayPoints)
 }
 
 func (g *geodb) getRecordForIP(ipstr string) *geoip2.City {
@@ -52,13 +105,24 @@ type jsonHandler struct {
 func (jh *jsonHandler) ServeHTTP(w http.ResponseWriter, req *http.Request) {
 	ipstr := getRemoteIP(req)
 	record := jh.geoipdb.getRecordForIP(ipstr)
+
+	x, y, z := jh.geoipdb.earth.ToECEF(record.Location.Latitude, record.Location.Longitude, 0)
+
+	t := NewEuclideanPoint(x, y, z)
+	nn := jh.geoipdb.GatewayTree.KNN(t, 1)[0]
+	p := [3]float64{nn.GetValue(0), nn.GetValue(1), nn.GetValue(2)}
+	closestGateway := jh.geoipdb.GatewayMap[p]
+
 	data := map[string]string{
 		"ip":   ipstr,
 		"cc":   record.Country.IsoCode,
 		"city": record.City.Names["en"],
 		"lat":  floatToString(record.Location.Latitude),
 		"lon":  floatToString(record.Location.Longitude),
+		"gw":   closestGateway.Location,
+		"gwip": closestGateway.IPAddress,
 	}
+
 	dataJSON, _ := json.Marshal(data)
 	fmt.Fprintf(w, string(dataJSON))
 }
@@ -90,7 +154,15 @@ func main() {
 	}
 	defer db.Close()
 
-	geoipdb := geodb{db}
+	earth := ellipsoid.Init("WGS84", ellipsoid.Degrees, ellipsoid.Meter, ellipsoid.LongitudeIsSymmetric, ellipsoid.BearingIsSymmetric)
+	geoipdb := geodb{db, nil, nil, nil, &earth}
+
+	log.Println("Seeding gateway list...")
+	bonafide := newBonafide()
+	bonafide.getGateways()
+
+	geoipdb.geolocateGateways(bonafide)
+	bonafide.listGateways()
 
 	mux := http.NewServeMux()
 	jh := &jsonHandler{&geoipdb}