bgp_aspath.c 47 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938
  1. /* AS path management routines.
  2. Copyright (C) 1996, 97, 98, 99 Kunihiro Ishiguro
  3. Copyright (C) 2005 Sun Microsystems, Inc.
  4. This file is part of GNU Zebra.
  5. GNU Zebra is free software; you can redistribute it and/or modify it
  6. under the terms of the GNU General Public License as published by the
  7. Free Software Foundation; either version 2, or (at your option) any
  8. later version.
  9. GNU Zebra is distributed in the hope that it will be useful, but
  10. WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  12. General Public License for more details.
  13. You should have received a copy of the GNU General Public License
  14. along with GNU Zebra; see the file COPYING. If not, write to the Free
  15. Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  16. 02111-1307, USA. */
  17. #include <zebra.h>
  18. #include "hash.h"
  19. #include "memory.h"
  20. #include "vector.h"
  21. #include "vty.h"
  22. #include "str.h"
  23. #include "log.h"
  24. #include "stream.h"
  25. #include "jhash.h"
  26. #include "filter.h"
  27. #include "bgpd/bgpd.h"
  28. #include "bgpd/bgp_aspath.h"
  29. #include "bgpd/bgp_debug.h"
  30. #include "bgpd/bgp_attr.h"
  31. /* Attr. Flags and Attr. Type Code. */
  32. #define AS_HEADER_SIZE 2
  33. /* Now FOUR octets are used for AS value. */
  34. #define AS_VALUE_SIZE sizeof (as_t)
  35. /* This is the old one */
  36. #define AS16_VALUE_SIZE sizeof (as16_t)
  37. /* Maximum protocol segment length value */
  38. #define AS_SEGMENT_MAX 255
  39. /* The following length and size macros relate specifically to Quagga's
  40. * internal representation of AS-Segments, not per se to the on-wire
  41. * sizes and lengths. At present (200508) they sort of match, however
  42. * the ONLY functions which should now about the on-wire syntax are
  43. * aspath_put, assegment_put and assegment_parse.
  44. *
  45. * aspath_put returns bytes written, the only definitive record of
  46. * size of wire-format attribute..
  47. */
  48. /* Calculated size in bytes of ASN segment data to hold N ASN's */
  49. #define ASSEGMENT_DATA_SIZE(N,S) \
  50. ((N) * ( (S) ? AS_VALUE_SIZE : AS16_VALUE_SIZE) )
  51. /* Calculated size of segment struct to hold N ASN's */
  52. #define ASSEGMENT_SIZE(N,S) (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N,S))
  53. /* AS segment octet length. */
  54. #define ASSEGMENT_LEN(X,S) ASSEGMENT_SIZE((X)->length,S)
  55. /* AS_SEQUENCE segments can be packed together */
  56. /* Can the types of X and Y be considered for packing? */
  57. #define ASSEGMENT_TYPES_PACKABLE(X,Y) \
  58. ( ((X)->type == (Y)->type) \
  59. && ((X)->type == AS_SEQUENCE))
  60. /* Types and length of X,Y suitable for packing? */
  61. #define ASSEGMENTS_PACKABLE(X,Y) \
  62. ( ASSEGMENT_TYPES_PACKABLE( (X), (Y)) \
  63. && ( ((X)->length + (Y)->length) <= AS_SEGMENT_MAX ) )
  64. /* As segment header - the on-wire representation
  65. * NOT the internal representation!
  66. */
  67. struct assegment_header
  68. {
  69. u_char type;
  70. u_char length;
  71. };
  72. /* Hash for aspath. This is the top level structure of AS path. */
  73. static struct hash *ashash;
  74. /* Stream for SNMP. See aspath_snmp_pathseg */
  75. static struct stream *snmp_stream;
  76. /* Callers are required to initialize the memory */
  77. static as_t *
  78. assegment_data_new (int num)
  79. {
  80. return (XMALLOC (MTYPE_AS_SEG_DATA, ASSEGMENT_DATA_SIZE (num, 1)));
  81. }
  82. static void
  83. assegment_data_free (as_t *asdata)
  84. {
  85. XFREE (MTYPE_AS_SEG_DATA, asdata);
  86. }
  87. /* Get a new segment. Note that 0 is an allowed length,
  88. * and will result in a segment with no allocated data segment.
  89. * the caller should immediately assign data to the segment, as the segment
  90. * otherwise is not generally valid
  91. */
  92. static struct assegment *
  93. assegment_new (u_char type, u_short length)
  94. {
  95. struct assegment *new;
  96. new = XCALLOC (MTYPE_AS_SEG, sizeof (struct assegment));
  97. if (length)
  98. new->as = assegment_data_new (length);
  99. new->length = length;
  100. new->type = type;
  101. return new;
  102. }
  103. static void
  104. assegment_free (struct assegment *seg)
  105. {
  106. if (!seg)
  107. return;
  108. if (seg->as)
  109. assegment_data_free (seg->as);
  110. memset (seg, 0xfe, sizeof(struct assegment));
  111. XFREE (MTYPE_AS_SEG, seg);
  112. return;
  113. }
  114. /* free entire chain of segments */
  115. static void
  116. assegment_free_all (struct assegment *seg)
  117. {
  118. struct assegment *prev;
  119. while (seg)
  120. {
  121. prev = seg;
  122. seg = seg->next;
  123. assegment_free (prev);
  124. }
  125. }
  126. /* Duplicate just the given assegment and its data */
  127. static struct assegment *
  128. assegment_dup (struct assegment *seg)
  129. {
  130. struct assegment *new;
  131. new = assegment_new (seg->type, seg->length);
  132. memcpy (new->as, seg->as, ASSEGMENT_DATA_SIZE (new->length, 1) );
  133. return new;
  134. }
  135. /* Duplicate entire chain of assegments, return the head */
  136. static struct assegment *
  137. assegment_dup_all (struct assegment *seg)
  138. {
  139. struct assegment *new = NULL;
  140. struct assegment *head = NULL;
  141. while (seg)
  142. {
  143. if (head)
  144. {
  145. new->next = assegment_dup (seg);
  146. new = new->next;
  147. }
  148. else
  149. head = new = assegment_dup (seg);
  150. seg = seg->next;
  151. }
  152. return head;
  153. }
  154. /* prepend the as number to given segment, given num of times */
  155. static struct assegment *
  156. assegment_prepend_asns (struct assegment *seg, as_t asnum, int num)
  157. {
  158. as_t *newas;
  159. int i;
  160. if (!num)
  161. return seg;
  162. if (num >= AS_SEGMENT_MAX)
  163. return seg; /* we don't do huge prepends */
  164. if ((newas = assegment_data_new (seg->length + num)) == NULL)
  165. return seg;
  166. for (i = 0; i < num; i++)
  167. newas[i] = asnum;
  168. memcpy (newas + num, seg->as, ASSEGMENT_DATA_SIZE (seg->length, 1));
  169. assegment_data_free (seg->as);
  170. seg->as = newas;
  171. seg->length += num;
  172. return seg;
  173. }
  174. /* append given array of as numbers to the segment */
  175. static struct assegment *
  176. assegment_append_asns (struct assegment *seg, as_t *asnos, int num)
  177. {
  178. as_t *newas;
  179. newas = XREALLOC (MTYPE_AS_SEG_DATA, seg->as,
  180. ASSEGMENT_DATA_SIZE (seg->length + num, 1));
  181. if (newas)
  182. {
  183. seg->as = newas;
  184. memcpy (seg->as + seg->length, asnos, ASSEGMENT_DATA_SIZE(num, 1));
  185. seg->length += num;
  186. return seg;
  187. }
  188. assegment_free_all (seg);
  189. return NULL;
  190. }
  191. static int
  192. int_cmp (const void *p1, const void *p2)
  193. {
  194. const as_t *as1 = p1;
  195. const as_t *as2 = p2;
  196. return (*as1 == *as2)
  197. ? 0 : ( (*as1 > *as2) ? 1 : -1);
  198. }
  199. /* normalise the segment.
  200. * In particular, merge runs of AS_SEQUENCEs into one segment
  201. * Internally, we do not care about the wire segment length limit, and
  202. * we want each distinct AS_PATHs to have the exact same internal
  203. * representation - eg, so that our hashing actually works..
  204. */
  205. static struct assegment *
  206. assegment_normalise (struct assegment *head)
  207. {
  208. struct assegment *seg = head, *pin;
  209. struct assegment *tmp;
  210. if (!head)
  211. return head;
  212. while (seg)
  213. {
  214. pin = seg;
  215. /* Sort values SET segments, for determinism in paths to aid
  216. * creation of hash values / path comparisons
  217. * and because it helps other lesser implementations ;)
  218. */
  219. if (seg->type == AS_SET || seg->type == AS_CONFED_SET)
  220. {
  221. int tail = 0;
  222. int i;
  223. qsort (seg->as, seg->length, sizeof(as_t), int_cmp);
  224. /* weed out dupes */
  225. for (i=1; i < seg->length; i++)
  226. {
  227. if (seg->as[tail] == seg->as[i])
  228. continue;
  229. tail++;
  230. if (tail < i)
  231. seg->as[tail] = seg->as[i];
  232. }
  233. /* seg->length can be 0.. */
  234. if (seg->length)
  235. seg->length = tail + 1;
  236. }
  237. /* read ahead from the current, pinned segment while the segments
  238. * are packable/mergeable. Append all following packable segments
  239. * to the segment we have pinned and remove these appended
  240. * segments.
  241. */
  242. while (pin->next && ASSEGMENT_TYPES_PACKABLE(pin, pin->next))
  243. {
  244. tmp = pin->next;
  245. seg = pin->next;
  246. /* append the next sequence to the pinned sequence */
  247. pin = assegment_append_asns (pin, seg->as, seg->length);
  248. /* bypass the next sequence */
  249. pin->next = seg->next;
  250. /* get rid of the now referenceless segment */
  251. assegment_free (tmp);
  252. }
  253. seg = pin->next;
  254. }
  255. return head;
  256. }
  257. static struct aspath *
  258. aspath_new (void)
  259. {
  260. return XCALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
  261. }
  262. /* Free AS path structure. */
  263. void
  264. aspath_free (struct aspath *aspath)
  265. {
  266. if (!aspath)
  267. return;
  268. if (aspath->segments)
  269. assegment_free_all (aspath->segments);
  270. if (aspath->str)
  271. XFREE (MTYPE_AS_STR, aspath->str);
  272. XFREE (MTYPE_AS_PATH, aspath);
  273. }
  274. /* Unintern aspath from AS path bucket. */
  275. void
  276. aspath_unintern (struct aspath **aspath)
  277. {
  278. struct aspath *ret;
  279. struct aspath *asp = *aspath;
  280. if (asp->refcnt)
  281. asp->refcnt--;
  282. if (asp->refcnt == 0)
  283. {
  284. /* This aspath must exist in aspath hash table. */
  285. ret = hash_release (ashash, asp);
  286. assert (ret != NULL);
  287. aspath_free (asp);
  288. *aspath = NULL;
  289. }
  290. }
  291. /* Return the start or end delimiters for a particular Segment type */
  292. #define AS_SEG_START 0
  293. #define AS_SEG_END 1
  294. static char
  295. aspath_delimiter_char (u_char type, u_char which)
  296. {
  297. int i;
  298. struct
  299. {
  300. int type;
  301. char start;
  302. char end;
  303. } aspath_delim_char [] =
  304. {
  305. { AS_SET, '{', '}' },
  306. { AS_CONFED_SET, '[', ']' },
  307. { AS_CONFED_SEQUENCE, '(', ')' },
  308. { 0 }
  309. };
  310. for (i = 0; aspath_delim_char[i].type != 0; i++)
  311. {
  312. if (aspath_delim_char[i].type == type)
  313. {
  314. if (which == AS_SEG_START)
  315. return aspath_delim_char[i].start;
  316. else if (which == AS_SEG_END)
  317. return aspath_delim_char[i].end;
  318. }
  319. }
  320. return ' ';
  321. }
  322. /* countup asns from this segment and index onward */
  323. static int
  324. assegment_count_asns (struct assegment *seg, int from)
  325. {
  326. int count = 0;
  327. while (seg)
  328. {
  329. if (!from)
  330. count += seg->length;
  331. else
  332. {
  333. count += (seg->length - from);
  334. from = 0;
  335. }
  336. seg = seg->next;
  337. }
  338. return count;
  339. }
  340. unsigned int
  341. aspath_count_confeds (struct aspath *aspath)
  342. {
  343. int count = 0;
  344. struct assegment *seg = aspath->segments;
  345. while (seg)
  346. {
  347. if (seg->type == AS_CONFED_SEQUENCE)
  348. count += seg->length;
  349. else if (seg->type == AS_CONFED_SET)
  350. count++;
  351. seg = seg->next;
  352. }
  353. return count;
  354. }
  355. unsigned int
  356. aspath_count_hops (struct aspath *aspath)
  357. {
  358. int count = 0;
  359. struct assegment *seg = aspath->segments;
  360. while (seg)
  361. {
  362. if (seg->type == AS_SEQUENCE)
  363. count += seg->length;
  364. else if (seg->type == AS_SET)
  365. count++;
  366. seg = seg->next;
  367. }
  368. return count;
  369. }
  370. /* Estimate size aspath /might/ take if encoded into an
  371. * ASPATH attribute.
  372. *
  373. * This is a quick estimate, not definitive! aspath_put()
  374. * may return a different number!!
  375. */
  376. unsigned int
  377. aspath_size (struct aspath *aspath)
  378. {
  379. int size = 0;
  380. struct assegment *seg = aspath->segments;
  381. while (seg)
  382. {
  383. size += ASSEGMENT_SIZE(seg->length, 1);
  384. seg = seg->next;
  385. }
  386. return size;
  387. }
  388. /* Return highest public ASN in path */
  389. as_t
  390. aspath_highest (struct aspath *aspath)
  391. {
  392. struct assegment *seg = aspath->segments;
  393. as_t highest = 0;
  394. unsigned int i;
  395. while (seg)
  396. {
  397. for (i = 0; i < seg->length; i++)
  398. if (seg->as[i] > highest
  399. && (seg->as[i] < BGP_PRIVATE_AS_MIN
  400. || seg->as[i] > BGP_PRIVATE_AS_MAX))
  401. highest = seg->as[i];
  402. seg = seg->next;
  403. }
  404. return highest;
  405. }
  406. /* Return the left-most ASN in path */
  407. as_t
  408. aspath_leftmost (struct aspath *aspath)
  409. {
  410. struct assegment *seg = aspath->segments;
  411. as_t leftmost = 0;
  412. if (seg && seg->length && seg->type == AS_SEQUENCE)
  413. leftmost = seg->as[0];
  414. return leftmost;
  415. }
  416. /* Return 1 if there are any 4-byte ASes in the path */
  417. unsigned int
  418. aspath_has_as4 (struct aspath *aspath)
  419. {
  420. struct assegment *seg = aspath->segments;
  421. unsigned int i;
  422. while (seg)
  423. {
  424. for (i = 0; i < seg->length; i++)
  425. if (seg->as[i] > BGP_AS_MAX)
  426. return 1;
  427. seg = seg->next;
  428. }
  429. return 0;
  430. }
  431. /* Convert aspath structure to string expression. */
  432. static void
  433. aspath_make_str_count (struct aspath *as)
  434. {
  435. struct assegment *seg;
  436. int str_size;
  437. int len = 0;
  438. char *str_buf;
  439. /* Empty aspath. */
  440. if (!as->segments)
  441. {
  442. as->str = XMALLOC (MTYPE_AS_STR, 1);
  443. as->str[0] = '\0';
  444. as->str_len = 0;
  445. return;
  446. }
  447. seg = as->segments;
  448. /* ASN takes 5 to 10 chars plus seperator, see below.
  449. * If there is one differing segment type, we need an additional
  450. * 2 chars for segment delimiters, and the final '\0'.
  451. * Hopefully this is large enough to avoid hitting the realloc
  452. * code below for most common sequences.
  453. *
  454. * This was changed to 10 after the well-known BGP assertion, which
  455. * had hit some parts of the Internet in May of 2009.
  456. */
  457. #define ASN_STR_LEN (10 + 1)
  458. str_size = MAX (assegment_count_asns (seg, 0) * ASN_STR_LEN + 2 + 1,
  459. ASPATH_STR_DEFAULT_LEN);
  460. str_buf = XMALLOC (MTYPE_AS_STR, str_size);
  461. while (seg)
  462. {
  463. int i;
  464. char seperator;
  465. /* Check AS type validity. Set seperator for segment */
  466. switch (seg->type)
  467. {
  468. case AS_SET:
  469. case AS_CONFED_SET:
  470. seperator = ',';
  471. break;
  472. case AS_SEQUENCE:
  473. case AS_CONFED_SEQUENCE:
  474. seperator = ' ';
  475. break;
  476. default:
  477. XFREE (MTYPE_AS_STR, str_buf);
  478. as->str = NULL;
  479. as->str_len = 0;
  480. return;
  481. }
  482. /* We might need to increase str_buf, particularly if path has
  483. * differing segments types, our initial guesstimate above will
  484. * have been wrong. Need 10 chars for ASN, a seperator each and
  485. * potentially two segment delimiters, plus a space between each
  486. * segment and trailing zero.
  487. *
  488. * This definitely didn't work with the value of 5 bytes and
  489. * 32-bit ASNs.
  490. */
  491. #define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1)
  492. if ( (len + SEGMENT_STR_LEN(seg)) > str_size)
  493. {
  494. str_size = len + SEGMENT_STR_LEN(seg);
  495. str_buf = XREALLOC (MTYPE_AS_STR, str_buf, str_size);
  496. }
  497. #undef ASN_STR_LEN
  498. #undef SEGMENT_STR_LEN
  499. if (seg->type != AS_SEQUENCE)
  500. len += snprintf (str_buf + len, str_size - len,
  501. "%c",
  502. aspath_delimiter_char (seg->type, AS_SEG_START));
  503. /* write out the ASNs, with their seperators, bar the last one*/
  504. for (i = 0; i < seg->length; i++)
  505. {
  506. len += snprintf (str_buf + len, str_size - len, "%u", seg->as[i]);
  507. if (i < (seg->length - 1))
  508. len += snprintf (str_buf + len, str_size - len, "%c", seperator);
  509. }
  510. if (seg->type != AS_SEQUENCE)
  511. len += snprintf (str_buf + len, str_size - len, "%c",
  512. aspath_delimiter_char (seg->type, AS_SEG_END));
  513. if (seg->next)
  514. len += snprintf (str_buf + len, str_size - len, " ");
  515. seg = seg->next;
  516. }
  517. assert (len < str_size);
  518. str_buf[len] = '\0';
  519. as->str = str_buf;
  520. as->str_len = len;
  521. return;
  522. }
  523. static void
  524. aspath_str_update (struct aspath *as)
  525. {
  526. if (as->str)
  527. XFREE (MTYPE_AS_STR, as->str);
  528. aspath_make_str_count (as);
  529. }
  530. /* Intern allocated AS path. */
  531. struct aspath *
  532. aspath_intern (struct aspath *aspath)
  533. {
  534. struct aspath *find;
  535. /* Assert this AS path structure is not interned and has the string
  536. representation built. */
  537. assert (aspath->refcnt == 0);
  538. assert (aspath->str);
  539. /* Check AS path hash. */
  540. find = hash_get (ashash, aspath, hash_alloc_intern);
  541. if (find != aspath)
  542. aspath_free (aspath);
  543. find->refcnt++;
  544. return find;
  545. }
  546. /* Duplicate aspath structure. Created same aspath structure but
  547. reference count and AS path string is cleared. */
  548. struct aspath *
  549. aspath_dup (struct aspath *aspath)
  550. {
  551. unsigned short buflen = aspath->str_len + 1;
  552. struct aspath *new;
  553. new = XCALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
  554. if (aspath->segments)
  555. new->segments = assegment_dup_all (aspath->segments);
  556. if (!aspath->str)
  557. return new;
  558. new->str = XMALLOC (MTYPE_AS_STR, buflen);
  559. new->str_len = aspath->str_len;
  560. /* copy the string data */
  561. if (aspath->str_len > 0)
  562. memcpy (new->str, aspath->str, buflen);
  563. else
  564. new->str[0] = '\0';
  565. return new;
  566. }
  567. static void *
  568. aspath_hash_alloc (void *arg)
  569. {
  570. const struct aspath *aspath = arg;
  571. struct aspath *new;
  572. /* Malformed AS path value. */
  573. assert (aspath->str);
  574. if (! aspath->str)
  575. return NULL;
  576. /* New aspath structure is needed. */
  577. new = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
  578. /* Reuse segments and string representation */
  579. new->refcnt = 0;
  580. new->segments = aspath->segments;
  581. new->str = aspath->str;
  582. new->str_len = aspath->str_len;
  583. return new;
  584. }
  585. /* parse as-segment byte stream in struct assegment */
  586. static int
  587. assegments_parse (struct stream *s, size_t length,
  588. struct assegment **result, int use32bit)
  589. {
  590. struct assegment_header segh;
  591. struct assegment *seg, *prev = NULL, *head = NULL;
  592. size_t bytes = 0;
  593. /* empty aspath (ie iBGP or somesuch) */
  594. if (length == 0)
  595. return 0;
  596. if (BGP_DEBUG (as4, AS4_SEGMENT))
  597. zlog_debug ("[AS4SEG] Parse aspath segment: got total byte length %lu",
  598. (unsigned long) length);
  599. /* basic checks */
  600. if ((STREAM_READABLE(s) < length)
  601. || (STREAM_READABLE(s) < AS_HEADER_SIZE)
  602. || (length % AS16_VALUE_SIZE ))
  603. return -1;
  604. while (bytes < length)
  605. {
  606. int i;
  607. size_t seg_size;
  608. if ((length - bytes) <= AS_HEADER_SIZE)
  609. {
  610. if (head)
  611. assegment_free_all (head);
  612. return -1;
  613. }
  614. /* softly softly, get the header first on its own */
  615. segh.type = stream_getc (s);
  616. segh.length = stream_getc (s);
  617. seg_size = ASSEGMENT_SIZE(segh.length, use32bit);
  618. if (BGP_DEBUG (as4, AS4_SEGMENT))
  619. zlog_debug ("[AS4SEG] Parse aspath segment: got type %d, length %d",
  620. segh.type, segh.length);
  621. /* check it.. */
  622. if ( ((bytes + seg_size) > length)
  623. /* 1771bis 4.3b: seg length contains one or more */
  624. || (segh.length == 0)
  625. /* Paranoia in case someone changes type of segment length.
  626. * Shift both values by 0x10 to make the comparison operate
  627. * on more, than 8 bits (otherwise it's a warning, bug #564).
  628. */
  629. || ((sizeof segh.length > 1)
  630. && (0x10 + segh.length > 0x10 + AS_SEGMENT_MAX)))
  631. {
  632. if (head)
  633. assegment_free_all (head);
  634. return -1;
  635. }
  636. switch (segh.type)
  637. {
  638. case AS_SEQUENCE:
  639. case AS_SET:
  640. case AS_CONFED_SEQUENCE:
  641. case AS_CONFED_SET:
  642. break;
  643. default:
  644. if (head)
  645. assegment_free_all (head);
  646. return -1;
  647. }
  648. /* now its safe to trust lengths */
  649. seg = assegment_new (segh.type, segh.length);
  650. if (head)
  651. prev->next = seg;
  652. else /* it's the first segment */
  653. head = prev = seg;
  654. for (i = 0; i < segh.length; i++)
  655. seg->as[i] = (use32bit) ? stream_getl (s) : stream_getw (s);
  656. bytes += seg_size;
  657. if (BGP_DEBUG (as4, AS4_SEGMENT))
  658. zlog_debug ("[AS4SEG] Parse aspath segment: Bytes now: %lu",
  659. (unsigned long) bytes);
  660. prev = seg;
  661. }
  662. *result = assegment_normalise (head);
  663. return 0;
  664. }
  665. /* AS path parse function. pnt is a pointer to byte stream and length
  666. is length of byte stream. If there is same AS path in the the AS
  667. path hash then return it else make new AS path structure.
  668. On error NULL is returned.
  669. */
  670. struct aspath *
  671. aspath_parse (struct stream *s, size_t length, int use32bit)
  672. {
  673. struct aspath as;
  674. struct aspath *find;
  675. /* If length is odd it's malformed AS path. */
  676. /* Nit-picking: if (use32bit == 0) it is malformed if odd,
  677. * otherwise its malformed when length is larger than 2 and (length-2)
  678. * is not dividable by 4.
  679. * But... this time we're lazy
  680. */
  681. if (length % AS16_VALUE_SIZE )
  682. return NULL;
  683. memset (&as, 0, sizeof (struct aspath));
  684. if (assegments_parse (s, length, &as.segments, use32bit) < 0)
  685. return NULL;
  686. /* If already same aspath exist then return it. */
  687. find = hash_get (ashash, &as, aspath_hash_alloc);
  688. /* bug! should not happen, let the daemon crash below */
  689. assert (find);
  690. /* if the aspath was already hashed free temporary memory. */
  691. if (find->refcnt)
  692. {
  693. assegment_free_all (as.segments);
  694. /* aspath_key_make() always updates the string */
  695. XFREE (MTYPE_AS_STR, as.str);
  696. }
  697. find->refcnt++;
  698. return find;
  699. }
  700. static void
  701. assegment_data_put (struct stream *s, as_t *as, int num, int use32bit)
  702. {
  703. int i;
  704. assert (num <= AS_SEGMENT_MAX);
  705. for (i = 0; i < num; i++)
  706. if ( use32bit )
  707. stream_putl (s, as[i]);
  708. else
  709. {
  710. if ( as[i] <= BGP_AS_MAX )
  711. stream_putw(s, as[i]);
  712. else
  713. stream_putw(s, BGP_AS_TRANS);
  714. }
  715. }
  716. static size_t
  717. assegment_header_put (struct stream *s, u_char type, int length)
  718. {
  719. size_t lenp;
  720. assert (length <= AS_SEGMENT_MAX);
  721. stream_putc (s, type);
  722. lenp = stream_get_endp (s);
  723. stream_putc (s, length);
  724. return lenp;
  725. }
  726. /* write aspath data to stream */
  727. size_t
  728. aspath_put (struct stream *s, struct aspath *as, int use32bit )
  729. {
  730. struct assegment *seg = as->segments;
  731. size_t bytes = 0;
  732. if (!seg || seg->length == 0)
  733. return 0;
  734. if (seg)
  735. {
  736. /*
  737. * Hey, what do we do when we have > STREAM_WRITABLE(s) here?
  738. * At the moment, we would write out a partial aspath, and our peer
  739. * will complain and drop the session :-/
  740. *
  741. * The general assumption here is that many things tested will
  742. * never happen. And, in real live, up to now, they have not.
  743. */
  744. while (seg && (ASSEGMENT_LEN(seg, use32bit) <= STREAM_WRITEABLE(s)))
  745. {
  746. struct assegment *next = seg->next;
  747. int written = 0;
  748. int asns_packed = 0;
  749. size_t lenp;
  750. /* Overlength segments have to be split up */
  751. while ( (seg->length - written) > AS_SEGMENT_MAX)
  752. {
  753. assegment_header_put (s, seg->type, AS_SEGMENT_MAX);
  754. assegment_data_put (s, seg->as, AS_SEGMENT_MAX, use32bit);
  755. written += AS_SEGMENT_MAX;
  756. bytes += ASSEGMENT_SIZE (written, use32bit);
  757. }
  758. /* write the final segment, probably is also the first */
  759. lenp = assegment_header_put (s, seg->type, seg->length - written);
  760. assegment_data_put (s, (seg->as + written), seg->length - written,
  761. use32bit);
  762. /* Sequence-type segments can be 'packed' together
  763. * Case of a segment which was overlength and split up
  764. * will be missed here, but that doesn't matter.
  765. */
  766. while (next && ASSEGMENTS_PACKABLE (seg, next))
  767. {
  768. /* NB: We should never normally get here given we
  769. * normalise aspath data when parse them. However, better
  770. * safe than sorry. We potentially could call
  771. * assegment_normalise here instead, but it's cheaper and
  772. * easier to do it on the fly here rather than go through
  773. * the segment list twice every time we write out
  774. * aspath's.
  775. */
  776. /* Next segment's data can fit in this one */
  777. assegment_data_put (s, next->as, next->length, use32bit);
  778. /* update the length of the segment header */
  779. stream_putc_at (s, lenp, seg->length - written + next->length);
  780. asns_packed += next->length;
  781. next = next->next;
  782. }
  783. bytes += ASSEGMENT_SIZE (seg->length - written + asns_packed,
  784. use32bit);
  785. seg = next;
  786. }
  787. }
  788. return bytes;
  789. }
  790. /* This is for SNMP BGP4PATHATTRASPATHSEGMENT
  791. * We have no way to manage the storage, so we use a static stream
  792. * wrapper around aspath_put.
  793. */
  794. u_char *
  795. aspath_snmp_pathseg (struct aspath *as, size_t *varlen)
  796. {
  797. #define SNMP_PATHSEG_MAX 1024
  798. if (!snmp_stream)
  799. snmp_stream = stream_new (SNMP_PATHSEG_MAX);
  800. else
  801. stream_reset (snmp_stream);
  802. if (!as)
  803. {
  804. *varlen = 0;
  805. return NULL;
  806. }
  807. aspath_put (snmp_stream, as, 0); /* use 16 bit for now here */
  808. *varlen = stream_get_endp (snmp_stream);
  809. return stream_pnt(snmp_stream);
  810. }
  811. #define min(A,B) ((A) < (B) ? (A) : (B))
  812. static struct assegment *
  813. aspath_aggregate_as_set_add (struct aspath *aspath, struct assegment *asset,
  814. as_t as)
  815. {
  816. int i;
  817. /* If this is first AS set member, create new as-set segment. */
  818. if (asset == NULL)
  819. {
  820. asset = assegment_new (AS_SET, 1);
  821. if (! aspath->segments)
  822. aspath->segments = asset;
  823. else
  824. {
  825. struct assegment *seg = aspath->segments;
  826. while (seg->next)
  827. seg = seg->next;
  828. seg->next = asset;
  829. }
  830. asset->type = AS_SET;
  831. asset->length = 1;
  832. asset->as[0] = as;
  833. }
  834. else
  835. {
  836. /* Check this AS value already exists or not. */
  837. for (i = 0; i < asset->length; i++)
  838. if (asset->as[i] == as)
  839. return asset;
  840. asset->length++;
  841. asset->as = XREALLOC (MTYPE_AS_SEG_DATA, asset->as,
  842. asset->length * AS_VALUE_SIZE);
  843. asset->as[asset->length - 1] = as;
  844. }
  845. return asset;
  846. }
  847. /* Modify as1 using as2 for aggregation. */
  848. struct aspath *
  849. aspath_aggregate (struct aspath *as1, struct aspath *as2)
  850. {
  851. int i;
  852. int minlen;
  853. int match;
  854. int from;
  855. struct assegment *seg1 = as1->segments;
  856. struct assegment *seg2 = as2->segments;
  857. struct aspath *aspath = NULL;
  858. struct assegment *asset;
  859. struct assegment *prevseg = NULL;
  860. match = 0;
  861. minlen = 0;
  862. aspath = NULL;
  863. asset = NULL;
  864. /* First of all check common leading sequence. */
  865. while (seg1 && seg2)
  866. {
  867. /* Check segment type. */
  868. if (seg1->type != seg2->type)
  869. break;
  870. /* Minimum segment length. */
  871. minlen = min (seg1->length, seg2->length);
  872. for (match = 0; match < minlen; match++)
  873. if (seg1->as[match] != seg2->as[match])
  874. break;
  875. if (match)
  876. {
  877. struct assegment *seg = assegment_new (seg1->type, 0);
  878. seg = assegment_append_asns (seg, seg1->as, match);
  879. if (! aspath)
  880. {
  881. aspath = aspath_new ();
  882. aspath->segments = seg;
  883. }
  884. else
  885. prevseg->next = seg;
  886. prevseg = seg;
  887. }
  888. if (match != minlen || match != seg1->length
  889. || seg1->length != seg2->length)
  890. break;
  891. seg1 = seg1->next;
  892. seg2 = seg2->next;
  893. }
  894. if (! aspath)
  895. aspath = aspath_new();
  896. /* Make as-set using rest of all information. */
  897. from = match;
  898. while (seg1)
  899. {
  900. for (i = from; i < seg1->length; i++)
  901. asset = aspath_aggregate_as_set_add (aspath, asset, seg1->as[i]);
  902. from = 0;
  903. seg1 = seg1->next;
  904. }
  905. from = match;
  906. while (seg2)
  907. {
  908. for (i = from; i < seg2->length; i++)
  909. asset = aspath_aggregate_as_set_add (aspath, asset, seg2->as[i]);
  910. from = 0;
  911. seg2 = seg2->next;
  912. }
  913. assegment_normalise (aspath->segments);
  914. aspath_str_update (aspath);
  915. return aspath;
  916. }
  917. /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
  918. attribute, check the leftmost AS number in the AS_PATH attribute is
  919. or not the peer's AS number. */
  920. int
  921. aspath_firstas_check (struct aspath *aspath, as_t asno)
  922. {
  923. if ( (aspath == NULL) || (aspath->segments == NULL) )
  924. return 0;
  925. if (aspath->segments
  926. && (aspath->segments->type == AS_SEQUENCE)
  927. && (aspath->segments->as[0] == asno ))
  928. return 1;
  929. return 0;
  930. }
  931. /* AS path loop check. If aspath contains asno then return >= 1. */
  932. int
  933. aspath_loop_check (struct aspath *aspath, as_t asno)
  934. {
  935. struct assegment *seg;
  936. int count = 0;
  937. if ( (aspath == NULL) || (aspath->segments == NULL) )
  938. return 0;
  939. seg = aspath->segments;
  940. while (seg)
  941. {
  942. int i;
  943. for (i = 0; i < seg->length; i++)
  944. if (seg->as[i] == asno)
  945. count++;
  946. seg = seg->next;
  947. }
  948. return count;
  949. }
  950. /* When all of AS path is private AS return 1. */
  951. int
  952. aspath_private_as_check (struct aspath *aspath)
  953. {
  954. struct assegment *seg;
  955. if ( !(aspath && aspath->segments) )
  956. return 0;
  957. seg = aspath->segments;
  958. while (seg)
  959. {
  960. int i;
  961. for (i = 0; i < seg->length; i++)
  962. {
  963. if ( (seg->as[i] < BGP_PRIVATE_AS_MIN)
  964. || (seg->as[i] > BGP_PRIVATE_AS_MAX) )
  965. return 0;
  966. }
  967. seg = seg->next;
  968. }
  969. return 1;
  970. }
  971. /* AS path confed check. If aspath contains confed set or sequence then return 1. */
  972. int
  973. aspath_confed_check (struct aspath *aspath)
  974. {
  975. struct assegment *seg;
  976. if ( !(aspath && aspath->segments) )
  977. return 0;
  978. seg = aspath->segments;
  979. while (seg)
  980. {
  981. if (seg->type == AS_CONFED_SET || seg->type == AS_CONFED_SEQUENCE)
  982. return 1;
  983. seg = seg->next;
  984. }
  985. return 0;
  986. }
  987. /* Leftmost AS path segment confed check. If leftmost AS segment is of type
  988. AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */
  989. int
  990. aspath_left_confed_check (struct aspath *aspath)
  991. {
  992. if ( !(aspath && aspath->segments) )
  993. return 0;
  994. if ( (aspath->segments->type == AS_CONFED_SEQUENCE)
  995. || (aspath->segments->type == AS_CONFED_SET) )
  996. return 1;
  997. return 0;
  998. }
  999. /* Merge as1 to as2. as2 should be uninterned aspath. */
  1000. static struct aspath *
  1001. aspath_merge (struct aspath *as1, struct aspath *as2)
  1002. {
  1003. struct assegment *last, *new;
  1004. if (! as1 || ! as2)
  1005. return NULL;
  1006. last = new = assegment_dup_all (as1->segments);
  1007. /* find the last valid segment */
  1008. while (last && last->next)
  1009. last = last->next;
  1010. last->next = as2->segments;
  1011. as2->segments = new;
  1012. aspath_str_update (as2);
  1013. return as2;
  1014. }
  1015. /* Prepend as1 to as2. as2 should be uninterned aspath. */
  1016. struct aspath *
  1017. aspath_prepend (struct aspath *as1, struct aspath *as2)
  1018. {
  1019. struct assegment *seg1;
  1020. struct assegment *seg2;
  1021. if (! as1 || ! as2)
  1022. return NULL;
  1023. seg1 = as1->segments;
  1024. seg2 = as2->segments;
  1025. /* If as2 is empty, only need to dupe as1's chain onto as2 */
  1026. if (seg2 == NULL)
  1027. {
  1028. as2->segments = assegment_dup_all (as1->segments);
  1029. aspath_str_update (as2);
  1030. return as2;
  1031. }
  1032. /* If as1 is empty AS, no prepending to do. */
  1033. if (seg1 == NULL)
  1034. return as2;
  1035. /* find the tail as1's segment chain. */
  1036. while (seg1 && seg1->next)
  1037. seg1 = seg1->next;
  1038. /* Delete any AS_CONFED_SEQUENCE segment from as2. */
  1039. if (seg1->type == AS_SEQUENCE && seg2->type == AS_CONFED_SEQUENCE)
  1040. as2 = aspath_delete_confed_seq (as2);
  1041. /* Compare last segment type of as1 and first segment type of as2. */
  1042. if (seg1->type != seg2->type)
  1043. return aspath_merge (as1, as2);
  1044. if (seg1->type == AS_SEQUENCE)
  1045. {
  1046. /* We have two chains of segments, as1->segments and seg2,
  1047. * and we have to attach them together, merging the attaching
  1048. * segments together into one.
  1049. *
  1050. * 1. dupe as1->segments onto head of as2
  1051. * 2. merge seg2's asns onto last segment of this new chain
  1052. * 3. attach chain after seg2
  1053. */
  1054. /* dupe as1 onto as2's head */
  1055. seg1 = as2->segments = assegment_dup_all (as1->segments);
  1056. /* refind the tail of as2, reusing seg1 */
  1057. while (seg1 && seg1->next)
  1058. seg1 = seg1->next;
  1059. /* merge the old head, seg2, into tail, seg1 */
  1060. seg1 = assegment_append_asns (seg1, seg2->as, seg2->length);
  1061. /* bypass the merged seg2, and attach any chain after it to
  1062. * chain descending from as2's head
  1063. */
  1064. seg1->next = seg2->next;
  1065. /* seg2 is now referenceless and useless*/
  1066. assegment_free (seg2);
  1067. /* we've now prepended as1's segment chain to as2, merging
  1068. * the inbetween AS_SEQUENCE of seg2 in the process
  1069. */
  1070. aspath_str_update (as2);
  1071. return as2;
  1072. }
  1073. else
  1074. {
  1075. /* AS_SET merge code is needed at here. */
  1076. return aspath_merge (as1, as2);
  1077. }
  1078. /* XXX: Ermmm, what if as1 has multiple segments?? */
  1079. /* Not reached */
  1080. }
  1081. /* Iterate over AS_PATH segments and wipe all occurences of the
  1082. * listed AS numbers. Hence some segments may lose some or even
  1083. * all data on the way, the operation is implemented as a smarter
  1084. * version of aspath_dup(), which allocates memory to hold the new
  1085. * data, not the original. The new AS path is returned.
  1086. */
  1087. struct aspath *
  1088. aspath_filter_exclude (struct aspath * source, struct aspath * exclude_list)
  1089. {
  1090. struct assegment * srcseg, * exclseg, * lastseg;
  1091. struct aspath * newpath;
  1092. newpath = aspath_new();
  1093. lastseg = NULL;
  1094. for (srcseg = source->segments; srcseg; srcseg = srcseg->next)
  1095. {
  1096. unsigned i, y, newlen = 0, done = 0, skip_as;
  1097. struct assegment * newseg;
  1098. /* Find out, how much ASns are we going to pick from this segment.
  1099. * We can't perform filtering right inline, because the size of
  1100. * the new segment isn't known at the moment yet.
  1101. */
  1102. for (i = 0; i < srcseg->length; i++)
  1103. {
  1104. skip_as = 0;
  1105. for (exclseg = exclude_list->segments; exclseg && !skip_as; exclseg = exclseg->next)
  1106. for (y = 0; y < exclseg->length; y++)
  1107. if (srcseg->as[i] == exclseg->as[y])
  1108. {
  1109. skip_as = 1;
  1110. // There's no sense in testing the rest of exclusion list, bail out.
  1111. break;
  1112. }
  1113. if (!skip_as)
  1114. newlen++;
  1115. }
  1116. /* newlen is now the number of ASns to copy */
  1117. if (!newlen)
  1118. continue;
  1119. /* Actual copying. Allocate memory and iterate once more, performing filtering. */
  1120. newseg = assegment_new (srcseg->type, newlen);
  1121. for (i = 0; i < srcseg->length; i++)
  1122. {
  1123. skip_as = 0;
  1124. for (exclseg = exclude_list->segments; exclseg && !skip_as; exclseg = exclseg->next)
  1125. for (y = 0; y < exclseg->length; y++)
  1126. if (srcseg->as[i] == exclseg->as[y])
  1127. {
  1128. skip_as = 1;
  1129. break;
  1130. }
  1131. if (skip_as)
  1132. continue;
  1133. newseg->as[done++] = srcseg->as[i];
  1134. }
  1135. /* At his point newlen must be equal to done, and both must be positive. Append
  1136. * the filtered segment to the gross result. */
  1137. if (!lastseg)
  1138. newpath->segments = newseg;
  1139. else
  1140. lastseg->next = newseg;
  1141. lastseg = newseg;
  1142. }
  1143. aspath_str_update (newpath);
  1144. /* We are happy returning even an empty AS_PATH, because the administrator
  1145. * might expect this very behaviour. There's a mean to avoid this, if necessary,
  1146. * by having a match rule against certain AS_PATH regexps in the route-map index.
  1147. */
  1148. aspath_free (source);
  1149. return newpath;
  1150. }
  1151. /* Add specified AS to the leftmost of aspath. */
  1152. static struct aspath *
  1153. aspath_add_asns (struct aspath *aspath, as_t asno, u_char type, unsigned num)
  1154. {
  1155. struct assegment *assegment = aspath->segments;
  1156. unsigned i;
  1157. if (assegment && assegment->type == type)
  1158. {
  1159. /* extend existing segment */
  1160. aspath->segments = assegment_prepend_asns (aspath->segments, asno, num);
  1161. }
  1162. else
  1163. {
  1164. /* prepend with new segment */
  1165. struct assegment *newsegment = assegment_new (type, num);
  1166. for (i = 0; i < num; i++)
  1167. newsegment->as[i] = asno;
  1168. /* insert potentially replacing empty segment */
  1169. if (assegment && assegment->length == 0)
  1170. {
  1171. newsegment->next = assegment->next;
  1172. assegment_free (assegment);
  1173. }
  1174. else
  1175. newsegment->next = assegment;
  1176. aspath->segments = newsegment;
  1177. }
  1178. aspath_str_update (aspath);
  1179. return aspath;
  1180. }
  1181. /* Add specified AS to the leftmost of aspath num times. */
  1182. struct aspath *
  1183. aspath_add_seq_n (struct aspath *aspath, as_t asno, unsigned num)
  1184. {
  1185. return aspath_add_asns (aspath, asno, AS_SEQUENCE, num);
  1186. }
  1187. /* Add specified AS to the leftmost of aspath. */
  1188. struct aspath *
  1189. aspath_add_seq (struct aspath *aspath, as_t asno)
  1190. {
  1191. return aspath_add_asns (aspath, asno, AS_SEQUENCE, 1);
  1192. }
  1193. /* Compare leftmost AS value for MED check. If as1's leftmost AS and
  1194. as2's leftmost AS is same return 1. */
  1195. int
  1196. aspath_cmp_left (const struct aspath *aspath1, const struct aspath *aspath2)
  1197. {
  1198. const struct assegment *seg1;
  1199. const struct assegment *seg2;
  1200. if (!(aspath1 && aspath2))
  1201. return 0;
  1202. seg1 = aspath1->segments;
  1203. seg2 = aspath2->segments;
  1204. /* find first non-confed segments for each */
  1205. while (seg1 && ((seg1->type == AS_CONFED_SEQUENCE)
  1206. || (seg1->type == AS_CONFED_SET)))
  1207. seg1 = seg1->next;
  1208. while (seg2 && ((seg2->type == AS_CONFED_SEQUENCE)
  1209. || (seg2->type == AS_CONFED_SET)))
  1210. seg2 = seg2->next;
  1211. /* Check as1's */
  1212. if (!(seg1 && seg2
  1213. && (seg1->type == AS_SEQUENCE) && (seg2->type == AS_SEQUENCE)))
  1214. return 0;
  1215. if (seg1->as[0] == seg2->as[0])
  1216. return 1;
  1217. return 0;
  1218. }
  1219. /* Truncate an aspath after a number of hops, and put the hops remaining
  1220. * at the front of another aspath. Needed for AS4 compat.
  1221. *
  1222. * Returned aspath is a /new/ aspath, which should either by free'd or
  1223. * interned by the caller, as desired.
  1224. */
  1225. struct aspath *
  1226. aspath_reconcile_as4 ( struct aspath *aspath, struct aspath *as4path)
  1227. {
  1228. struct assegment *seg, *newseg, *prevseg = NULL;
  1229. struct aspath *newpath = NULL, *mergedpath;
  1230. int hops, cpasns = 0;
  1231. if (!aspath)
  1232. return NULL;
  1233. seg = aspath->segments;
  1234. /* CONFEDs should get reconciled too.. */
  1235. hops = (aspath_count_hops (aspath) + aspath_count_confeds (aspath))
  1236. - aspath_count_hops (as4path);
  1237. if (hops < 0)
  1238. {
  1239. if (BGP_DEBUG (as4, AS4))
  1240. zlog_warn ("[AS4] Fewer hops in AS_PATH than NEW_AS_PATH");
  1241. /* Something's gone wrong. The RFC says we should now ignore AS4_PATH,
  1242. * which is daft behaviour - it contains vital loop-detection
  1243. * information which must have been removed from AS_PATH.
  1244. */
  1245. hops = aspath_count_hops (aspath);
  1246. }
  1247. if (!hops)
  1248. return aspath_dup (as4path);
  1249. if ( BGP_DEBUG(as4, AS4))
  1250. zlog_debug("[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now",
  1251. aspath->str, as4path->str);
  1252. while (seg && hops > 0)
  1253. {
  1254. switch (seg->type)
  1255. {
  1256. case AS_SET:
  1257. case AS_CONFED_SET:
  1258. hops--;
  1259. cpasns = seg->length;
  1260. break;
  1261. case AS_CONFED_SEQUENCE:
  1262. /* Should never split a confed-sequence, if hop-count
  1263. * suggests we must then something's gone wrong somewhere.
  1264. *
  1265. * Most important goal is to preserve AS_PATHs prime function
  1266. * as loop-detector, so we fudge the numbers so that the entire
  1267. * confed-sequence is merged in.
  1268. */
  1269. if (hops < seg->length)
  1270. {
  1271. if (BGP_DEBUG (as4, AS4))
  1272. zlog_debug ("[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls"
  1273. " across 2/4 ASN boundary somewhere, broken..");
  1274. hops = seg->length;
  1275. }
  1276. case AS_SEQUENCE:
  1277. cpasns = MIN(seg->length, hops);
  1278. hops -= seg->length;
  1279. }
  1280. assert (cpasns <= seg->length);
  1281. newseg = assegment_new (seg->type, 0);
  1282. newseg = assegment_append_asns (newseg, seg->as, cpasns);
  1283. if (!newpath)
  1284. {
  1285. newpath = aspath_new ();
  1286. newpath->segments = newseg;
  1287. }
  1288. else
  1289. prevseg->next = newseg;
  1290. prevseg = newseg;
  1291. seg = seg->next;
  1292. }
  1293. /* We may be able to join some segments here, and we must
  1294. * do this because... we want normalised aspaths in out hash
  1295. * and we do not want to stumble in aspath_put.
  1296. */
  1297. mergedpath = aspath_merge (newpath, aspath_dup(as4path));
  1298. aspath_free (newpath);
  1299. mergedpath->segments = assegment_normalise (mergedpath->segments);
  1300. aspath_str_update (mergedpath);
  1301. if ( BGP_DEBUG(as4, AS4))
  1302. zlog_debug ("[AS4] result of synthesizing is %s",
  1303. mergedpath->str);
  1304. return mergedpath;
  1305. }
  1306. /* Compare leftmost AS value for MED check. If as1's leftmost AS and
  1307. as2's leftmost AS is same return 1. (confederation as-path
  1308. only). */
  1309. int
  1310. aspath_cmp_left_confed (const struct aspath *aspath1, const struct aspath *aspath2)
  1311. {
  1312. if (! (aspath1 && aspath2) )
  1313. return 0;
  1314. if ( !(aspath1->segments && aspath2->segments) )
  1315. return 0;
  1316. if ( (aspath1->segments->type != AS_CONFED_SEQUENCE)
  1317. || (aspath2->segments->type != AS_CONFED_SEQUENCE) )
  1318. return 0;
  1319. if (aspath1->segments->as[0] == aspath2->segments->as[0])
  1320. return 1;
  1321. return 0;
  1322. }
  1323. /* Delete all leading AS_CONFED_SEQUENCE/SET segments from aspath.
  1324. * See RFC3065, 6.1 c1 */
  1325. struct aspath *
  1326. aspath_delete_confed_seq (struct aspath *aspath)
  1327. {
  1328. struct assegment *seg;
  1329. if (!(aspath && aspath->segments))
  1330. return aspath;
  1331. seg = aspath->segments;
  1332. /* "if the first path segment of the AS_PATH is
  1333. * of type AS_CONFED_SEQUENCE,"
  1334. */
  1335. if (aspath->segments->type != AS_CONFED_SEQUENCE)
  1336. return aspath;
  1337. /* "... that segment and any immediately following segments
  1338. * of the type AS_CONFED_SET or AS_CONFED_SEQUENCE are removed
  1339. * from the AS_PATH attribute,"
  1340. */
  1341. while (seg &&
  1342. (seg->type == AS_CONFED_SEQUENCE || seg->type == AS_CONFED_SET))
  1343. {
  1344. aspath->segments = seg->next;
  1345. assegment_free (seg);
  1346. seg = aspath->segments;
  1347. }
  1348. aspath_str_update (aspath);
  1349. return aspath;
  1350. }
  1351. /* Add new AS number to the leftmost part of the aspath as
  1352. AS_CONFED_SEQUENCE. */
  1353. struct aspath*
  1354. aspath_add_confed_seq (struct aspath *aspath, as_t asno)
  1355. {
  1356. return aspath_add_asns (aspath, asno, AS_CONFED_SEQUENCE, 1);
  1357. }
  1358. /* Add new as value to as path structure. */
  1359. static void
  1360. aspath_as_add (struct aspath *as, as_t asno)
  1361. {
  1362. struct assegment *seg = as->segments;
  1363. if (!seg)
  1364. return;
  1365. /* Last segment search procedure. */
  1366. while (seg->next)
  1367. seg = seg->next;
  1368. assegment_append_asns (seg, &asno, 1);
  1369. }
  1370. /* Add new as segment to the as path. */
  1371. static void
  1372. aspath_segment_add (struct aspath *as, int type)
  1373. {
  1374. struct assegment *seg = as->segments;
  1375. struct assegment *new = assegment_new (type, 0);
  1376. if (seg)
  1377. {
  1378. while (seg->next)
  1379. seg = seg->next;
  1380. seg->next = new;
  1381. }
  1382. else
  1383. as->segments = new;
  1384. }
  1385. struct aspath *
  1386. aspath_empty (void)
  1387. {
  1388. return aspath_parse (NULL, 0, 1); /* 32Bit ;-) */
  1389. }
  1390. struct aspath *
  1391. aspath_empty_get (void)
  1392. {
  1393. struct aspath *aspath;
  1394. aspath = aspath_new ();
  1395. aspath_make_str_count (aspath);
  1396. return aspath;
  1397. }
  1398. unsigned long
  1399. aspath_count (void)
  1400. {
  1401. return ashash->count;
  1402. }
  1403. /*
  1404. Theoretically, one as path can have:
  1405. One BGP packet size should be less than 4096.
  1406. One BGP attribute size should be less than 4096 - BGP header size.
  1407. One BGP aspath size should be less than 4096 - BGP header size -
  1408. BGP mandantry attribute size.
  1409. */
  1410. /* AS path string lexical token enum. */
  1411. enum as_token
  1412. {
  1413. as_token_asval,
  1414. as_token_set_start,
  1415. as_token_set_end,
  1416. as_token_confed_seq_start,
  1417. as_token_confed_seq_end,
  1418. as_token_confed_set_start,
  1419. as_token_confed_set_end,
  1420. as_token_unknown
  1421. };
  1422. /* Return next token and point for string parse. */
  1423. static const char *
  1424. aspath_gettoken (const char *buf, enum as_token *token, u_long *asno)
  1425. {
  1426. const char *p = buf;
  1427. /* Skip seperators (space for sequences, ',' for sets). */
  1428. while (isspace ((int) *p) || *p == ',')
  1429. p++;
  1430. /* Check the end of the string and type specify characters
  1431. (e.g. {}()). */
  1432. switch (*p)
  1433. {
  1434. case '\0':
  1435. return NULL;
  1436. case '{':
  1437. *token = as_token_set_start;
  1438. p++;
  1439. return p;
  1440. case '}':
  1441. *token = as_token_set_end;
  1442. p++;
  1443. return p;
  1444. case '(':
  1445. *token = as_token_confed_seq_start;
  1446. p++;
  1447. return p;
  1448. case ')':
  1449. *token = as_token_confed_seq_end;
  1450. p++;
  1451. return p;
  1452. case '[':
  1453. *token = as_token_confed_set_start;
  1454. p++;
  1455. return p;
  1456. case ']':
  1457. *token = as_token_confed_set_end;
  1458. p++;
  1459. return p;
  1460. }
  1461. /* Check actual AS value. */
  1462. if (isdigit ((int) *p))
  1463. {
  1464. as_t asval;
  1465. *token = as_token_asval;
  1466. asval = (*p - '0');
  1467. p++;
  1468. while (isdigit ((int) *p))
  1469. {
  1470. asval *= 10;
  1471. asval += (*p - '0');
  1472. p++;
  1473. }
  1474. *asno = asval;
  1475. return p;
  1476. }
  1477. /* There is no match then return unknown token. */
  1478. *token = as_token_unknown;
  1479. return p++;
  1480. }
  1481. struct aspath *
  1482. aspath_str2aspath (const char *str)
  1483. {
  1484. enum as_token token = as_token_unknown;
  1485. u_short as_type;
  1486. u_long asno = 0;
  1487. struct aspath *aspath;
  1488. int needtype;
  1489. aspath = aspath_new ();
  1490. /* We start default type as AS_SEQUENCE. */
  1491. as_type = AS_SEQUENCE;
  1492. needtype = 1;
  1493. while ((str = aspath_gettoken (str, &token, &asno)) != NULL)
  1494. {
  1495. switch (token)
  1496. {
  1497. case as_token_asval:
  1498. if (needtype)
  1499. {
  1500. aspath_segment_add (aspath, as_type);
  1501. needtype = 0;
  1502. }
  1503. aspath_as_add (aspath, asno);
  1504. break;
  1505. case as_token_set_start:
  1506. as_type = AS_SET;
  1507. aspath_segment_add (aspath, as_type);
  1508. needtype = 0;
  1509. break;
  1510. case as_token_set_end:
  1511. as_type = AS_SEQUENCE;
  1512. needtype = 1;
  1513. break;
  1514. case as_token_confed_seq_start:
  1515. as_type = AS_CONFED_SEQUENCE;
  1516. aspath_segment_add (aspath, as_type);
  1517. needtype = 0;
  1518. break;
  1519. case as_token_confed_seq_end:
  1520. as_type = AS_SEQUENCE;
  1521. needtype = 1;
  1522. break;
  1523. case as_token_confed_set_start:
  1524. as_type = AS_CONFED_SET;
  1525. aspath_segment_add (aspath, as_type);
  1526. needtype = 0;
  1527. break;
  1528. case as_token_confed_set_end:
  1529. as_type = AS_SEQUENCE;
  1530. needtype = 1;
  1531. break;
  1532. case as_token_unknown:
  1533. default:
  1534. aspath_free (aspath);
  1535. return NULL;
  1536. }
  1537. }
  1538. aspath_make_str_count (aspath);
  1539. return aspath;
  1540. }
  1541. /* Make hash value by raw aspath data. */
  1542. unsigned int
  1543. aspath_key_make (void *p)
  1544. {
  1545. struct aspath *aspath = (struct aspath *) p;
  1546. unsigned int key = 0;
  1547. if (!aspath->str)
  1548. aspath_str_update (aspath);
  1549. key = jhash (aspath->str, aspath->str_len, 2334325);
  1550. return key;
  1551. }
  1552. /* If two aspath have same value then return 1 else return 0 */
  1553. int
  1554. aspath_cmp (const void *arg1, const void *arg2)
  1555. {
  1556. const struct assegment *seg1 = ((const struct aspath *)arg1)->segments;
  1557. const struct assegment *seg2 = ((const struct aspath *)arg2)->segments;
  1558. while (seg1 || seg2)
  1559. {
  1560. int i;
  1561. if ((!seg1 && seg2) || (seg1 && !seg2))
  1562. return 0;
  1563. if (seg1->type != seg2->type)
  1564. return 0;
  1565. if (seg1->length != seg2->length)
  1566. return 0;
  1567. for (i = 0; i < seg1->length; i++)
  1568. if (seg1->as[i] != seg2->as[i])
  1569. return 0;
  1570. seg1 = seg1->next;
  1571. seg2 = seg2->next;
  1572. }
  1573. return 1;
  1574. }
  1575. /* AS path hash initialize. */
  1576. void
  1577. aspath_init (void)
  1578. {
  1579. ashash = hash_create_size (32768, aspath_key_make, aspath_cmp);
  1580. }
  1581. void
  1582. aspath_finish (void)
  1583. {
  1584. hash_clean (ashash, (void (*)(void *))aspath_free);
  1585. hash_free (ashash);
  1586. ashash = NULL;
  1587. if (snmp_stream)
  1588. stream_free (snmp_stream);
  1589. }
  1590. /* return and as path value */
  1591. const char *
  1592. aspath_print (struct aspath *as)
  1593. {
  1594. return (as ? as->str : NULL);
  1595. }
  1596. /* Printing functions */
  1597. /* Feed the AS_PATH to the vty; the suffix string follows it only in case
  1598. * AS_PATH wasn't empty.
  1599. */
  1600. void
  1601. aspath_print_vty (struct vty *vty, const char *format, struct aspath *as, const char * suffix)
  1602. {
  1603. assert (format);
  1604. vty_out (vty, format, as->str);
  1605. if (as->str_len && strlen (suffix))
  1606. vty_out (vty, "%s", suffix);
  1607. }
  1608. static void
  1609. aspath_show_all_iterator (struct hash_backet *backet, struct vty *vty)
  1610. {
  1611. struct aspath *as;
  1612. as = (struct aspath *) backet->data;
  1613. vty_out (vty, "[%p:%u] (%ld) ", (void *)backet, backet->key, as->refcnt);
  1614. vty_out (vty, "%s%s", as->str, VTY_NEWLINE);
  1615. }
  1616. /* Print all aspath and hash information. This function is used from
  1617. `show ip bgp paths' command. */
  1618. void
  1619. aspath_print_all_vty (struct vty *vty)
  1620. {
  1621. hash_iterate (ashash,
  1622. (void (*) (struct hash_backet *, void *))
  1623. aspath_show_all_iterator,
  1624. vty);
  1625. }