bgp_aspath.c 47 KB

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