bgp_aspath.c 46 KB

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