rt_data.c @ 717:571b3abaa5df

Last change on this file since 717:571b3abaa5df was 717:571b3abaa5df, checked in by Sebastien Decugis <sdecugis@nict.go.jp>, 11 years ago
Support for Diameter Redirects through rt_redirect.fdx extension (EXPERIMENTAL)
File size: 10.4 KB

Line
1	/*********************************************************************************************************
2	* Software License Agreement (BSD License) *
3	* Author: Sebastien Decugis <sdecugis@nict.go.jp> *
4	* *
5	* Copyright (c) 2011, 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 */
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 */
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 */
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. */
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 */
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
163	int cmp = fd_os_almostcasecmp(id, idsz, c->diamid, c->diamidlen);
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 (cmp > 0)
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*/
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)
188	{
189	struct fd_list * li;
190	int match = 0;
191
192	TRACE_ENTRY("%p %p %zd %p %zd %u", rtd, sentto, senttolen, origin, originsz, rcode);
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	/* Done! */
242	return 0;
243	}
244
245	/* Extract the list of valid candidates, and initialize their scores */
246	void fd_rtd_candidate_extract(struct rt_data * rtd, struct fd_list ** candidates, int ini_score)
247	{
248	struct fd_list * li;
249
250	TRACE_ENTRY("%p %p", rtd, candidates);
251	CHECK_PARAMS_DO( candidates, return );
252	CHECK_PARAMS_DO( rtd, { *candidates = NULL; return; } );
253
254	*candidates = &rtd->candidates;
255
256	/* Reset all scores to INITIAL score */
257	for (li = rtd->candidates.next; li != &rtd->candidates; li = li->next) {
258	struct rtd_candidate * c = (struct rtd_candidate *) li;
259	c->score = ini_score;
260	}
261
262	rtd->extracted = 1;
263	return;
264	}
265
266	/* Reorder the list of peers. If several peer have the same highest score, they are randomized. */
267	int fd_rtd_candidate_reorder(struct fd_list * candidates)
268	{
269	struct fd_list unordered = FD_LIST_INITIALIZER(unordered), *li;
270	struct fd_list highest = FD_LIST_INITIALIZER(highest);
271	int hs = -1;
272
273	TRACE_ENTRY("%p", candidates);
274	CHECK_PARAMS( candidates );
275
276	/* First, move all items from candidates to the undordered list */
277	fd_list_move_end(&unordered, candidates);
278
279	/* Now extract each element from unordered and add it back to list ordered by score */
280	while (!FD_IS_LIST_EMPTY(&unordered)) {
281	struct rtd_candidate * c = (struct rtd_candidate *) unordered.next;
282
283	fd_list_unlink(&c->chain);
284
285	/* If this candidate has a higher score than the previous ones */
286	if (c->score > hs) {
287	/* Then we move the previous high score items at end of the list */
288	fd_list_move_end(candidates, &highest);
289
290	/* And the new high score is set */
291	hs = c->score;
292	}
293
294	/* If this candidate equals the higher score, add it into highest list at a random place */
295	if (c->score == hs) {
296	if (rand() & 1) {
297	fd_list_insert_after(&highest, &c->chain);
298	} else {
299	fd_list_insert_before(&highest, &c->chain);
300	}
301	/* Otherwise, insert at normal place in the list */
302	} else {
303	/* Find the position in ordered candidates list */
304	for (li = candidates->next; li != candidates; li = li->next) {
305	struct rtd_candidate * cnext = (struct rtd_candidate *) li;
306	if (cnext->score >= c->score)
307	break;
308	}
309
310	/* Add the element there */
311	fd_list_insert_before(li, &c->chain);
312	}
313	}
314
315	/* Now simply move back all the "highest" candidates at the end of the list */
316	fd_list_move_end(candidates, &highest);
317
318	return 0;
319	}
320

Note: See TracBrowser for help on using the repository browser.

Navigation

source: freeDiameter/libfdproto/rt_data.c @ 717:571b3abaa5df

Download in other formats: