1 /* Copyright © 2012 Brandon L Black <blblack@gmail.com>
2 *
3 * This file is part of gdnsd.
4 *
5 * gdnsd-plugin-geoip is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * gdnsd-plugin-geoip is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with gdnsd. If not, see <http://www.gnu.org/licenses/>.
17 *
18 */
19
20 // gdmaps = GeoIP -> Datacenter Mapping library code
21
22 #include <config.h>
23 #include "dclists.h"
24
25 #include <gdnsd/alloc.h>
26 #include <gdnsd/log.h>
27 #include <gdnsd/vscf.h>
28
29 #include <math.h>
30
31 /***************************************
32 * dclists_t and related methods
33 **************************************/
34
35 // dclists_t is a storage container for unique ordered
36 // lists of datacenters to be used for lookup results.
37 // It keeps a const pointer to this map's dcinfo_t for reference
38 // because many of its operations require that data.
39 // Because city-auto mode needs to add lists to this very
40 // late in the game (at db load time, which happens "late"
41 // on initial load, and randomly later when geoip db's are
42 // updated on the filesystem), we also have to be able
43 // to update this structure when we create the ntree_t
44 // later.
45 // So it has a clone operation which clones the list and
46 // copies the string pointers, and various levels of
47 // destroy operation that destroy only the newly-added
48 // strings, all strings, or no strings.
49 // The idea is when a new tree is being constructed on the
50 // side in the reload thread, it clones the current runtime
51 // tree and adds new strings to it as necc (which won't
52 // be often, most likely, since we've already stored most
53 // likely orderings the first time). The dclists_t is
54 // "owned" by the new tree, and the old tree destructs
55 // the old dclists_t without freeing the shared string
56 // storage when it's destroyed after the locked tree swap.
57 // The destruct-only-new-strings destroy is used when
58 // ntree construction fails partway through and has to
59 // be aborted, and the destruct-all-strings form is
60 // used on true shutdown of the whole gdmap (only debug
61 // mode for the real plugin).
62
63 struct _dclists {
64 unsigned count; // count of unique result lists
65 unsigned old_count; // count from object we cloned from
66 uint8_t** list; // strings of dc numbers
67 const dcinfo_t* info; // dclists_t doesn't own "info", just uses it for reference a lot
68 };
69
dclists_new(const dcinfo_t * info)70 dclists_t* dclists_new(const dcinfo_t* info) {
71 const unsigned num_dcs = dcinfo_get_count(info);
72 uint8_t* deflist = xmalloc(num_dcs + 1);
73 for(unsigned i = 0; i < num_dcs; i++)
74 deflist[i] = i + 1;
75 deflist[num_dcs] = 0;
76
77 dclists_t* newdcl = xmalloc(sizeof(dclists_t));
78 newdcl->count = 1;
79 newdcl->old_count = 0;
80 newdcl->list = xmalloc(sizeof(uint8_t*));
81 newdcl->list[0] = deflist;
82 newdcl->info = info;
83
84 return newdcl;
85 }
86
dclists_clone(const dclists_t * old)87 dclists_t* dclists_clone(const dclists_t* old) {
88 dclists_t* dcl_clone = xmalloc(sizeof(dclists_t));
89 dcl_clone->info = old->info;
90 dcl_clone->count = old->count;
91 dcl_clone->old_count = old->count;
92 dcl_clone->list = xmalloc(dcl_clone->count * sizeof(uint8_t*));
93 memcpy(dcl_clone->list, old->list, dcl_clone->count * sizeof(uint8_t*));
94 return dcl_clone;
95 }
96
dclists_get_count(const dclists_t * lists)97 unsigned dclists_get_count(const dclists_t* lists) {
98 dmn_assert(lists->count <= (DCLIST_MAX + 1U));
99 return lists->count;
100 }
101
dclists_get_list(const dclists_t * lists,const uint32_t idx)102 const uint8_t* dclists_get_list(const dclists_t* lists, const uint32_t idx) {
103 dmn_assert(idx < lists->count);
104 dmn_assert(idx <= DCLIST_MAX);
105 return lists->list[idx];
106 }
107
108 // Locates an existing dclist that matches newlist and returns its index, or if no match
109 // it copies newlist to the storage area and returns the new index.
110 // If someone complains about load-time performance with large datecenter sets, this func
111 // will probably be a profiling hotspot. It could use a hashtable rather than linear
112 // search for comparisons, and it could realloc the list by doubling instead of 1-at-a-time.
113 // Not terribly worried about this unless someone complains first.
114 F_NONNULL
dclists_find_or_add_raw(dclists_t * lists,const uint8_t * newlist,const char * map_name)115 static uint32_t dclists_find_or_add_raw(dclists_t* lists, const uint8_t* newlist, const char* map_name) {
116 for(uint32_t i = 0; i < lists->count; i++)
117 if(!strcmp((const char*)newlist, (const char*)(lists->list[i])))
118 return i;
119
120 if(lists->count > DCLIST_MAX)
121 log_fatal("plugin_geoip: map '%s': too many unique dclists (>%u)", map_name, lists->count);
122
123 const uint32_t newidx = lists->count;
124 lists->list = xrealloc(lists->list, (++lists->count) * sizeof(uint8_t*));
125 lists->list[newidx] = (uint8_t*)strdup((const char*)newlist);
126
127 dmn_assert(newidx <= DCLIST_MAX);
128 return newidx;
129 }
130
131 // replace the first (default) dclist...
dclists_replace_list0(dclists_t * lists,uint8_t * newlist)132 void dclists_replace_list0(dclists_t* lists, uint8_t* newlist) {
133 free(lists->list[0]);
134 lists->list[0] = newlist;
135 }
136
137 // We should probably check for dupes in these map dclists, but really the fallout
138 // is just some redundant lookup work if the user screws that up.
dclists_xlate_vscf(dclists_t * lists,vscf_data_t * vscf_list,const char * map_name,uint8_t * newlist,const bool allow_auto)139 bool dclists_xlate_vscf(dclists_t* lists, vscf_data_t* vscf_list, const char* map_name, uint8_t* newlist, const bool allow_auto) {
140 const unsigned count = vscf_array_get_len(vscf_list);
141
142 for(unsigned i = 0; i < count; i++) {
143 vscf_data_t* dcname_cfg = vscf_array_get_data(vscf_list, i);
144 if(!dcname_cfg || !vscf_is_simple(dcname_cfg))
145 log_fatal("plugin_geoip: map '%s': datacenter lists must be an array of one or more datacenter name strings", map_name);
146 const char* dcname = vscf_simple_get_data(dcname_cfg);
147 if(count == 1 && allow_auto && !strcmp(dcname, "auto"))
148 return true;
149 const unsigned idx = dcinfo_name2num(lists->info, dcname);
150 if(!idx)
151 log_fatal("plugin_geoip: map '%s': datacenter name '%s' invalid ...", map_name, dcname);
152 newlist[i] = idx;
153 }
154 newlist[count] = 0;
155
156 return false;
157 }
158
dclists_find_or_add_vscf(dclists_t * lists,vscf_data_t * vscf_list,const char * map_name,const bool allow_auto)159 uint32_t dclists_find_or_add_vscf(dclists_t* lists, vscf_data_t* vscf_list, const char* map_name, const bool allow_auto) {
160 uint8_t newlist[256];
161 bool is_auto = dclists_xlate_vscf(lists,vscf_list,map_name,newlist,allow_auto);
162 if(is_auto) {
163 dmn_assert(allow_auto);
164 return DCLIST_AUTO;
165 }
166 return dclists_find_or_add_raw(lists, newlist, map_name);
167 }
168
169 // Geographic distance between two lat/long points.
170 // Because we only care about rough distance comparison rather than
171 // the precise values themselves, input is specified in radians
172 // and output in units of the earth's diameter.
173 F_CONST
haversine(double lat1,double lon1,double lat2,double lon2)174 static double haversine(double lat1, double lon1, double lat2, double lon2) {
175 double a = pow(sin((lat2 - lat1) * 0.5), 2.0)
176 + cos(lat1) * cos(lat2) * pow(sin((lon2 - lon1) * 0.5), 2.0);
177 return atan2(sqrt(a), sqrt(1.0 - a));
178 }
179
dclists_city_auto_map(dclists_t * lists,const char * map_name,const double lat,const double lon)180 uint32_t dclists_city_auto_map(dclists_t* lists, const char* map_name, const double lat, const double lon) {
181 const double lat_rad = lat * DEG2RAD;
182 const double lon_rad = lon * DEG2RAD;
183
184 // Copy the default datacenter list to local storage for sorting
185 const unsigned num_dcs = dcinfo_get_count(lists->info);
186 const unsigned store_len = num_dcs + 1;
187 uint8_t sortlist[store_len];
188 memcpy(sortlist, lists->list[0], store_len);
189
190 // calculate the target's distance from each datacenter.
191 // note the first element of 'dists' is unused, and
192 // storage is offset by one. This is so that the actual
193 // 1-based dcnums in 'sortlist' can be used as direct
194 // indices into 'dists'
195 double dists[store_len];
196 for(unsigned i = 0; i < num_dcs; i++) {
197 const double* coords = dcinfo_get_coords(lists->info, i);
198 if (!isnan(coords[0]))
199 dists[i + 1] = haversine(lat_rad, lon_rad, coords[0], coords[1]);
200 else
201 dists[i + 1] = (double)+INFINITY;
202 }
203
204 // Given the relatively small num_dcs of most configs,
205 // this simple insertion sort is probably reasonably quick
206 for(unsigned i = 1; i < num_dcs; i++) {
207 unsigned temp = sortlist[i];
208 int j = (int)i - 1;
209 while(j >= 0 && (dists[temp] < dists[sortlist[j]])) {
210 sortlist[j + 1] = sortlist[j];
211 j--;
212 }
213 sortlist[j + 1] = temp;
214 }
215
216 // Cap the list at the auto_limit
217 sortlist[dcinfo_get_limit(lists->info)] = 0;
218
219 return dclists_find_or_add_raw(lists, sortlist, map_name);
220 }
221
dclists_destroy(dclists_t * lists,dclists_destroy_depth_t depth)222 void dclists_destroy(dclists_t* lists, dclists_destroy_depth_t depth) {
223 switch(depth) {
224 case KILL_ALL_LISTS:
225 for(unsigned i = 0; i < lists->count; i++)
226 free(lists->list[i]);
227 break;
228 case KILL_NEW_LISTS:
229 for(unsigned i = lists->old_count; i < lists->count; i++)
230 free(lists->list[i]);
231 break;
232 case KILL_NO_LISTS:
233 default:
234 break;
235 }
236 free(lists->list);
237 free(lists);
238 }
239