Navigation


source: freeDiameter/libfdproto/rt_data.c @ 738:d666051658bd

Last change on this file since 738:d666051658bd was 738:d666051658bd, checked in by Sebastien Decugis <sdecugis@nict.go.jp>, 11 years ago

Fix broken 'almostcasecmp' logic

File size: 10.5 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 */
44struct 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 */
51struct 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 */
61int  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 */
78void 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. */
112int  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 */
149void 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*/
187int  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                }
231after_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 */
246void 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. */
267int  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.