1 /*
2 *
3 * Copyright (c) 2003 The Regents of the University of California. All
4 * rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * - Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * - Neither the name of the University nor the names of its
14 * contributors may be used to endorse or promote products derived
15 * from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS''
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
19 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
20 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
24 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
25 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 *
29 */
30
31
32 #include "common.h"
33 #include "gls_i.h"
34 #include "hash.h"
35 #include "dijkstra.h"
36
37 extern node_id_t my_node_id;
38 extern loc_t my_loc;
39
40 #define MY_LOG_LEVEL LOG_DEBUG(4)
41
42
43 /***** Hash Table Walk to find node closest to destination location ****/
44
45 typedef struct closest_node {
46 struct nodeconf *min_node;
47 geo_t dst_geo;
48 } closest_node_t;
49
50
51 static
52 void get_nodeid_closest_to_loc (gpointer key, gpointer value, gpointer user_data) {
53 /* Get the input arguments */
54 closest_node_t *args = (closest_node_t *)user_data;
55 /* get the node config of the current min */
56 struct nodeconf *min_node;
57 /* node configuration of the node we're interested in */
58 struct nodeconf *cur_node = (struct nodeconf *)value;
59 /* current min distance */
60 double dist_min;
61 /* distance to destination location from current node */
62 double dist_cur;
63
64 if (args->min_node == NULL) {
65 min_node = cur_node;
66 } else {
67 /* get current min distance */
68 dist_min = EUCLIDEAN_DIST(args->dst_geo, min_node->geo);
69 /* get distance to destination location from current node */
70 dist_cur = EUCLIDEAN_DIST(args->dst_geo, cur_node->geo);
71
72 elog (LOG_DEBUG_0, "CurNode:%d:%f,%f MinNode:%d:%f,%f",
73 cur_node->id, loc_expand(cur_node->geo.x), loc_expand(cur_node->geo.y),
74 min_node->id, loc_expand(min_node->geo.x), loc_expand(min_node->geo.y));
75
76 /* set min either if the distance is lower or if it is equal and
77 * node_id is lower. The latter case breaks a distance tie */
78 if ((dist_cur < dist_min) ||
79 (dist_cur == dist_min && cur_node->id < min_node->id)) {
80 min_node = cur_node;
81 }
82 }
83
84 args->min_node = min_node;
85 }
86
87
88 /* Lookup the id of next hop closest to destination (x,y).
89 * The lookup progresses in two parts: first the node closest to
90 * x,y is located, and then the shortest route to the node is
91 * determined. The next hop is selected as the next hop on this
92 * shortest path.
93 *
94 * NOTE: If different nodes dont have a consistent view of the link
95 * state, the routing will be to different nodes given the same
96 * dst loc i.e. routing inconsistencies are possible.
97 */
98 int
99 get_nexthop_to_dest_loc(gls_addr_t *in, gls_addr_t *out,
100 gboolean *result, struct routedev_info *tables)
101 {
102 uint32_t dest_nodeid; /* nodeid of the destination node */
103 struct nodeconf *req_cfg = NULL;
104 struct routedev_nodeinfo *route = NULL;
105 closest_node_t closest_node = {
106 min_node: NULL,
107 dst_geo: {
108 x: 0,
109 y: 0,
110 },
111 };
112
113 assert(in); assert(out); assert(result); assert(tables);
114
115 /* First, find a node id of the destination node
116 * for the specified lookup.
117 * WARNING: Only type ADDR_GEO is currently supported.
118 */
119 switch(in->type)
120 {
121 case ADDR_GEO:
122
123 /* Find the location of the node closest to the given destination loc
124 * Use this location for rest of lookup */
125 closest_node.min_node = NULL;
126 closest_node.dst_geo = in->addr.geo;
127
128 elog (MY_LOG_LEVEL, "Looking up closest to %f,%f",
129 loc_expand(in->addr.geo.x),loc_expand(in->addr.geo.y));
130
131 g_hash_table_foreach(tables->geo,
132 get_nodeid_closest_to_loc, (gpointer)&closest_node);
133
134 elog (MY_LOG_LEVEL, "After Lookup: Closest Node:%d:%2.2f,%2.2f",
135 closest_node.min_node->id,
136 loc_expand(closest_node.min_node->geo.x),
137 loc_expand(closest_node.min_node->geo.y));
138
139
140 /* ugh what a name */
141 /* get the configuration of node closest to destination location */
142 req_cfg = closest_node.min_node;
143
144 // req_cfg = g_hash_table_lookup(tables->geo, &(data->in.gls_geo));
145
146 if (req_cfg) /* found a match in our hash table */
147 {
148 dest_nodeid = req_cfg->id;
149 }
150 else /* did not find a match */
151 {
152 *result = FALSE;
153 return 0;
154 }
155
156 break;
157
158 case ADDR_NODEID:
159 dest_nodeid = in->addr.nodeid;
160 break;
161
162 default:
163 printf("Unrecognized type of address supplied %d\n", in->type);
164 return (-1);
165
166 /* NOTREACHED */
167 break;
168 }
169
170 /* Are we the closest. If so, fill "out" and return */
171 if (dest_nodeid == my_node_id) {
172 out->addr.nodeid = my_node_id;
173 *result = TRUE;
174 return 0;
175 }
176
177 elog(MY_LOG_LEVEL, "PRINTING NBR TABLE: %d",my_node_id);
178
179 /* print the entire neighbor table for debugging */
180 print_global_table(tables->nodeid);
181
182 print_routing_table(tables->rtable);
183
184 fflush(stdout);
185
186 /* lookup a routing table entry associated with the destination nodeid */
187 route = g_hash_table_lookup(tables->rtable, &(dest_nodeid));
188
189 if (route == NULL)
190 elog(MY_LOG_LEVEL, "route is NULL!!!! How is this possible??");
191
192 if (route->next_hop != INFINITY)
193 elog(MY_LOG_LEVEL, "DstId:%lu next hop is %lu",route->id, route->next_hop);
194
195 /* Look at the out->type and return either nodeid or geo-address
196 * of next hop. WARNING: Only ADDR_NODEID is currently compatible with
197 * rest of gls.
198 */
199 if (route)
200 {
201 if (INFINITY == route->next_hop)
202 {
203 /* we know that there is no path to the destination node */
204 *result = FALSE;
205 }
206 else if (ADDR_NODEID == out->type)
207 {
208 /* since we're asked to return information as a nodeid, we don't
209 * need to do any further lookups */
210 out->addr.nodeid = route->next_hop;
211 *result = TRUE;
212 elog(MY_LOG_LEVEL, "returning next hop is %lu",out->addr.nodeid);
213 }
214 else
215 {
216 struct nodeconf *cfg = g_hash_table_lookup(tables->nodeid,
217 &(route->next_hop));
218 if (cfg)
219 {
220 /* it is possible that GEO/UDP information is not going to be
221 * present in the table. The only way for us to know that is to
222 * check the udp/geo tables for information. Since the nodeid
223 * table points to the node, and the node config. structure
224 * contains both udp and geo information (not pointers). This
225 * means, that there is always something stored in the
226 * structure, except that sometimes that information is plain
227 * wrong */
228 if (ADDR_GEO == out->type)
229 {
230 if ((g_hash_table_lookup(tables->geo, &(cfg->geo))))
231 {
232 out->addr.geo = cfg->geo;
233 *result = TRUE;
234 }
235 else
236 {
237 *result = FALSE;
238 }
239 }
240 else
241 {
242 printf("Unrecognized output type of address requested %d\n"
243 "when looking up next hop for %lu\n",
244 out->type, (ulong)route->next_hop);
245 return (-1);
246 }
247 }
248 else
249 {
250 /* we'd fall in here if the node is present on the neighborlist,
251 * but no information about the node is available */
252 *result = FALSE;
253 }
254 }
255 }
256 else /* did not find a match: we dont know what the next hop is */
257 {
258 *result = FALSE;
259 }
260
261 return 0;
262 }
263
264 /* Called when a local client tries to write a packet to our GLS
265 * device file. Check the packet is valid before admitting it to the
266 * queue. */
267 static int gls_enqueue(pd_context_t *pd, const void *packet, int packetlen)
268 {
269 gls_state_t *gls_state = (gls_state_t *) pd_data(pd);
270
271 if (packetlen < sizeof(link_pkt_t)) {
272 elog(LOG_ERR, "short packet (%d bytes) written to %s",
273 packetlen, gls_dev_name(gls_state));
274 return -EINVAL;
275 }
276
277 elog(MY_LOG_LEVEL, "got route request");
278
279 /* XXX TODO FIXME - do some mtu check based on MTU of interfaces underneath */
280
281 /* funny...MTU shd be defined at the link layer not here */
282 /* if (packetlen > (GLS_MTU - sizeof(link_pkt_t))) { */
283 /* elog(LOG_ERR, "large packet (%d bytes) over MTU to %s", */
284 /* packetlen, gls_dev_name(u)); */
285 /* return -EMSGSIZE; */
286 /* } */
287
288 return 0;
289 }
290
291 static int gls_send(pd_context_t *pd, const void *packet,
292 int packetlen, int loop_needed)
293 {
294 /* get my state */
295 gls_state_t *gls_state = (gls_state_t *)pd_data(pd);
296 /* Get link packet from input packet */
297 link_pkt_t *link_pkt_in = (link_pkt_t *)packet;
298
299 /* declarations for outgoing packet */
300 /* create a new resizable packet buffer (misc_buf.h) */
301 buf_t *pkt_out = buf_new ();
302
303 /* find size of user payload */
304 ssize_t data_len = packetlen - sizeof(link_pkt_t);
305
306 /* Create our *outgoing* link header */
307 link_pkt_t link_hdr = {
308 dst: {
309 id: LINK_BROADCAST,
310 },
311 type: PKT_TYPE_GLS,
312 };
313
314 /* create outgoing gls header */
315 gls_pkt_t gls_hdr = {
316 original_src: {
317 type:ADDR_GEO,
318 addr: {
319 geo: {
320 x: loc_trunc(my_loc.x), /* ASSUMPTION: I am the src of the packet */
321 y: loc_trunc(my_loc.y),
322 },
323 },
324 },
325 final_dst: {
326 type:ADDR_GEO,
327 addr: {
328 geo: {
329 x: loc_trunc(link_pkt_in->dst.loc.x),
330 y: loc_trunc(link_pkt_in->dst.loc.y),
331 },
332 },
333 },
334 inner_type: link_pkt_in->type, /* save the application-type */
335 };
336
337
338 /* need it for the get_nexthop fn..it shd be returned to user??
339 * Can we return to user?? Shd this be done within enqueue??
340 */
341 gboolean lookup_result=FALSE;
342
343 /* address/location to be looked up */
344 gls_addr_t gls_addr_in = {
345 type: ADDR_GEO,
346 addr: {
347 geo: {
348 x: loc_trunc(link_pkt_in->dst.loc.x),
349 y: loc_trunc(link_pkt_in->dst.loc.y),
350 },
351 },
352 };
353
354 /* address after lookup */
355 gls_addr_t gls_addr_out = {
356 type:ADDR_NODEID,
357 };
358
359
360 elog(MY_LOG_LEVEL, "Route to Destination: %f,%f",
361 link_pkt_in->dst.loc.x, link_pkt_in->dst.loc.y);
362
363
364 /* We want nodeid output, so set output type to nodeid */
365 // gls_addr_out.type = ADDR_NODEID;
366
367 /* Lookup next hop to dst */
368 get_nexthop_to_dest_loc(&gls_addr_in, &gls_addr_out,
369 &lookup_result, gls_state->info);
370
371 elog(LOG_DEBUG_0, "Next hop: %lu",gls_addr_out.addr.nodeid);
372
373 /* drop pkt if no route to dst can be found */
374 /* XXX: Remember to free packet */
375 if (!lookup_result) goto done;
376
377 /* Create the gls-specific header */
378 /* GLS header does not have fields to prevent looping, since this
379 should not happen in a link-state protocol.
380 struct gls_data supports multiple input types: UDP, GEO, ID. Only
381 geo-lookup is currently supported */
382
383 /* set default ttl if user didn't set it */
384 /* if (gls_hdr.ttl == 0) */
385 /* gls_hdr.ttl =GLS_DEFAULT_MAX_TTL; */
386
387 /* For debugging. Spit out packet contents */
388 elog(MY_LOG_LEVEL, "Printing Packet: Datalen:%d gls_hdr:%d link_hdr:%d",
389 data_len,sizeof(gls_hdr),sizeof(link_hdr));
390 elog_raw(MY_LOG_LEVEL, link_pkt_in->data, data_len);
391
392 /*
393 * Construct the packet: outer link header, inner gls header, user
394 * payload
395 */
396 bufcpy(pkt_out, &link_hdr, sizeof(link_hdr));
397 bufcpy(pkt_out, &gls_hdr, sizeof(gls_hdr));
398 bufcpy(pkt_out, link_pkt_in->data, data_len);
399
400 elog(MY_LOG_LEVEL, "pkt_out->len - sizeof(link_pkt_t):%d: sizeof(gls_addr_t):%d",
401 pkt_out->len - sizeof(link_pkt_t), sizeof(gls_addr_t));
402 elog_raw(MY_LOG_LEVEL, ((link_pkt_t *)(pkt_out->buf))->data,
403 pkt_out->len - sizeof(link_pkt_t));
404
405
406 // elog_raw(MY_LOG_LEVEL, (link_pkt_t *)(pkt_out->buf),
407 // pkt_out->len);
408
409 /* forward packet to next_hop_nodeid.
410 * account for increased data length due to addition of gls_hdr
411 */
412 gls_forward(gls_state, (link_pkt_t *)pkt_out->buf,
413 pkt_out->len - sizeof(link_pkt_t), (node_id_t)gls_addr_out.addr.nodeid);
414
415 done:
416 buf_free(pkt_out);
417 return 0;
418 }
419
420
421 /*
422 * Register the gls device that other processes open to send gls
423 * packets
424 */
425 void gls_register_packetdev(gls_state_t *gls_state)
426 {
427 /* set options for the packetdev */
428 packet_dev_opts_t pd_opts = {
429 send: gls_send,
430 enqueue: gls_enqueue,
431 filter: link_standard_filter,
432 device: {
433 device_info: (void *) gls_state,
434 }
435 };
436
437 /* and options to tell it what we're trying to register */
438 memset(&(gls_state->pd_link_opts), 0, sizeof(link_opts_t));
439 gls_state->pd_link_opts.dev_type = LINK_DEV_GLS;
440
441 /* try to register the packetdev as a link interface */
442 if (link_register(&pd_opts, &gls_state->pd_context, &gls_state->pd_link_opts) < 0) {
443 elog(LOG_CRIT, "can't create packetdev %s: %m", pd_opts.device.devname);
444 exit(1);
445 }
446
447 elog(LOG_INFO, "created upper interface, %s", pd_opts.device.devname);
448 }
449
450
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.