## iof-bird-daemon / nest / a-path.c @ 62e64905

History | View | Annotate | Download (13.8 KB)

1 | c0668f36 | Martin Mares | ```
/*
``` |
---|---|---|---|

2 | ```
* BIRD -- Path Operations
``` |
||

3 | ```
*
``` |
||

4 | ```
* (c) 2000 Martin Mares <mj@ucw.cz>
``` |
||

5 | ```
* (c) 2000 Pavel Machek <pavel@ucw.cz>
``` |
||

6 | ```
*
``` |
||

7 | ```
* Can be freely distributed and used under the terms of the GNU GPL.
``` |
||

8 | ```
*/
``` |
||

9 | |||

10 | #include "nest/bird.h" |
||

11 | #include "nest/route.h" |
||

12 | c6add07f | Martin Mares | #include "nest/attrs.h" |

13 | c0668f36 | Martin Mares | #include "lib/resource.h" |

14 | #include "lib/unaligned.h" |
||

15 | c6add07f | Martin Mares | #include "lib/string.h" |

16 | 05198c12 | Ondrej Zajicek | #include "filter/filter.h" |

17 | c0668f36 | Martin Mares | |

18 | 43c1cecc | Ondrej Zajicek | ```
// static inline void put_as(byte *data, u32 as) { put_u32(data, as); }
``` |

19 | ```
// static inline u32 get_as(byte *data) { return get_u32(data); }
``` |
||

20 | 11cb6202 | Ondrej Zajicek | |

21 | 43c1cecc | Ondrej Zajicek | ```
#define put_as put_u32
``` |

22 | ```
#define get_as get_u32
``` |
||

23 | 0eb7f17d | Pavel Tvrdik | #define BS 4 /* Default block size of ASN (autonomous system number) */ |

24 | 11cb6202 | Ondrej Zajicek | |

25 | d15b0b0a | Ondrej Zajicek (work) | #define BAD(DSC, VAL) ({ err_dsc = DSC; err_val = VAL; goto bad; }) |

26 | |||

27 | ```
int
``` |
||

28 | as_path_valid(byte *data, uint len, int bs, char *err, uint elen) |
||

29 | c0668f36 | Martin Mares | { |

30 | d15b0b0a | Ondrej Zajicek (work) | byte *pos = data; |

31 | char *err_dsc = NULL; |
||

32 | ```
uint err_val = 0;
``` |
||

33 | |||

34 | ```
while (len)
``` |
||

35 | { |
||

36 | if (len < 2) |
||

37 | BAD("segment framing error", 0); |
||

38 | |||

39 | ```
/* Process one AS path segment */
``` |
||

40 | ```
uint type = pos[0];
``` |
||

41 | uint slen = 2 + bs * pos[1]; |
||

42 | |||

43 | ```
if (len < slen)
``` |
||

44 | ```
BAD("segment framing error", len);
``` |
||

45 | |||

46 | ```
/* XXXX handle CONFED segments */
``` |
||

47 | ```
if ((type != AS_PATH_SET) && (type != AS_PATH_SEQUENCE))
``` |
||

48 | ```
BAD("unknown segment", type);
``` |
||

49 | |||

50 | if (pos[1] == 0) |
||

51 | ```
BAD("zero-length segment", type);
``` |
||

52 | c0668f36 | Martin Mares | |

53 | d15b0b0a | Ondrej Zajicek (work) | pos += slen; |

54 | len -= slen; |
||

55 | } |
||

56 | |||

57 | return 1; |
||

58 | |||

59 | ```
bad:
``` |
||

60 | ```
if (err)
``` |
||

61 | if (bsnprintf(err, elen, "%s (%u) at %d", err_dsc, err_val, (int) (pos - data)) < 0) |
||

62 | err[0] = 0; |
||

63 | |||

64 | return 0; |
||

65 | } |
||

66 | |||

67 | ```
int
``` |
||

68 | as_path_16to32(byte *dst, byte *src, uint len) |
||

69 | { |
||

70 | byte *dst0 = dst; |
||

71 | byte *end = src + len; |
||

72 | uint i, n; |
||

73 | |||

74 | ```
while (src < end)
``` |
||

75 | { |
||

76 | ```
n = src[1];
``` |
||

77 | *dst++ = *src++; |
||

78 | *dst++ = *src++; |
||

79 | |||

80 | for (i = 0; i < n; i++) |
||

81 | c0668f36 | Martin Mares | { |

82 | d15b0b0a | Ondrej Zajicek (work) | put_u32(dst, get_u16(src)); |

83 | ```
src += 2;
``` |
||

84 | ```
dst += 4;
``` |
||

85 | c0668f36 | Martin Mares | } |

86 | d15b0b0a | Ondrej Zajicek (work) | } |

87 | |||

88 | ```
return dst - dst0;
``` |
||

89 | } |
||

90 | |||

91 | ```
int
``` |
||

92 | as_path_32to16(byte *dst, byte *src, uint len) |
||

93 | { |
||

94 | byte *dst0 = dst; |
||

95 | byte *end = src + len; |
||

96 | uint i, n; |
||

97 | |||

98 | ```
while (src < end)
``` |
||

99 | { |
||

100 | ```
n = src[1];
``` |
||

101 | *dst++ = *src++; |
||

102 | *dst++ = *src++; |
||

103 | |||

104 | for (i = 0; i < n; i++) |
||

105 | c0668f36 | Martin Mares | { |

106 | d15b0b0a | Ondrej Zajicek (work) | put_u16(dst, get_u32(src)); |

107 | ```
src += 4;
``` |
||

108 | ```
dst += 2;
``` |
||

109 | c0668f36 | Martin Mares | } |

110 | d15b0b0a | Ondrej Zajicek (work) | } |

111 | |||

112 | ```
return dst - dst0;
``` |
||

113 | c0668f36 | Martin Mares | } |

114 | c6add07f | Martin Mares | |

115 | 11cb6202 | Ondrej Zajicek | ```
int
``` |

116 | d15b0b0a | Ondrej Zajicek (work) | as_path_contains_as4(const struct adata *path) |

117 | 11cb6202 | Ondrej Zajicek | { |

118 | d15b0b0a | Ondrej Zajicek (work) | ```
const byte *pos = path->data;
``` |

119 | ```
const byte *end = pos + path->length;
``` |
||

120 | uint i, n; |
||

121 | 11cb6202 | Ondrej Zajicek | |

122 | d15b0b0a | Ondrej Zajicek (work) | ```
while (pos < end)
``` |

123 | { |
||

124 | ```
n = pos[1];
``` |
||

125 | ```
pos += 2;
``` |
||

126 | |||

127 | for (i = 0; i < n; i++) |
||

128 | 11cb6202 | Ondrej Zajicek | { |

129 | d15b0b0a | Ondrej Zajicek (work) | if (get_as(pos) > 0xFFFF) |

130 | return 1; |
||

131 | 11cb6202 | Ondrej Zajicek | |

132 | d15b0b0a | Ondrej Zajicek (work) | pos += BS; |

133 | 11cb6202 | Ondrej Zajicek | } |

134 | d15b0b0a | Ondrej Zajicek (work) | } |

135 | 11cb6202 | Ondrej Zajicek | |

136 | d15b0b0a | Ondrej Zajicek (work) | return 0; |

137 | 11cb6202 | Ondrej Zajicek | } |

138 | |||

139 | ```
int
``` |
||

140 | d15b0b0a | Ondrej Zajicek (work) | as_path_contains_confed(const struct adata *path) |

141 | { |
||

142 | ```
const byte *pos = path->data;
``` |
||

143 | ```
const byte *end = pos + path->length;
``` |
||

144 | |||

145 | ```
while (pos < end)
``` |
||

146 | { |
||

147 | ```
uint type = pos[0];
``` |
||

148 | uint slen = 2 + BS * pos[1]; |
||

149 | |||

150 | ```
if ((type == AS_PATH_CONFED_SEQUENCE) ||
``` |
||

151 | (type == AS_PATH_CONFED_SET)) |
||

152 | return 1; |
||

153 | |||

154 | pos += slen; |
||

155 | } |
||

156 | |||

157 | return 0; |
||

158 | } |
||

159 | |||

160 | static void |
||

161 | ```
as_path_strip_confed_(byte *dst, const byte *src, uint len)
``` |
||

162 | { |
||

163 | ```
const byte *end = src + len;
``` |
||

164 | |||

165 | ```
while (src < end)
``` |
||

166 | { |
||

167 | ```
uint type = src[0];
``` |
||

168 | uint slen = 2 + BS * src[1]; |
||

169 | |||

170 | ```
/* Copy regular segments */
``` |
||

171 | ```
if ((type == AS_PATH_SET) || (type == AS_PATH_SEQUENCE))
``` |
||

172 | { |
||

173 | memcpy(dst, src, slen); |
||

174 | dst += slen; |
||

175 | } |
||

176 | |||

177 | src += slen; |
||

178 | } |
||

179 | } |
||

180 | |||

181 | ```
struct adata *
``` |
||

182 | as_path_strip_confed(struct linpool *pool, const struct adata *op) |
||

183 | { |
||

184 | ```
struct adata *np = lp_alloc_adata(pool, op->length);
``` |
||

185 | as_path_strip_confed_(np->data, op->data, op->length); |
||

186 | ```
return np;
``` |
||

187 | } |
||

188 | |||

189 | ```
struct adata *
``` |
||

190 | as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as, int strip) |
||

191 | { |
||

192 | ```
struct adata *np;
``` |
||

193 | ```
const byte *pos = op->data;
``` |
||

194 | uint len = op->length; |
||

195 | |||

196 | if (len && (pos[0] == seq) && (pos[1] < 255)) |
||

197 | { |
||

198 | ```
/* Starting with matching segment => just prepend the AS number */
``` |
||

199 | np = lp_alloc_adata(pool, len + BS); |
||

200 | ```
np->data[0] = seq;
``` |
||

201 | np->data[1] = pos[1] + 1; |
||

202 | ```
put_as(np->data + 2, as);
``` |
||

203 | |||

204 | ```
uint dlen = BS * pos[1];
``` |
||

205 | memcpy(np->data + 2 + BS, pos + 2, dlen); |
||

206 | ```
ADVANCE(pos, len, 2 + dlen);
``` |
||

207 | } |
||

208 | ```
else
``` |
||

209 | { |
||

210 | ```
/* Create a new path segment */
``` |
||

211 | ```
np = lp_alloc_adata(pool, len + 2 + BS);
``` |
||

212 | ```
np->data[0] = seq;
``` |
||

213 | np->data[1] = 1; |
||

214 | ```
put_as(np->data + 2, as);
``` |
||

215 | } |
||

216 | |||

217 | ```
if (len)
``` |
||

218 | { |
||

219 | byte *dst = np->data + 2 + BS * np->data[1]; |
||

220 | |||

221 | ```
if (strip)
``` |
||

222 | as_path_strip_confed_(dst, pos, len); |
||

223 | ```
else
``` |
||

224 | memcpy(dst, pos, len); |
||

225 | } |
||

226 | |||

227 | ```
return np;
``` |
||

228 | } |
||

229 | |||

230 | |||

231 | ```
struct adata *
``` |
||

232 | as_path_to_old(struct linpool *pool, const struct adata *path) |
||

233 | 11cb6202 | Ondrej Zajicek | { |

234 | d15b0b0a | Ondrej Zajicek (work) | ```
struct adata *res = lp_alloc_adata(pool, path->length);
``` |

235 | byte *pos = res->data; |
||

236 | byte *end = pos + res->length; |
||

237 | uint i, n; |
||

238 | 11cb6202 | Ondrej Zajicek | u32 as; |

239 | |||

240 | d15b0b0a | Ondrej Zajicek (work) | ```
/* Copy the whole path */
``` |

241 | memcpy(res->data, path->data, path->length); |
||

242 | 11cb6202 | Ondrej Zajicek | |

243 | d15b0b0a | Ondrej Zajicek (work) | ```
/* Replace 32-bit AS numbers with AS_TRANS */
``` |

244 | ```
while (pos < end)
``` |
||

245 | { |
||

246 | ```
n = pos[1];
``` |
||

247 | ```
pos += 2;
``` |
||

248 | |||

249 | for (i = 0; i < n; i++) |
||

250 | 11cb6202 | Ondrej Zajicek | { |

251 | d15b0b0a | Ondrej Zajicek (work) | as = get_as(pos); |

252 | if (as > 0xFFFF) |
||

253 | put_as(pos, AS_TRANS); |
||

254 | 11cb6202 | Ondrej Zajicek | |

255 | d15b0b0a | Ondrej Zajicek (work) | pos += BS; |

256 | } |
||

257 | } |
||

258 | 11cb6202 | Ondrej Zajicek | |

259 | d15b0b0a | Ondrej Zajicek (work) | ```
return res;
``` |

260 | } |
||

261 | 11cb6202 | Ondrej Zajicek | |

262 | d15b0b0a | Ondrej Zajicek (work) | ```
/*
``` |

263 | ```
* Cut the path to the length @num, measured to the usual path metric. Note that
``` |
||

264 | ```
* AS_CONFED_* segments have zero length and must be added if they are on edge.
``` |
||

265 | ```
* In contrast to other as_path_* functions, @path is modified in place.
``` |
||

266 | ```
*/
``` |
||

267 | ```
void
``` |
||

268 | ```
as_path_cut(struct adata *path, uint num)
``` |
||

269 | { |
||

270 | byte *pos = path->data; |
||

271 | byte *end = pos + path->length; |
||

272 | 11cb6202 | Ondrej Zajicek | |

273 | d15b0b0a | Ondrej Zajicek (work) | ```
while (pos < end)
``` |

274 | { |
||

275 | ```
uint t = pos[0];
``` |
||

276 | ```
uint l = pos[1];
``` |
||

277 | ```
uint n = 0;
``` |
||

278 | |||

279 | ```
switch (t)
``` |
||

280 | { |
||

281 | case AS_PATH_SET: n = 1; break; |
||

282 | case AS_PATH_SEQUENCE: n = l; break; |
||

283 | case AS_PATH_CONFED_SEQUENCE: n = 0; break; |
||

284 | case AS_PATH_CONFED_SET: n = 0; break; |
||

285 | default: bug("as_path_cut: Invalid path segment"); |
||

286 | 11cb6202 | Ondrej Zajicek | } |

287 | |||

288 | d15b0b0a | Ondrej Zajicek (work) | ```
/* Cannot add whole segment, so try partial one and finish */
``` |

289 | ```
if (num < n)
``` |
||

290 | { |
||

291 | ```
if (num)
``` |
||

292 | { |
||

293 | ```
pos[1] = num;
``` |
||

294 | ```
pos += 2 + BS * num;
``` |
||

295 | } |
||

296 | |||

297 | ```
break;
``` |
||

298 | } |
||

299 | |||

300 | num -= n; |
||

301 | ```
pos += 2 + BS * l;
``` |
||

302 | } |
||

303 | |||

304 | path->length = pos - path->data; |
||

305 | } |
||

306 | |||

307 | ```
/*
``` |
||

308 | ```
* Merge (concatenate) paths @p1 and @p2 and return the result.
``` |
||

309 | ```
* In contrast to other as_path_* functions, @p1 and @p2 may be reused.
``` |
||

310 | ```
*/
``` |
||

311 | ```
struct adata *
``` |
||

312 | as_path_merge(struct linpool *pool, struct adata *p1, struct adata *p2) |
||

313 | { |
||

314 | if (p1->length == 0) |
||

315 | ```
return p2;
``` |
||

316 | |||

317 | if (p2->length == 0) |
||

318 | ```
return p1;
``` |
||

319 | |||

320 | ```
struct adata *res = lp_alloc_adata(pool, p1->length + p2->length);
``` |
||

321 | memcpy(res->data, p1->data, p1->length); |
||

322 | memcpy(res->data + p1->length, p2->data, p2->length); |
||

323 | |||

324 | ```
return res;
``` |
||

325 | 11cb6202 | Ondrej Zajicek | } |

326 | |||

327 | c6add07f | Martin Mares | ```
void
``` |

328 | d15b0b0a | Ondrej Zajicek (work) | as_path_format(const struct adata *path, byte *buf, uint size) |

329 | c6add07f | Martin Mares | { |

330 | d15b0b0a | Ondrej Zajicek (work) | ```
const byte *p = path->data;
``` |

331 | ```
const byte *e = p + path->length;
``` |
||

332 | 11cb6202 | Ondrej Zajicek | ```
byte *end = buf + size - 16;
``` |

333 | c6add07f | Martin Mares | int sp = 1; |

334 | 93a786cb | Martin Mares | ```
int l, isset;
``` |

335 | c6add07f | Martin Mares | |

336 | ```
while (p < e)
``` |
||

337 | { |
||

338 | ```
if (buf > end)
``` |
||

339 | { |
||

340 | ```
strcpy(buf, " ...");
``` |
||

341 | ```
return;
``` |
||

342 | } |
||

343 | isset = (*p++ == AS_PATH_SET); |
||

344 | l = *p++; |
||

345 | ```
if (isset)
``` |
||

346 | { |
||

347 | ```
if (!sp)
``` |
||

348 | ```
*buf++ = ' ';
``` |
||

349 | ```
*buf++ = '{';
``` |
||

350 | ```
sp = 0;
``` |
||

351 | } |
||

352 | ```
while (l-- && buf <= end)
``` |
||

353 | { |
||

354 | ```
if (!sp)
``` |
||

355 | ```
*buf++ = ' ';
``` |
||

356 | 11cb6202 | Ondrej Zajicek | ```
buf += bsprintf(buf, "%u", get_as(p));
``` |

357 | 43c1cecc | Ondrej Zajicek | p += BS; |

358 | c6add07f | Martin Mares | ```
sp = 0;
``` |

359 | } |
||

360 | ```
if (isset)
``` |
||

361 | { |
||

362 | ```
*buf++ = ' ';
``` |
||

363 | ```
*buf++ = '}';
``` |
||

364 | ```
sp = 0;
``` |
||

365 | } |
||

366 | } |
||

367 | ```
*buf = 0;
``` |
||

368 | } |
||

369 | 684c6f5a | Pavel Machek | |

370 | ```
int
``` |
||

371 | d15b0b0a | Ondrej Zajicek (work) | as_path_getlen(const struct adata *path) |

372 | 684c6f5a | Pavel Machek | { |

373 | d15b0b0a | Ondrej Zajicek (work) | ```
const byte *pos = path->data;
``` |

374 | ```
const byte *end = pos + path->length;
``` |
||

375 | ```
uint res = 0;
``` |
||

376 | 949bd34e | Ondrej Zajicek | |

377 | d15b0b0a | Ondrej Zajicek (work) | ```
while (pos < end)
``` |

378 | { |
||

379 | ```
uint t = pos[0];
``` |
||

380 | ```
uint l = pos[1];
``` |
||

381 | ```
uint n = 0;
``` |
||

382 | 684c6f5a | Pavel Machek | |

383 | d15b0b0a | Ondrej Zajicek (work) | ```
switch (t)
``` |

384 | 4b03f64b | Martin Mares | { |

385 | d15b0b0a | Ondrej Zajicek (work) | case AS_PATH_SET: n = 1; break; |

386 | case AS_PATH_SEQUENCE: n = l; break; |
||

387 | case AS_PATH_CONFED_SEQUENCE: n = 0; break; |
||

388 | case AS_PATH_CONFED_SET: n = 0; break; |
||

389 | default: bug("as_path_getlen: Invalid path segment"); |
||

390 | 684c6f5a | Pavel Machek | } |

391 | d15b0b0a | Ondrej Zajicek (work) | |

392 | res += n; |
||

393 | ```
pos += 2 + BS * l;
``` |
||

394 | } |
||

395 | |||

396 | 684c6f5a | Pavel Machek | ```
return res;
``` |

397 | } |
||

398 | 2a40efa5 | Pavel Machek | |

399 | f49528a3 | Martin Mares | ```
int
``` |

400 | d15b0b0a | Ondrej Zajicek (work) | as_path_get_last(const struct adata *path, u32 *orig_as) |

401 | f49528a3 | Martin Mares | { |

402 | 11cb6202 | Ondrej Zajicek | int found = 0; |

403 | ```
u32 res = 0;
``` |
||

404 | d15b0b0a | Ondrej Zajicek (work) | ```
const u8 *p = path->data;
``` |

405 | ```
const u8 *q = p+path->length;
``` |
||

406 | f49528a3 | Martin Mares | ```
int len;
``` |

407 | |||

408 | ```
while (p<q)
``` |
||

409 | { |
||

410 | ```
switch (*p++)
``` |
||

411 | { |
||

412 | ```
case AS_PATH_SET:
``` |
||

413 | ```
if (len = *p++)
``` |
||

414 | 11cb6202 | Ondrej Zajicek | { |

415 | 52b9b2a1 | Ondrej Zajicek | ```
found = 0;
``` |

416 | 43c1cecc | Ondrej Zajicek | p += BS * len; |

417 | 11cb6202 | Ondrej Zajicek | } |

418 | f49528a3 | Martin Mares | ```
break;
``` |

419 | ```
case AS_PATH_SEQUENCE:
``` |
||

420 | ```
if (len = *p++)
``` |
||

421 | 11cb6202 | Ondrej Zajicek | { |

422 | ```
found = 1;
``` |
||

423 | 43c1cecc | Ondrej Zajicek | ```
res = get_as(p + BS * (len - 1));
``` |

424 | p += BS * len; |
||

425 | 11cb6202 | Ondrej Zajicek | } |

426 | f49528a3 | Martin Mares | ```
break;
``` |

427 | 9c9cc35c | Ondrej Zajicek (work) | default: bug("Invalid path segment"); |

428 | f49528a3 | Martin Mares | } |

429 | } |
||

430 | 11cb6202 | Ondrej Zajicek | |

431 | 52b9b2a1 | Ondrej Zajicek | ```
if (found)
``` |

432 | *orig_as = res; |
||

433 | 11cb6202 | Ondrej Zajicek | ```
return found;
``` |

434 | f49528a3 | Martin Mares | } |

435 | |||

436 | 9c9cc35c | Ondrej Zajicek (work) | u32 |

437 | d15b0b0a | Ondrej Zajicek (work) | as_path_get_last_nonaggregated(const struct adata *path) |

438 | 9c9cc35c | Ondrej Zajicek (work) | { |

439 | d15b0b0a | Ondrej Zajicek (work) | ```
const u8 *p = path->data;
``` |

440 | ```
const u8 *q = p+path->length;
``` |
||

441 | 9c9cc35c | Ondrej Zajicek (work) | ```
u32 res = 0;
``` |

442 | ```
int len;
``` |
||

443 | |||

444 | ```
while (p<q)
``` |
||

445 | { |
||

446 | ```
switch (*p++)
``` |
||

447 | { |
||

448 | ```
case AS_PATH_SET:
``` |
||

449 | ```
return res;
``` |
||

450 | |||

451 | ```
case AS_PATH_SEQUENCE:
``` |
||

452 | ```
if (len = *p++)
``` |
||

453 | ```
res = get_as(p + BS * (len - 1));
``` |
||

454 | p += BS * len; |
||

455 | ```
break;
``` |
||

456 | |||

457 | default: bug("Invalid path segment"); |
||

458 | } |
||

459 | } |
||

460 | |||

461 | ```
return res;
``` |
||

462 | } |
||

463 | |||

464 | 11cb6202 | Ondrej Zajicek | ```
int
``` |

465 | d15b0b0a | Ondrej Zajicek (work) | as_path_get_first(const struct adata *path, u32 *last_as) |

466 | b6bf284a | Ondrej Zajicek | { |

467 | d15b0b0a | Ondrej Zajicek (work) | ```
const u8 *p = path->data;
``` |

468 | b6bf284a | Ondrej Zajicek | |

469 | if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0)) |
||

470 | return 0; |
||

471 | ```
else
``` |
||

472 | { |
||

473 | ```
*last_as = get_as(p+2);
``` |
||

474 | return 1; |
||

475 | } |
||

476 | } |
||

477 | |||

478 | ```
int
``` |
||

479 | d15b0b0a | Ondrej Zajicek (work) | as_path_contains(const struct adata *path, u32 as, int min) |

480 | 11cb6202 | Ondrej Zajicek | { |

481 | d15b0b0a | Ondrej Zajicek (work) | ```
const u8 *p = path->data;
``` |

482 | ```
const u8 *q = p+path->length;
``` |
||

483 | a15dab76 | Ondrej Zajicek | int num = 0; |

484 | 11cb6202 | Ondrej Zajicek | ```
int i, n;
``` |

485 | |||

486 | ```
while (p<q)
``` |
||

487 | { |
||

488 | ```
n = p[1];
``` |
||

489 | ```
p += 2;
``` |
||

490 | for(i=0; i<n; i++) |
||

491 | { |
||

492 | ```
if (get_as(p) == as)
``` |
||

493 | a15dab76 | Ondrej Zajicek | ```
if (++num == min)
``` |

494 | return 1; |
||

495 | 43c1cecc | Ondrej Zajicek | p += BS; |

496 | 11cb6202 | Ondrej Zajicek | } |

497 | } |
||

498 | return 0; |
||

499 | } |
||

500 | |||

501 | cc31b75a | Ondrej Zajicek | ```
int
``` |

502 | d15b0b0a | Ondrej Zajicek (work) | as_path_match_set(const struct adata *path, struct f_tree *set) |

503 | cc31b75a | Ondrej Zajicek | { |

504 | d15b0b0a | Ondrej Zajicek (work) | ```
const u8 *p = path->data;
``` |

505 | ```
const u8 *q = p+path->length;
``` |
||

506 | cc31b75a | Ondrej Zajicek | ```
int i, n;
``` |

507 | |||

508 | ```
while (p<q)
``` |
||

509 | { |
||

510 | ```
n = p[1];
``` |
||

511 | ```
p += 2;
``` |
||

512 | for (i=0; i<n; i++) |
||

513 | { |
||

514 | ```
struct f_val v = {T_INT, .val.i = get_as(p)};
``` |
||

515 | ```
if (find_tree(set, v))
``` |
||

516 | return 1; |
||

517 | p += BS; |
||

518 | } |
||

519 | } |
||

520 | |||

521 | return 0; |
||

522 | } |
||

523 | |||

524 | bff9ce51 | Ondrej Zajicek | ```
struct adata *
``` |

525 | as_path_filter(struct linpool *pool, struct adata *path, struct f_tree *set, u32 key, int pos) |
||

526 | { |
||

527 | ```
if (!path)
``` |
||

528 | return NULL; |
||

529 | |||

530 | ```
int len = path->length;
``` |
||

531 | d15b0b0a | Ondrej Zajicek (work) | ```
const u8 *p = path->data;
``` |

532 | ```
const u8 *q = path->data + len;
``` |
||

533 | bff9ce51 | Ondrej Zajicek | u8 *d, *d2; |

534 | ```
int i, bt, sn, dn;
``` |
||

535 | u8 buf[len]; |
||

536 | |||

537 | d = buf; |
||

538 | ```
while (p<q)
``` |
||

539 | { |
||

540 | ```
/* Read block header (type and length) */
``` |
||

541 | ```
bt = p[0];
``` |
||

542 | ```
sn = p[1];
``` |
||

543 | ```
dn = 0;
``` |
||

544 | ```
p += 2;
``` |
||

545 | ```
d2 = d + 2;
``` |
||

546 | |||

547 | for (i = 0; i < sn; i++) |
||

548 | { |
||

549 | u32 as = get_as(p); |
||

550 | ```
int match;
``` |
||

551 | |||

552 | ```
if (set)
``` |
||

553 | ```
match = !!find_tree(set, (struct f_val){T_INT, .val.i = as});
``` |
||

554 | ```
else
``` |
||

555 | match = (as == key); |
||

556 | |||

557 | ```
if (match == pos)
``` |
||

558 | { |
||

559 | put_as(d2, as); |
||

560 | d2 += BS; |
||

561 | dn++; |
||

562 | } |
||

563 | |||

564 | p += BS; |
||

565 | } |
||

566 | |||

567 | if (dn > 0) |
||

568 | { |
||

569 | ```
/* Nonempty block, set block header and advance */
``` |
||

570 | ```
d[0] = bt;
``` |
||

571 | ```
d[1] = dn;
``` |
||

572 | d = d2; |
||

573 | } |
||

574 | } |
||

575 | |||

576 | 3e236955 | Jan Moskyto Matejka | uint nl = d - buf; |

577 | bff9ce51 | Ondrej Zajicek | ```
if (nl == path->length)
``` |

578 | ```
return path;
``` |
||

579 | |||

580 | struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl); |
||

581 | res->length = nl; |
||

582 | memcpy(res->data, buf, nl); |
||

583 | |||

584 | ```
return res;
``` |
||

585 | } |
||

586 | |||

587 | 11cb6202 | Ondrej Zajicek | |

588 | c8a6b9a3 | Ondrej Zajicek | ```
struct pm_pos
``` |

589 | { |
||

590 | u8 set; |
||

591 | u8 mark; |
||

592 | ```
union
``` |
||

593 | { |
||

594 | d15b0b0a | Ondrej Zajicek (work) | const char *sp; |

595 | c8a6b9a3 | Ondrej Zajicek | u32 asn; |

596 | } val; |
||

597 | }; |
||

598 | |||

599 | static int |
||

600 | d15b0b0a | Ondrej Zajicek (work) | parse_path(const struct adata *path, struct pm_pos *pos) |

601 | 2a40efa5 | Pavel Machek | { |

602 | d15b0b0a | Ondrej Zajicek (work) | ```
const u8 *p = path->data;
``` |

603 | ```
const u8 *q = p + path->length;
``` |
||

604 | c8a6b9a3 | Ondrej Zajicek | ```
struct pm_pos *opos = pos;
``` |

605 | 05198c12 | Ondrej Zajicek | ```
int i, len;
``` |

606 | 2a40efa5 | Pavel Machek | |

607 | 25cb9f1d | Ondrej Zajicek | |

608 | c8a6b9a3 | Ondrej Zajicek | ```
while (p < q)
``` |

609 | ```
switch (*p++)
``` |
||

610 | 2a40efa5 | Pavel Machek | { |

611 | c8a6b9a3 | Ondrej Zajicek | ```
case AS_PATH_SET:
``` |

612 | ```
pos->set = 1;
``` |
||

613 | ```
pos->mark = 0;
``` |
||

614 | pos->val.sp = p; |
||

615 | len = *p; |
||

616 | 43c1cecc | Ondrej Zajicek | ```
p += 1 + BS * len;
``` |

617 | c8a6b9a3 | Ondrej Zajicek | pos++; |

618 | ```
break;
``` |
||

619 | |||

620 | ```
case AS_PATH_SEQUENCE:
``` |
||

621 | len = *p++; |
||

622 | for (i = 0; i < len; i++) |
||

623 | { |
||

624 | ```
pos->set = 0;
``` |
||

625 | ```
pos->mark = 0;
``` |
||

626 | pos->val.asn = get_as(p); |
||

627 | 43c1cecc | Ondrej Zajicek | p += BS; |

628 | c8a6b9a3 | Ondrej Zajicek | pos++; |

629 | 2a40efa5 | Pavel Machek | } |

630 | c8a6b9a3 | Ondrej Zajicek | ```
break;
``` |

631 | |||

632 | ```
default:
``` |
||

633 | ```
bug("as_path_match: Invalid path component");
``` |
||

634 | 2a40efa5 | Pavel Machek | } |

635 | d15b0b0a | Ondrej Zajicek (work) | |

636 | c8a6b9a3 | Ondrej Zajicek | ```
return pos - opos;
``` |

637 | } |
||

638 | |||

639 | static int |
||

640 | a0fe1944 | Ondrej Filip | ```
pm_match(struct pm_pos *pos, u32 asn, u32 asn2)
``` |

641 | c8a6b9a3 | Ondrej Zajicek | { |

642 | a0fe1944 | Ondrej Filip | u32 gas; |

643 | c8a6b9a3 | Ondrej Zajicek | ```
if (! pos->set)
``` |

644 | a0fe1944 | Ondrej Filip | ```
return ((pos->val.asn >= asn) && (pos->val.asn <= asn2));
``` |

645 | c8a6b9a3 | Ondrej Zajicek | |

646 | d15b0b0a | Ondrej Zajicek (work) | ```
const u8 *p = pos->val.sp;
``` |

647 | c8a6b9a3 | Ondrej Zajicek | ```
int len = *p++;
``` |

648 | ```
int i;
``` |
||

649 | |||

650 | for (i = 0; i < len; i++) |
||

651 | a0fe1944 | Ondrej Filip | { |

652 | gas = get_as(p + i * BS); |
||

653 | |||

654 | ```
if ((gas >= asn) && (gas <= asn2))
``` |
||

655 | c8a6b9a3 | Ondrej Zajicek | return 1; |

656 | a0fe1944 | Ondrej Filip | } |

657 | c8a6b9a3 | Ondrej Zajicek | |

658 | return 0; |
||

659 | } |
||

660 | |||

661 | static void |
||

662 | pm_mark(struct pm_pos *pos, int i, int plen, int *nl, int *nh) |
||

663 | { |
||

664 | ```
int j;
``` |
||

665 | |||

666 | ```
if (pos[i].set)
``` |
||

667 | ```
pos[i].mark = 1;
``` |
||

668 | d15b0b0a | Ondrej Zajicek (work) | |

669 | c8a6b9a3 | Ondrej Zajicek | for (j = i + 1; (j < plen) && pos[j].set && (! pos[j].mark); j++) |

670 | ```
pos[j].mark = 1;
``` |
||

671 | ```
pos[j].mark = 1;
``` |
||

672 | |||

673 | ```
/* We are going downwards, therefore every mark is
``` |
||

674 | ```
new low and just the first mark is new high */
``` |
||

675 | |||

676 | *nl = i + (pos[i].set ? 0 : 1); |
||

677 | |||

678 | if (*nh < 0) |
||

679 | *nh = j; |
||

680 | } |
||

681 | |||

682 | ```
/* AS path matching is nontrivial. Because AS path can
``` |
||

683 | ```
* contain sets, it is not a plain wildcard matching. A set
``` |
||

684 | ```
* in an AS path is interpreted as it might represent any
``` |
||

685 | ```
* sequence of AS numbers from that set (possibly with
``` |
||

686 | ```
* repetitions). So it is also a kind of a pattern,
``` |
||

687 | ```
* more complicated than a path mask.
``` |
||

688 | ```
*
``` |
||

689 | ```
* The algorithm for AS path matching is a variant
``` |
||

690 | ```
* of nondeterministic finite state machine, where
``` |
||

691 | ```
* positions in AS path are states, and items in
``` |
||

692 | ```
* path mask are input for that finite state machine.
``` |
||

693 | ```
* During execution of the algorithm we maintain a set
``` |
||

694 | ```
* of marked states - a state is marked if it can be
``` |
||

695 | ```
* reached by any walk through NFSM with regard to
``` |
||

696 | ```
* currently processed part of input. When we process
``` |
||

697 | ```
* next part of mask, we advance each marked state.
``` |
||

698 | ```
* We start with marked first position, when we
``` |
||

699 | ```
* run out of marked positions, we reject. When
``` |
||

700 | a0fe1944 | Ondrej Filip | ```
* we process the whole mask, we accept if final position
``` |

701 | c8a6b9a3 | Ondrej Zajicek | ```
* (auxiliary position after last real position in AS path)
``` |

702 | ```
* is marked.
``` |
||

703 | ```
*/
``` |
||

704 | ```
int
``` |
||

705 | d15b0b0a | Ondrej Zajicek (work) | as_path_match(const struct adata *path, struct f_path_mask *mask) |

706 | c8a6b9a3 | Ondrej Zajicek | { |

707 | struct pm_pos pos[2048 + 1]; |
||

708 | ```
int plen = parse_path(path, pos);
``` |
||

709 | ```
int l, h, i, nh, nl;
``` |
||

710 | e81b440f | Ondrej Zajicek | ```
u32 val = 0;
``` |

711 | a0fe1944 | Ondrej Filip | ```
u32 val2 = 0;
``` |

712 | c8a6b9a3 | Ondrej Zajicek | |

713 | ```
/* l and h are bound of interval of positions where
``` |
||

714 | ```
are marked states */
``` |
||

715 | |||

716 | ```
pos[plen].set = 0;
``` |
||

717 | ```
pos[plen].mark = 0;
``` |
||

718 | |||

719 | ```
l = h = 0;
``` |
||

720 | pos[0].mark = 1; |
||

721 | |||

722 | ```
while (mask)
``` |
||

723 | { |
||

724 | ```
/* We remove this mark to not step after pos[plen] */
``` |
||

725 | ```
pos[plen].mark = 0;
``` |
||

726 | |||

727 | ```
switch (mask->kind)
``` |
||

728 | { |
||

729 | ```
case PM_ASTERISK:
``` |
||

730 | ```
for (i = l; i <= plen; i++)
``` |
||

731 | ```
pos[i].mark = 1;
``` |
||

732 | h = plen; |
||

733 | ```
break;
``` |
||

734 | |||

735 | a0fe1944 | Ondrej Filip | case PM_ASN: /* Define single ASN as ASN..ASN - very narrow interval */ |

736 | val2 = val = mask->val; |
||

737 | 92a72a4c | Ondrej Zajicek | ```
goto step;
``` |

738 | ```
case PM_ASN_EXPR:
``` |
||

739 | a0fe1944 | Ondrej Filip | ```
val2 = val = f_eval_asn((struct f_inst *) mask->val);
``` |

740 | 92a72a4c | Ondrej Zajicek | ```
goto step;
``` |

741 | a0fe1944 | Ondrej Filip | ```
case PM_ASN_RANGE:
``` |

742 | val = mask->val; |
||

743 | val2 = mask->val2; |
||

744 | ```
goto step;
``` |
||

745 | 92a72a4c | Ondrej Zajicek | ```
case PM_QUESTION:
``` |

746 | ```
step:
``` |
||

747 | e81b440f | Ondrej Zajicek | ```
nh = nl = -1;
``` |

748 | c8a6b9a3 | Ondrej Zajicek | ```
for (i = h; i >= l; i--)
``` |

749 | ```
if (pos[i].mark)
``` |
||

750 | { |
||

751 | ```
pos[i].mark = 0;
``` |
||

752 | a0fe1944 | Ondrej Filip | ```
if ((mask->kind == PM_QUESTION) || pm_match(pos + i, val, val2))
``` |

753 | c8a6b9a3 | Ondrej Zajicek | pm_mark(pos, i, plen, &nl, &nh); |

754 | } |
||

755 | |||

756 | if (nh < 0) |
||

757 | 2a40efa5 | Pavel Machek | return 0; |

758 | c8a6b9a3 | Ondrej Zajicek | |

759 | h = nh; |
||

760 | l = nl; |
||

761 | ```
break;
``` |
||

762 | 2a40efa5 | Pavel Machek | } |

763 | |||

764 | c8a6b9a3 | Ondrej Zajicek | mask = mask->next; |

765 | 2a40efa5 | Pavel Machek | } |

766 | 98347659 | Pavel Machek | |

767 | c8a6b9a3 | Ondrej Zajicek | ```
return pos[plen].mark;
``` |

768 | } |