bgp_aspath.c 46 KB

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