1 /*********************************************************************************************************
2 * Software License Agreement (BSD License) *
3 * Author: Sebastien Decugis <sdecugis@freediameter.net> *
4 * *
5 * Copyright (c) 2013, WIDE Project and NICT *
6 * All rights reserved. *
7 * *
8 * Redistribution and use of this software in source and binary forms, with or without modification, are *
9 * permitted provided that the following conditions are met: *
10 * *
11 * * Redistributions of source code must retain the above *
12 * copyright notice, this list of conditions and the *
13 * following disclaimer. *
14 * *
15 * * Redistributions in binary form must reproduce the above *
16 * copyright notice, this list of conditions and the *
17 * following disclaimer in the documentation and/or other *
18 * materials provided with the distribution. *
19 * *
20 * * Neither the name of the WIDE Project or NICT nor the *
21 * names of its contributors may be used to endorse or *
22 * promote products derived from this software without *
23 * specific prior written permission of WIDE Project and *
24 * NICT. *
25 * *
26 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED *
27 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
28 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR *
29 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT *
30 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS *
31 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR *
32 * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF *
33 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
34 *********************************************************************************************************/
35
36 /* Routing module helpers.
37 *
38 * This file provides support for the rt_data structure manipulation.
39 */
40
41 #include "fdproto-internal.h"
42
43 /* Structure that contains the routing data for a message */
44 struct rt_data {
45 int extracted; /* if 0, candidates is ordered by diamid, otherwise the order is unspecified. This also counts the number of times the message was (re-)sent, as a side effect */
46 struct fd_list candidates; /* All the candidates. Items are struct rtd_candidate. */
47 struct fd_list errors; /* All errors received from other peers for this message */
48 };
49
50 /* Items of the errors list */
51 struct rtd_error {
52 struct fd_list chain; /* link in the list, ordered by nexthop (fd_os_cmp) */
53 DiamId_t nexthop;/* the peer the message was sent to */
54 size_t nexthoplen; /* cached string length */
55 DiamId_t erh; /* the origin of the error */
56 size_t erhlen; /* cached string length */
57 uint32_t code; /* the error code */
58 };
59
60 /* Create a new structure to store routing data */
fd_rtd_init(struct rt_data ** rtd)61 int fd_rtd_init(struct rt_data ** rtd)
62 {
63 struct rt_data *new;
64 TRACE_ENTRY("%p", rtd);
65 CHECK_PARAMS(rtd);
66
67 /* Alloc the structure */
68 CHECK_MALLOC( new = malloc(sizeof(struct rt_data)) );
69 memset(new, 0, sizeof(struct rt_data) );
70 fd_list_init(&new->candidates, new);
71 fd_list_init(&new->errors, new);
72
73 *rtd = new;
74 return 0;
75 }
76
77 /* Destroy the routing data */
fd_rtd_free(struct rt_data ** rtd)78 void fd_rtd_free(struct rt_data ** rtd)
79 {
80 struct rt_data *old;
81
82 TRACE_ENTRY("%p", rtd);
83 CHECK_PARAMS_DO(rtd, return );
84
85 old = *rtd;
86 *rtd = NULL;
87
88 while (!FD_IS_LIST_EMPTY(&old->candidates)) {
89 struct rtd_candidate * c = (struct rtd_candidate *) old->candidates.next;
90
91 fd_list_unlink(&c->chain);
92 free(c->diamid);
93 free(c->realm);
94 free(c);
95 }
96
97 while (!FD_IS_LIST_EMPTY(&old->errors)) {
98 struct rtd_error * c = (struct rtd_error *) old->errors.next;
99
100 fd_list_unlink(&c->chain);
101 free(c->nexthop);
102 free(c->erh);
103 free(c);
104 }
105
106 free(old);
107
108 return;
109 }
110
111 /* Add a peer to the candidates list. The source is our local peer list, so no need to care for the case here. */
fd_rtd_candidate_add(struct rt_data * rtd,DiamId_t peerid,size_t peeridlen,DiamId_t realm,size_t realmlen)112 int fd_rtd_candidate_add(struct rt_data * rtd, DiamId_t peerid, size_t peeridlen, DiamId_t realm, size_t realmlen)
113 {
114 struct fd_list * prev;
115 struct rtd_candidate * new;
116
117 TRACE_ENTRY("%p %p %zd %p %zd", rtd, peerid, peeridlen, realm, realmlen);
118 CHECK_PARAMS(rtd && peerid && peeridlen);
119
120 /* Since the peers are ordered when they are added (fd_g_activ_peers) we search for the position from the end -- this should be efficient */
121 for (prev = rtd->candidates.prev; prev != &rtd->candidates; prev = prev->prev) {
122 struct rtd_candidate * cp = (struct rtd_candidate *) prev;
123 int cmp = fd_os_cmp(peerid, peeridlen, cp->diamid, cp->diamidlen);
124 if (cmp > 0)
125 break;
126 if (cmp == 0)
127 /* The candidate is already in the list */
128 return 0;
129 }
130
131 /* Create the new entry */
132 CHECK_MALLOC( new = malloc(sizeof(struct rtd_candidate)) );
133 memset(new, 0, sizeof(struct rtd_candidate) );
134 fd_list_init(&new->chain, new);
135 CHECK_MALLOC( new->diamid = os0dup(peerid, peeridlen) )
136 new->diamidlen = peeridlen;
137 if (realm) {
138 CHECK_MALLOC( new->realm = os0dup(realm, realmlen) )
139 new->realmlen = realmlen;
140 }
141
142 /* insert in the list at the correct position */
143 fd_list_insert_after(prev, &new->chain);
144
145 return 0;
146 }
147
148 /* Remove a peer from the candidates (if it is found). Case insensitive search since the names are received from other peers */
fd_rtd_candidate_del(struct rt_data * rtd,uint8_t * id,size_t idsz)149 void fd_rtd_candidate_del(struct rt_data * rtd, uint8_t * id, size_t idsz)
150 {
151 struct fd_list * li;
152
153 TRACE_ENTRY("%p %p %zd", rtd, id, idsz);
154 CHECK_PARAMS_DO( rtd && id && idsz, return );
155
156 if (!fd_os_is_valid_DiameterIdentity(id, idsz))
157 /* it cannot be in the list */
158 return;
159
160 for (li = rtd->candidates.next; li != &rtd->candidates; li = li->next) {
161 struct rtd_candidate * c = (struct rtd_candidate *) li;
162 int cont;
163 int cmp = fd_os_almostcasesrch(id, idsz, c->diamid, c->diamidlen, &cont);
164
165 if (!cmp) {
166 /* Found it! Remove it */
167 fd_list_unlink(&c->chain);
168 free(c->diamid);
169 free(c->realm);
170 free(c);
171 break;
172 }
173
174 if (cont)
175 continue;
176
177 /* The list is guaranteed to be ordered only if not extracted */
178 if (! rtd->extracted)
179 break;
180 }
181
182 return;
183 }
184
185 /* If a peer returned a protocol error for this message, save it so that we don't try to send it there again.
186 Case insensitive search since the names are received from other peers*/
fd_rtd_error_add(struct rt_data * rtd,DiamId_t sentto,size_t senttolen,uint8_t * origin,size_t originsz,uint32_t rcode,struct fd_list ** candidates,int * sendingattemtps)187 int fd_rtd_error_add(struct rt_data * rtd, DiamId_t sentto, size_t senttolen, uint8_t * origin, size_t originsz, uint32_t rcode, struct fd_list ** candidates, int * sendingattemtps)
188 {
189 struct fd_list * li;
190 int match = 0;
191
192 TRACE_ENTRY("%p %p %zd %p %zd %u %p %p", rtd, sentto, senttolen, origin, originsz, rcode, candidates, sendingattemtps);
193 CHECK_PARAMS( rtd && sentto && senttolen ); /* origin may be NULL */
194
195 /* First add the new error entry */
196 for (li = rtd->errors.next; li != &rtd->errors; li = li->next) {
197 struct rtd_error * e = (struct rtd_error *) li;
198 int cmp = fd_os_cmp(sentto, senttolen, e->nexthop, e->nexthoplen);
199 if (cmp > 0)
200 continue;
201 if (!cmp)
202 match = 1;
203 break;
204 }
205
206 /* If we already had this entry, we should not have sent the message again to this peer... anyway, let's close our eyes. */
207 /* in the normal case, we save the error */
208 if (!match) {
209 /* Add a new entry in the error list */
210 struct rtd_error * new;
211 CHECK_MALLOC( new = malloc(sizeof(struct rtd_error)) );
212 memset(new, 0, sizeof(struct rtd_error));
213 fd_list_init(&new->chain, NULL);
214
215 CHECK_MALLOC(new->nexthop = os0dup(sentto, senttolen));
216 new->nexthoplen = senttolen;
217
218 if (origin) {
219 if (!originsz) {
220 originsz=strlen((char *)origin);
221 } else {
222 if (!fd_os_is_valid_DiameterIdentity(origin, originsz)){
223 TRACE_DEBUG(FULL, "Received error %d from peer with invalid Origin-Host AVP, not saved", rcode);
224 origin = NULL;
225 goto after_origin;
226 }
227 }
228 CHECK_MALLOC( new->erh = (DiamId_t)os0dup(origin, originsz) );
229 new->erhlen = originsz;
230 }
231 after_origin:
232 new->code = rcode;
233 fd_list_insert_before(li, &new->chain);
234 }
235
236 /* Finally, remove this (these) peers from the candidate list */
237 fd_rtd_candidate_del(rtd, (os0_t)sentto, senttolen);
238 if (origin)
239 fd_rtd_candidate_del(rtd, origin, originsz);
240
241 if (candidates)
242 *candidates = &rtd->candidates;
243
244 if (sendingattemtps)
245 *sendingattemtps = rtd->extracted;
246
247 /* Done! */
248 return 0;
249 }
250
251 /* Only retrieve the number of times this message has been processed by the routing-out mechanism (i.e. number of times it was failed over) */
fd_rtd_get_nb_attempts(struct rt_data * rtd,int * sendingattemtps)252 int fd_rtd_get_nb_attempts(struct rt_data * rtd, int * sendingattemtps)
253 {
254 TRACE_ENTRY("%p %p", rtd, sendingattemtps);
255 CHECK_PARAMS( rtd && sendingattemtps );
256
257 *sendingattemtps = rtd->extracted;
258
259 /* Done! */
260 return 0;
261 }
262
263 /* Extract the list of valid candidates, and initialize their scores */
fd_rtd_candidate_extract(struct rt_data * rtd,struct fd_list ** candidates,int ini_score)264 void fd_rtd_candidate_extract(struct rt_data * rtd, struct fd_list ** candidates, int ini_score)
265 {
266 struct fd_list * li;
267
268 TRACE_ENTRY("%p %p", rtd, candidates);
269 CHECK_PARAMS_DO( candidates, return );
270 CHECK_PARAMS_DO( rtd, { *candidates = NULL; return; } );
271
272 *candidates = &rtd->candidates;
273
274 /* Reset all scores to INITIAL score */
275 for (li = rtd->candidates.next; li != &rtd->candidates; li = li->next) {
276 struct rtd_candidate * c = (struct rtd_candidate *) li;
277 c->score = ini_score;
278 }
279
280 rtd->extracted += 1;
281 return;
282 }
283
284 /* Reorder the list of peers. If several peer have the same highest score, they are randomized. */
fd_rtd_candidate_reorder(struct fd_list * candidates)285 int fd_rtd_candidate_reorder(struct fd_list * candidates)
286 {
287 struct fd_list unordered = FD_LIST_INITIALIZER(unordered), *li;
288 struct fd_list highest = FD_LIST_INITIALIZER(highest);
289 int hs = -1;
290
291 TRACE_ENTRY("%p", candidates);
292 CHECK_PARAMS( candidates );
293
294 /* First, move all items from candidates to the undordered list */
295 fd_list_move_end(&unordered, candidates);
296
297 /* Now extract each element from unordered and add it back to list ordered by score */
298 while (!FD_IS_LIST_EMPTY(&unordered)) {
299 struct rtd_candidate * c = (struct rtd_candidate *) unordered.next;
300
301 fd_list_unlink(&c->chain);
302
303 /* If this candidate has a higher score than the previous ones */
304 if (c->score > hs) {
305 /* Then we move the previous high score items at end of the list */
306 fd_list_move_end(candidates, &highest);
307
308 /* And the new high score is set */
309 hs = c->score;
310 }
311
312 /* If this candidate equals the higher score, add it into highest list at a random place */
313 if (c->score == hs) {
314 if (rand() & 1) {
315 fd_list_insert_after(&highest, &c->chain);
316 } else {
317 fd_list_insert_before(&highest, &c->chain);
318 }
319 /* Otherwise, insert at normal place in the list */
320 } else {
321 /* Find the position in ordered candidates list */
322 for (li = candidates->next; li != candidates; li = li->next) {
323 struct rtd_candidate * cnext = (struct rtd_candidate *) li;
324 if (cnext->score >= c->score)
325 break;
326 }
327
328 /* Add the element there */
329 fd_list_insert_before(li, &c->chain);
330 }
331 }
332
333 /* Now simply move back all the "highest" candidates at the end of the list */
334 fd_list_move_end(candidates, &highest);
335
336 return 0;
337 }
338
339