bgp_aspath.c 50 KB

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