Mercurial > hg > freeDiameter
annotate libfdproto/rt_data.c @ 662:2e94ef0515d7 1.1.0-rc1
Updated copyright information
| author | Sebastien Decugis <sdecugis@nict.go.jp> |
|---|---|
| date | Fri, 14 Jan 2011 16:27:21 +0900 |
| parents | f198d16fa7f4 |
| children | 4ffbc9f1e922 |
| rev | line source |
|---|---|
| 84 | 1 /********************************************************************************************************* |
| 2 * Software License Agreement (BSD License) * | |
| 3 * Author: Sebastien Decugis <sdecugis@nict.go.jp> * | |
| 4 * * | |
|
662
2e94ef0515d7
Updated copyright information
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
658
diff
changeset
|
5 * Copyright (c) 2011, WIDE Project and NICT * |
| 84 | 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 | |
|
658
f198d16fa7f4
Initial commit for 1.1.0:
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
563
diff
changeset
|
41 #include "fdproto-internal.h" |
| 84 | 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 */ | |
| 53 char * nexthop;/* the peer the message was sent to */ | |
| 54 char * erh; /* the origin of the error */ | |
| 55 uint32_t code; /* the error code */ | |
| 56 }; | |
| 57 | |
| 58 /* Create a new structure to store routing data */ | |
| 59 int fd_rtd_init(struct rt_data ** rtd) | |
| 60 { | |
| 61 struct rt_data *new; | |
| 62 TRACE_ENTRY("%p", rtd); | |
| 63 CHECK_PARAMS(rtd); | |
| 64 | |
| 65 /* Alloc the structure */ | |
| 66 CHECK_MALLOC( new = malloc(sizeof(struct rt_data)) ); | |
| 67 memset(new, 0, sizeof(struct rt_data) ); | |
| 68 fd_list_init(&new->candidates, new); | |
| 69 fd_list_init(&new->errors, new); | |
| 70 | |
| 71 *rtd = new; | |
| 72 return 0; | |
| 73 } | |
| 74 | |
| 75 /* Destroy the routing data */ | |
| 76 void fd_rtd_free(struct rt_data ** rtd) | |
| 77 { | |
| 78 struct rt_data *old; | |
| 79 | |
| 80 TRACE_ENTRY("%p", rtd); | |
| 81 CHECK_PARAMS_DO(rtd, return ); | |
| 82 | |
| 83 old = *rtd; | |
| 84 *rtd = NULL; | |
| 85 | |
| 86 while (!FD_IS_LIST_EMPTY(&old->candidates)) { | |
| 87 struct rtd_candidate * c = (struct rtd_candidate *) old->candidates.next; | |
| 88 | |
| 89 fd_list_unlink(&c->chain); | |
| 90 free(c->diamid); | |
|
168
6db078b955e3
Completed rt_default extension
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
166
diff
changeset
|
91 free(c->realm); |
| 84 | 92 free(c); |
| 93 } | |
| 94 | |
| 95 while (!FD_IS_LIST_EMPTY(&old->errors)) { | |
| 96 struct rtd_error * c = (struct rtd_error *) old->errors.next; | |
| 97 | |
| 98 fd_list_unlink(&c->chain); | |
| 99 free(c->nexthop); | |
| 100 free(c->erh); | |
| 101 free(c); | |
| 102 } | |
| 103 | |
| 104 free(old); | |
| 105 | |
| 106 return; | |
| 107 } | |
| 108 | |
| 109 /* Add a peer to the candidates list */ | |
|
168
6db078b955e3
Completed rt_default extension
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
166
diff
changeset
|
110 int fd_rtd_candidate_add(struct rt_data * rtd, char * peerid, char * realm) |
| 84 | 111 { |
| 112 struct fd_list * prev; | |
| 113 struct rtd_candidate * new; | |
| 114 | |
| 115 TRACE_ENTRY("%p %p", rtd, peerid); | |
| 116 CHECK_PARAMS(rtd && peerid); | |
| 117 | |
| 118 /* 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 */ | |
| 119 for (prev = rtd->candidates.prev; prev != &rtd->candidates; prev = prev->prev) { | |
| 120 struct rtd_candidate * cp = (struct rtd_candidate *) prev; | |
| 121 int cmp = strcmp(peerid, cp->diamid); | |
| 122 if (cmp > 0) | |
| 123 break; | |
| 124 if (cmp == 0) | |
| 125 /* The candidate is already in the list */ | |
| 126 return 0; | |
| 127 } | |
| 128 | |
| 129 CHECK_MALLOC( new = malloc(sizeof(struct rtd_candidate)) ); | |
| 130 memset(new, 0, sizeof(struct rtd_candidate) ); | |
| 131 fd_list_init(&new->chain, NULL); | |
| 132 CHECK_MALLOC( new->diamid = strdup(peerid) ); | |
|
168
6db078b955e3
Completed rt_default extension
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
166
diff
changeset
|
133 CHECK_MALLOC( new->realm = strdup(realm) ); |
| 84 | 134 |
| 135 fd_list_insert_after(prev, &new->chain); | |
| 136 | |
| 137 return 0; | |
| 138 } | |
| 139 | |
| 140 /* Remove a peer from the candidates (if it is found) */ | |
| 141 void fd_rtd_candidate_del(struct rt_data * rtd, char * peerid, size_t sz /* if !0, peerid does not need to be \0 terminated */) | |
| 142 { | |
| 143 struct fd_list * li; | |
| 144 | |
| 145 TRACE_ENTRY("%p %p %zd", rtd, peerid, sz); | |
| 146 CHECK_PARAMS_DO( rtd && peerid , return ); | |
| 147 | |
| 148 for (li = rtd->candidates.next; li != &rtd->candidates; li = li->next) { | |
| 149 struct rtd_candidate * c = (struct rtd_candidate *) li; | |
| 150 int cmp; | |
| 151 if (sz) { | |
| 152 cmp = strncmp(peerid, c->diamid, sz); | |
| 153 if (!cmp) { | |
| 154 int len = strlen(c->diamid); | |
| 155 if (sz < len) | |
| 156 cmp = -1; | |
| 157 else if (sz == len) | |
| 158 cmp = 0; | |
| 159 else cmp = 1; | |
| 160 } | |
| 161 } else { | |
| 162 cmp = strcmp(peerid, c->diamid); | |
| 163 } | |
| 164 | |
| 165 if (!cmp) { | |
| 166 /* Found it! Remove it */ | |
| 167 fd_list_unlink(&c->chain); | |
| 168 free(c->diamid); | |
|
168
6db078b955e3
Completed rt_default extension
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
166
diff
changeset
|
169 free(c->realm); |
| 84 | 170 free(c); |
| 171 break; | |
| 172 } | |
| 173 | |
| 174 if (cmp > 0) | |
| 175 continue; | |
| 176 | |
| 177 /* The list is 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 int fd_rtd_error_add(struct rt_data * rtd, char * sentto, uint8_t * origin, size_t originsz, uint32_t rcode) | |
| 187 { | |
| 188 struct fd_list * li; | |
| 189 int match = 0; | |
| 190 | |
| 191 TRACE_ENTRY("%p %p %p %d", rtd, sentto, origin, rcode); | |
| 192 CHECK_PARAMS( rtd && sentto ); /* origin may be NULL */ | |
| 193 | |
| 194 /* First add the new error entry */ | |
| 195 for (li = rtd->errors.next; li != &rtd->errors; li = li->next) { | |
| 196 struct rtd_error * e = (struct rtd_error *) li; | |
| 197 int cmp = strcmp(sentto, e->nexthop); | |
| 198 if (cmp > 0) | |
| 199 continue; | |
| 200 if (!cmp) | |
| 201 match = 1; | |
| 202 break; | |
| 203 } | |
| 204 | |
| 205 /* If we already had this entry, we should not have sent the message again to this peer... anyway... */ | |
| 206 if (!match) { | |
| 207 /* Add a new entry in the error list */ | |
| 208 struct rtd_error * new; | |
| 209 CHECK_MALLOC( new = malloc(sizeof(struct rtd_error)) ); | |
| 210 memset(new, 0, sizeof(struct rtd_error)); | |
| 211 fd_list_init(&new->chain, NULL); | |
| 212 CHECK_MALLOC(new->nexthop = strdup(sentto)); | |
| 213 if (origin) { | |
| 214 CHECK_MALLOC( new->erh = malloc(originsz + 1) ); | |
| 215 memcpy(new->erh, origin, originsz); | |
| 216 new->erh[originsz] = '\0'; | |
| 217 } | |
| 218 new->code = rcode; | |
| 219 fd_list_insert_before(li, &new->chain); | |
| 220 } | |
| 221 | |
| 222 /* Finally, remove this (these) peers from the candidate list */ | |
| 223 fd_rtd_candidate_del(rtd, sentto, 0); | |
| 224 if (origin) | |
|
403
26aafbbc1640
Cleanup all compilation warnings in base code for 32 bit arch
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
258
diff
changeset
|
225 fd_rtd_candidate_del(rtd, (char *)origin, originsz); |
| 84 | 226 |
| 227 /* Done! */ | |
| 228 return 0; | |
| 229 } | |
| 230 | |
|
166
6d166f75e25a
Fix routing list scores initialization
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
124
diff
changeset
|
231 /* Extract the list of valid candidates, and initialize their scores */ |
|
124
cc42d8607114
Completed cleanups of queues when the daemon is stopping
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
84
diff
changeset
|
232 void fd_rtd_candidate_extract(struct rt_data * rtd, struct fd_list ** candidates, int ini_score) |
| 84 | 233 { |
|
166
6d166f75e25a
Fix routing list scores initialization
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
124
diff
changeset
|
234 struct fd_list * li; |
|
6d166f75e25a
Fix routing list scores initialization
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
124
diff
changeset
|
235 |
| 84 | 236 TRACE_ENTRY("%p %p", rtd, candidates); |
| 237 CHECK_PARAMS_DO( candidates, return ); | |
| 238 CHECK_PARAMS_DO( rtd, { *candidates = NULL; return; } ); | |
| 239 | |
| 240 *candidates = &rtd->candidates; | |
| 241 | |
|
166
6d166f75e25a
Fix routing list scores initialization
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
124
diff
changeset
|
242 /* Reset all scores to INITIAL score */ |
|
6d166f75e25a
Fix routing list scores initialization
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
124
diff
changeset
|
243 for (li = rtd->candidates.next; li != &rtd->candidates; li = li->next) { |
|
6d166f75e25a
Fix routing list scores initialization
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
124
diff
changeset
|
244 struct rtd_candidate * c = (struct rtd_candidate *) li; |
|
6d166f75e25a
Fix routing list scores initialization
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
124
diff
changeset
|
245 c->score = ini_score; |
| 84 | 246 } |
| 247 | |
| 248 rtd->extracted = 1; | |
| 249 return; | |
| 250 } | |
| 251 | |
|
563
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
252 /* Reorder the list of peers. If several peer have the same highest score, they are randomized. */ |
| 84 | 253 int fd_rtd_candidate_reorder(struct fd_list * candidates) |
| 254 { | |
| 255 struct fd_list unordered = FD_LIST_INITIALIZER(unordered), *li; | |
|
563
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
256 struct fd_list highest = FD_LIST_INITIALIZER(highest); |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
257 int hs = -1; |
| 84 | 258 |
| 259 TRACE_ENTRY("%p", candidates); | |
| 260 CHECK_PARAMS( candidates ); | |
| 261 | |
| 262 /* First, move all items from candidates to the undordered list */ | |
| 263 fd_list_move_end(&unordered, candidates); | |
| 264 | |
| 265 /* Now extract each element from unordered and add it back to list ordered by score */ | |
| 266 while (!FD_IS_LIST_EMPTY(&unordered)) { | |
| 267 struct rtd_candidate * c = (struct rtd_candidate *) unordered.next; | |
| 268 | |
| 269 fd_list_unlink(&c->chain); | |
| 270 | |
|
563
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
271 /* If this candidate has a higher score than the previous ones */ |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
272 if (c->score > hs) { |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
273 /* Then we move the previous high score items at end of the list */ |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
274 fd_list_move_end(candidates, &highest); |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
275 |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
276 /* And the new high score is this reset */ |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
277 hs = c->score; |
| 84 | 278 } |
| 279 | |
|
563
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
280 /* If this candidate equals the higher score, add it into highest list at a random place */ |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
281 if (c->score == hs) { |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
282 if (rand() & 1) { |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
283 fd_list_insert_after(&highest, &c->chain); |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
284 } else { |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
285 fd_list_insert_before(&highest, &c->chain); |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
286 } |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
287 /* Otherwise, insert at normal place in the list */ |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
288 } else { |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
289 /* Find the position in ordered candidates list */ |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
290 for (li = candidates->next; li != candidates; li = li->next) { |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
291 struct rtd_candidate * cnext = (struct rtd_candidate *) li; |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
292 if (cnext->score >= c->score) |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
293 break; |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
294 } |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
295 |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
296 /* Add the element there */ |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
297 fd_list_insert_before(li, &c->chain); |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
298 } |
| 84 | 299 } |
| 300 | |
|
563
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
301 /* Now simply move back all the "highest" candidates at the end of the list */ |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
302 fd_list_move_end(candidates, &highest); |
|
dc9764591567
Automatic load-balancing between peers that have the same routing score. Use rt_ereg to obtain stable routes.
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
403
diff
changeset
|
303 |
| 84 | 304 return 0; |
| 305 } | |
| 306 |