bgp_aspath.c 26 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196
  1. /* AS path management routines.
  2. Copyright (C) 1996, 97, 98, 99 Kunihiro Ishiguro
  3. This file is part of GNU Zebra.
  4. GNU Zebra is free software; you can redistribute it and/or modify it
  5. under the terms of the GNU General Public License as published by the
  6. Free Software Foundation; either version 2, or (at your option) any
  7. later version.
  8. GNU Zebra is distributed in the hope that it will be useful, but
  9. WITHOUT ANY WARRANTY; without even the implied warranty of
  10. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  11. General Public License for more details.
  12. You should have received a copy of the GNU General Public License
  13. along with GNU Zebra; see the file COPYING. If not, write to the Free
  14. Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  15. 02111-1307, USA. */
  16. #include <zebra.h>
  17. #include "hash.h"
  18. #include "memory.h"
  19. #include "vector.h"
  20. #include "vty.h"
  21. #include "str.h"
  22. #include "log.h"
  23. #include "bgpd/bgpd.h"
  24. #include "bgpd/bgp_aspath.h"
  25. /* Attr. Flags and Attr. Type Code. */
  26. #define AS_HEADER_SIZE 2
  27. /* Two octet is used for AS value. */
  28. #define AS_VALUE_SIZE sizeof (as_t)
  29. /* AS segment octet length. */
  30. #define ASSEGMENT_LEN(X) ((X)->length * AS_VALUE_SIZE + AS_HEADER_SIZE)
  31. /* To fetch and store as segment value. */
  32. struct assegment
  33. {
  34. u_char type;
  35. u_char length;
  36. as_t asval[1];
  37. };
  38. /* Hash for aspath. This is the top level structure of AS path. */
  39. struct hash *ashash;
  40. static struct aspath *
  41. aspath_new ()
  42. {
  43. struct aspath *aspath;
  44. aspath = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
  45. memset (aspath, 0, sizeof (struct aspath));
  46. return aspath;
  47. }
  48. /* Free AS path structure. */
  49. void
  50. aspath_free (struct aspath *aspath)
  51. {
  52. if (!aspath)
  53. return;
  54. if (aspath->data)
  55. XFREE (MTYPE_AS_SEG, aspath->data);
  56. if (aspath->str)
  57. XFREE (MTYPE_AS_STR, aspath->str);
  58. XFREE (MTYPE_AS_PATH, aspath);
  59. }
  60. /* Unintern aspath from AS path bucket. */
  61. void
  62. aspath_unintern (struct aspath *aspath)
  63. {
  64. struct aspath *ret;
  65. if (aspath->refcnt)
  66. aspath->refcnt--;
  67. if (aspath->refcnt == 0)
  68. {
  69. /* This aspath must exist in aspath hash table. */
  70. ret = hash_release (ashash, aspath);
  71. assert (ret != NULL);
  72. aspath_free (aspath);
  73. }
  74. }
  75. /* Return the start or end delimiters for a particular Segment type */
  76. #define AS_SEG_START 0
  77. #define AS_SEG_END 1
  78. static char
  79. aspath_delimiter_char (u_char type, u_char which)
  80. {
  81. int i;
  82. struct
  83. {
  84. int type;
  85. char start;
  86. char end;
  87. } aspath_delim_char [] =
  88. {
  89. { AS_SET, '{', '}' },
  90. { AS_SEQUENCE, ' ', ' ' },
  91. { AS_CONFED_SET, '[', ']' },
  92. { AS_CONFED_SEQUENCE, '(', ')' },
  93. { 0 }
  94. };
  95. for (i = 0; aspath_delim_char[i].type != 0; i++)
  96. {
  97. if (aspath_delim_char[i].type == type)
  98. {
  99. if (which == AS_SEG_START)
  100. return aspath_delim_char[i].start;
  101. else if (which == AS_SEG_END)
  102. return aspath_delim_char[i].end;
  103. }
  104. }
  105. return ' ';
  106. }
  107. /* Convert aspath structure to string expression. */
  108. static char *
  109. aspath_make_str_count (struct aspath *as)
  110. {
  111. int space;
  112. u_char type;
  113. caddr_t pnt;
  114. caddr_t end;
  115. struct assegment *assegment;
  116. int str_size = ASPATH_STR_DEFAULT_LEN;
  117. int str_pnt;
  118. char *str_buf;
  119. int count = 0;
  120. int confed_count = 0;
  121. /* Empty aspath. */
  122. if (as->length == 0)
  123. {
  124. str_buf = XMALLOC (MTYPE_AS_STR, 1);
  125. str_buf[0] = '\0';
  126. as->count = count;
  127. as->confed_count = confed_count;
  128. return str_buf;
  129. }
  130. /* Set default value. */
  131. space = 0;
  132. type = AS_SEQUENCE;
  133. /* Set initial pointer. */
  134. pnt = as->data;
  135. end = pnt + as->length;
  136. str_buf = XMALLOC (MTYPE_AS_STR, str_size);
  137. str_pnt = 0;
  138. assegment = (struct assegment *) pnt;
  139. while (pnt < end)
  140. {
  141. int i;
  142. int estimate_len;
  143. /* For fetch value. */
  144. assegment = (struct assegment *) pnt;
  145. /* Check AS type validity. */
  146. if ((assegment->type != AS_SET) &&
  147. (assegment->type != AS_SEQUENCE) &&
  148. (assegment->type != AS_CONFED_SET) &&
  149. (assegment->type != AS_CONFED_SEQUENCE))
  150. {
  151. XFREE (MTYPE_AS_STR, str_buf);
  152. return NULL;
  153. }
  154. /* Check AS length. */
  155. if ((pnt + (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE) > end)
  156. {
  157. XFREE (MTYPE_AS_STR, str_buf);
  158. return NULL;
  159. }
  160. /* Buffer length check. */
  161. estimate_len = ((assegment->length * 6) + 4);
  162. /* String length check. */
  163. while (str_pnt + estimate_len >= str_size)
  164. {
  165. str_size *= 2;
  166. str_buf = XREALLOC (MTYPE_AS_STR, str_buf, str_size);
  167. }
  168. /* If assegment type is changed, print previous type's end
  169. character. */
  170. if (type != AS_SEQUENCE)
  171. str_buf[str_pnt++] = aspath_delimiter_char (type, AS_SEG_END);
  172. if (space)
  173. str_buf[str_pnt++] = ' ';
  174. if (assegment->type != AS_SEQUENCE)
  175. str_buf[str_pnt++] = aspath_delimiter_char (assegment->type, AS_SEG_START);
  176. space = 0;
  177. /* Increment counts */
  178. switch (assegment->type)
  179. {
  180. case AS_SEQUENCE:
  181. count += assegment->length;
  182. break;
  183. case AS_SET:
  184. count++;
  185. break;
  186. case AS_CONFED_SEQUENCE:
  187. confed_count += assegment->length;
  188. break;
  189. case AS_CONFED_SET:
  190. confed_count++;
  191. break;
  192. }
  193. for (i = 0; i < assegment->length; i++)
  194. {
  195. int len;
  196. if (space)
  197. {
  198. if (assegment->type == AS_SET
  199. || assegment->type == AS_CONFED_SET)
  200. str_buf[str_pnt++] = ',';
  201. else
  202. str_buf[str_pnt++] = ' ';
  203. }
  204. else
  205. space = 1;
  206. len = sprintf (str_buf + str_pnt, "%d", ntohs (assegment->asval[i]));
  207. str_pnt += len;
  208. }
  209. type = assegment->type;
  210. pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE;
  211. }
  212. if (assegment->type != AS_SEQUENCE)
  213. str_buf[str_pnt++] = aspath_delimiter_char (assegment->type, AS_SEG_END);
  214. str_buf[str_pnt] = '\0';
  215. as->count = count;
  216. as->confed_count = confed_count;
  217. return str_buf;
  218. }
  219. /* Intern allocated AS path. */
  220. struct aspath *
  221. aspath_intern (struct aspath *aspath)
  222. {
  223. struct aspath *find;
  224. /* Assert this AS path structure is not interned. */
  225. assert (aspath->refcnt == 0);
  226. /* Check AS path hash. */
  227. find = hash_get (ashash, aspath, hash_alloc_intern);
  228. if (find != aspath)
  229. aspath_free (aspath);
  230. find->refcnt++;
  231. if (! find->str)
  232. find->str = aspath_make_str_count (find);
  233. return find;
  234. }
  235. /* Duplicate aspath structure. Created same aspath structure but
  236. reference count and AS path string is cleared. */
  237. struct aspath *
  238. aspath_dup (struct aspath *aspath)
  239. {
  240. struct aspath *new;
  241. new = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
  242. memset (new, 0, sizeof (struct aspath));
  243. new->length = aspath->length;
  244. if (new->length)
  245. {
  246. new->data = XMALLOC (MTYPE_AS_SEG, aspath->length);
  247. memcpy (new->data, aspath->data, aspath->length);
  248. }
  249. else
  250. new->data = NULL;
  251. /* new->str = aspath_make_str_count (aspath); */
  252. return new;
  253. }
  254. static void *
  255. aspath_hash_alloc (struct aspath *arg)
  256. {
  257. struct aspath *aspath;
  258. /* New aspath strucutre is needed. */
  259. aspath = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
  260. memset ((void *) aspath, 0, sizeof (struct aspath));
  261. aspath->length = arg->length;
  262. /* In case of IBGP connection aspath's length can be zero. */
  263. if (arg->length)
  264. {
  265. aspath->data = XMALLOC (MTYPE_AS_SEG, arg->length);
  266. memcpy (aspath->data, arg->data, arg->length);
  267. }
  268. else
  269. aspath->data = NULL;
  270. /* Make AS path string. */
  271. aspath->str = aspath_make_str_count (aspath);
  272. /* Malformed AS path value. */
  273. if (! aspath->str)
  274. {
  275. aspath_free (aspath);
  276. return NULL;
  277. }
  278. return aspath;
  279. }
  280. /* AS path parse function. pnt is a pointer to byte stream and length
  281. is length of byte stream. If there is same AS path in the the AS
  282. path hash then return it else make new AS path structure. */
  283. struct aspath *
  284. aspath_parse (caddr_t pnt, int length)
  285. {
  286. struct aspath as;
  287. struct aspath *find;
  288. /* If length is odd it's malformed AS path. */
  289. if (length % 2)
  290. return NULL;
  291. /* Looking up aspath hash entry. */
  292. as.data = pnt;
  293. as.length = length;
  294. /* If already same aspath exist then return it. */
  295. find = hash_get (ashash, &as, aspath_hash_alloc);
  296. if (! find)
  297. return NULL;
  298. find->refcnt++;
  299. return find;
  300. }
  301. #define min(A,B) ((A) < (B) ? (A) : (B))
  302. #define ASSEGMENT_SIZE(N) (AS_HEADER_SIZE + ((N) * AS_VALUE_SIZE))
  303. static struct aspath *
  304. aspath_aggregate_segment_copy (struct aspath *aspath, struct assegment *seg,
  305. int i)
  306. {
  307. struct assegment *newseg;
  308. if (! aspath->data)
  309. {
  310. aspath->data = XMALLOC (MTYPE_AS_SEG, ASSEGMENT_SIZE (i));
  311. newseg = (struct assegment *) aspath->data;
  312. aspath->length = ASSEGMENT_SIZE (i);
  313. }
  314. else
  315. {
  316. aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data,
  317. aspath->length + ASSEGMENT_SIZE (i));
  318. newseg = (struct assegment *) (aspath->data + aspath->length);
  319. aspath->length += ASSEGMENT_SIZE (i);
  320. }
  321. newseg->type = seg->type;
  322. newseg->length = i;
  323. memcpy (newseg->asval, seg->asval, (i * AS_VALUE_SIZE));
  324. return aspath;
  325. }
  326. static struct assegment *
  327. aspath_aggregate_as_set_add (struct aspath *aspath, struct assegment *asset,
  328. as_t as)
  329. {
  330. int i;
  331. /* If this is first AS set member, create new as-set segment. */
  332. if (asset == NULL)
  333. {
  334. if (! aspath->data)
  335. {
  336. aspath->data = XMALLOC (MTYPE_AS_SEG, ASSEGMENT_SIZE (1));
  337. asset = (struct assegment *) aspath->data;
  338. aspath->length = ASSEGMENT_SIZE (1);
  339. }
  340. else
  341. {
  342. aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data,
  343. aspath->length + ASSEGMENT_SIZE (1));
  344. asset = (struct assegment *) (aspath->data + aspath->length);
  345. aspath->length += ASSEGMENT_SIZE (1);
  346. }
  347. asset->type = AS_SET;
  348. asset->length = 1;
  349. asset->asval[0] = as;
  350. }
  351. else
  352. {
  353. size_t offset;
  354. /* Check this AS value already exists or not. */
  355. for (i = 0; i < asset->length; i++)
  356. if (asset->asval[i] == as)
  357. return asset;
  358. offset = (caddr_t) asset - (caddr_t) aspath->data;
  359. aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data,
  360. aspath->length + AS_VALUE_SIZE);
  361. asset = (struct assegment *) (aspath->data + offset);
  362. aspath->length += AS_VALUE_SIZE;
  363. asset->asval[asset->length] = as;
  364. asset->length++;
  365. }
  366. return asset;
  367. }
  368. /* Modify as1 using as2 for aggregation. */
  369. struct aspath *
  370. aspath_aggregate (struct aspath *as1, struct aspath *as2)
  371. {
  372. int i;
  373. int minlen;
  374. int match;
  375. int match1;
  376. int match2;
  377. caddr_t cp1;
  378. caddr_t cp2;
  379. caddr_t end1;
  380. caddr_t end2;
  381. struct assegment *seg1;
  382. struct assegment *seg2;
  383. struct aspath *aspath;
  384. struct assegment *asset;
  385. match = 0;
  386. minlen = 0;
  387. aspath = NULL;
  388. asset = NULL;
  389. cp1 = as1->data;
  390. end1 = as1->data + as1->length;
  391. cp2 = as2->data;
  392. end2 = as2->data + as2->length;
  393. seg1 = (struct assegment *) cp1;
  394. seg2 = (struct assegment *) cp2;
  395. /* First of all check common leading sequence. */
  396. while ((cp1 < end1) && (cp2 < end2))
  397. {
  398. /* Check segment type. */
  399. if (seg1->type != seg2->type)
  400. break;
  401. /* Minimum segment length. */
  402. minlen = min (seg1->length, seg2->length);
  403. for (match = 0; match < minlen; match++)
  404. if (seg1->asval[match] != seg2->asval[match])
  405. break;
  406. if (match)
  407. {
  408. if (! aspath)
  409. aspath = aspath_new();
  410. aspath = aspath_aggregate_segment_copy (aspath, seg1, match);
  411. }
  412. if (match != minlen || match != seg1->length
  413. || seg1->length != seg2->length)
  414. break;
  415. cp1 += ((seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
  416. cp2 += ((seg2->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
  417. seg1 = (struct assegment *) cp1;
  418. seg2 = (struct assegment *) cp2;
  419. }
  420. if (! aspath)
  421. aspath = aspath_new();
  422. /* Make as-set using rest of all information. */
  423. match1 = match;
  424. while (cp1 < end1)
  425. {
  426. seg1 = (struct assegment *) cp1;
  427. for (i = match1; i < seg1->length; i++)
  428. asset = aspath_aggregate_as_set_add (aspath, asset, seg1->asval[i]);
  429. match1 = 0;
  430. cp1 += ((seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
  431. }
  432. match2 = match;
  433. while (cp2 < end2)
  434. {
  435. seg2 = (struct assegment *) cp2;
  436. for (i = match2; i < seg2->length; i++)
  437. asset = aspath_aggregate_as_set_add (aspath, asset, seg2->asval[i]);
  438. match2 = 0;
  439. cp2 += ((seg2->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
  440. }
  441. return aspath;
  442. }
  443. /* When a BGP router receives an UPDATE with an MP_REACH_NLRI
  444. attribute, check the leftmost AS number in the AS_PATH attribute is
  445. or not the peer's AS number. */
  446. int
  447. aspath_firstas_check (struct aspath *aspath, as_t asno)
  448. {
  449. caddr_t pnt;
  450. struct assegment *assegment;
  451. if (aspath == NULL)
  452. return 0;
  453. pnt = aspath->data;
  454. assegment = (struct assegment *) pnt;
  455. if (assegment
  456. && assegment->type == AS_SEQUENCE
  457. && assegment->asval[0] == htons (asno))
  458. return 1;
  459. return 0;
  460. }
  461. /* AS path loop check. If aspath contains asno then return 1. */
  462. int
  463. aspath_loop_check (struct aspath *aspath, as_t asno)
  464. {
  465. caddr_t pnt;
  466. caddr_t end;
  467. struct assegment *assegment;
  468. int count = 0;
  469. if (aspath == NULL)
  470. return 0;
  471. pnt = aspath->data;
  472. end = aspath->data + aspath->length;
  473. while (pnt < end)
  474. {
  475. int i;
  476. assegment = (struct assegment *) pnt;
  477. for (i = 0; i < assegment->length; i++)
  478. if (assegment->asval[i] == htons (asno))
  479. count++;
  480. pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE;
  481. }
  482. return count;
  483. }
  484. /* When all of AS path is private AS return 1. */
  485. int
  486. aspath_private_as_check (struct aspath *aspath)
  487. {
  488. caddr_t pnt;
  489. caddr_t end;
  490. struct assegment *assegment;
  491. if (aspath == NULL)
  492. return 0;
  493. if (aspath->length == 0)
  494. return 0;
  495. pnt = aspath->data;
  496. end = aspath->data + aspath->length;
  497. while (pnt < end)
  498. {
  499. int i;
  500. assegment = (struct assegment *) pnt;
  501. for (i = 0; i < assegment->length; i++)
  502. {
  503. if (ntohs (assegment->asval[i]) < BGP_PRIVATE_AS_MIN
  504. || ntohs (assegment->asval[i]) > BGP_PRIVATE_AS_MAX)
  505. return 0;
  506. }
  507. pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE;
  508. }
  509. return 1;
  510. }
  511. /* Merge as1 to as2. as2 should be uninterned aspath. */
  512. static struct aspath *
  513. aspath_merge (struct aspath *as1, struct aspath *as2)
  514. {
  515. caddr_t data;
  516. if (! as1 || ! as2)
  517. return NULL;
  518. data = XMALLOC (MTYPE_AS_SEG, as1->length + as2->length);
  519. memcpy (data, as1->data, as1->length);
  520. memcpy (data + as1->length, as2->data, as2->length);
  521. XFREE (MTYPE_AS_SEG, as2->data);
  522. as2->data = data;
  523. as2->length += as1->length;
  524. as2->count += as1->count;
  525. return as2;
  526. }
  527. /* Prepend as1 to as2. as2 should be uninterned aspath. */
  528. struct aspath *
  529. aspath_prepend (struct aspath *as1, struct aspath *as2)
  530. {
  531. caddr_t pnt;
  532. caddr_t end;
  533. struct assegment *seg1 = NULL;
  534. struct assegment *seg2 = NULL;
  535. if (! as1 || ! as2)
  536. return NULL;
  537. seg2 = (struct assegment *) as2->data;
  538. /* In case of as2 is empty AS. */
  539. if (seg2 == NULL)
  540. {
  541. as2->length = as1->length;
  542. as2->data = XMALLOC (MTYPE_AS_SEG, as1->length);
  543. as2->count = as1->count;
  544. memcpy (as2->data, as1->data, as1->length);
  545. return as2;
  546. }
  547. /* assegment points last segment of as1. */
  548. pnt = as1->data;
  549. end = as1->data + as1->length;
  550. while (pnt < end)
  551. {
  552. seg1 = (struct assegment *) pnt;
  553. pnt += (seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE;
  554. }
  555. /* In case of as1 is empty AS. */
  556. if (seg1 == NULL)
  557. return as2;
  558. /* Compare last segment type of as1 and first segment type of as2. */
  559. if (seg1->type != seg2->type)
  560. return aspath_merge (as1, as2);
  561. if (seg1->type == AS_SEQUENCE)
  562. {
  563. caddr_t newdata;
  564. struct assegment *seg = NULL;
  565. newdata = XMALLOC (MTYPE_AS_SEG,
  566. as1->length + as2->length - AS_HEADER_SIZE);
  567. memcpy (newdata, as1->data, as1->length);
  568. seg = (struct assegment *) (newdata + ((caddr_t)seg1 - as1->data));
  569. seg->length += seg2->length;
  570. memcpy (newdata + as1->length, as2->data + AS_HEADER_SIZE,
  571. as2->length - AS_HEADER_SIZE);
  572. XFREE (MTYPE_AS_SEG, as2->data);
  573. as2->data = newdata;
  574. as2->length += (as1->length - AS_HEADER_SIZE);
  575. as2->count += as1->count;
  576. return as2;
  577. }
  578. else
  579. {
  580. /* AS_SET merge code is needed at here. */
  581. return aspath_merge (as1, as2);
  582. }
  583. /* Not reached */
  584. }
  585. /* Add specified AS to the leftmost of aspath. */
  586. static struct aspath *
  587. aspath_add_one_as (struct aspath *aspath, as_t asno, u_char type)
  588. {
  589. struct assegment *assegment;
  590. assegment = (struct assegment *) aspath->data;
  591. /* In case of empty aspath. */
  592. if (assegment == NULL || assegment->length == 0)
  593. {
  594. aspath->length = AS_HEADER_SIZE + AS_VALUE_SIZE;
  595. if (assegment)
  596. aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data, aspath->length);
  597. else
  598. aspath->data = XMALLOC (MTYPE_AS_SEG, aspath->length);
  599. assegment = (struct assegment *) aspath->data;
  600. assegment->type = type;
  601. assegment->length = 1;
  602. assegment->asval[0] = htons (asno);
  603. return aspath;
  604. }
  605. if (assegment->type == type)
  606. {
  607. caddr_t newdata;
  608. struct assegment *newsegment;
  609. newdata = XMALLOC (MTYPE_AS_SEG, aspath->length + AS_VALUE_SIZE);
  610. newsegment = (struct assegment *) newdata;
  611. newsegment->type = type;
  612. newsegment->length = assegment->length + 1;
  613. newsegment->asval[0] = htons (asno);
  614. memcpy (newdata + AS_HEADER_SIZE + AS_VALUE_SIZE,
  615. aspath->data + AS_HEADER_SIZE,
  616. aspath->length - AS_HEADER_SIZE);
  617. XFREE (MTYPE_AS_SEG, aspath->data);
  618. aspath->data = newdata;
  619. aspath->length += AS_VALUE_SIZE;
  620. } else {
  621. caddr_t newdata;
  622. struct assegment *newsegment;
  623. newdata = XMALLOC (MTYPE_AS_SEG, aspath->length + AS_VALUE_SIZE + AS_HEADER_SIZE);
  624. newsegment = (struct assegment *) newdata;
  625. newsegment->type = type;
  626. newsegment->length = 1;
  627. newsegment->asval[0] = htons (asno);
  628. memcpy (newdata + AS_HEADER_SIZE + AS_VALUE_SIZE,
  629. aspath->data,
  630. aspath->length);
  631. XFREE (MTYPE_AS_SEG, aspath->data);
  632. aspath->data = newdata;
  633. aspath->length += AS_HEADER_SIZE + AS_VALUE_SIZE;
  634. }
  635. return aspath;
  636. }
  637. /* Add specified AS to the leftmost of aspath. */
  638. struct aspath *
  639. aspath_add_seq (struct aspath *aspath, as_t asno)
  640. {
  641. return aspath_add_one_as (aspath, asno, AS_SEQUENCE);
  642. }
  643. /* Compare leftmost AS value for MED check. If as1's leftmost AS and
  644. as2's leftmost AS is same return 1. */
  645. int
  646. aspath_cmp_left (struct aspath *aspath1, struct aspath *aspath2)
  647. {
  648. struct assegment *seg1;
  649. struct assegment *seg2;
  650. as_t as1;
  651. as_t as2;
  652. seg1 = (struct assegment *) aspath1->data;
  653. seg2 = (struct assegment *) aspath2->data;
  654. while (seg1 && seg1->length
  655. && (seg1->type == AS_CONFED_SEQUENCE || seg1->type == AS_CONFED_SET))
  656. seg1 = (struct assegment *) ((caddr_t) seg1 + ASSEGMENT_LEN (seg1));
  657. while (seg2 && seg2->length
  658. && (seg2->type == AS_CONFED_SEQUENCE || seg2->type == AS_CONFED_SET))
  659. seg2 = (struct assegment *) ((caddr_t) seg2 + ASSEGMENT_LEN (seg2));
  660. /* Check as1's */
  661. if (seg1 == NULL || seg1->length == 0 || seg1->type != AS_SEQUENCE)
  662. return 0;
  663. as1 = seg1->asval[0];
  664. if (seg2 == NULL || seg2->length == 0 || seg2->type != AS_SEQUENCE)
  665. return 0;
  666. as2 = seg2->asval[0];
  667. if (as1 == as2)
  668. return 1;
  669. return 0;
  670. }
  671. /* Compare leftmost AS value for MED check. If as1's leftmost AS and
  672. as2's leftmost AS is same return 1. (confederation as-path
  673. only). */
  674. int
  675. aspath_cmp_left_confed (struct aspath *aspath1, struct aspath *aspath2)
  676. {
  677. struct assegment *seg1;
  678. struct assegment *seg2;
  679. as_t as1;
  680. as_t as2;
  681. if (aspath1->count || aspath2->count)
  682. return 0;
  683. seg1 = (struct assegment *) aspath1->data;
  684. seg2 = (struct assegment *) aspath2->data;
  685. /* Check as1's */
  686. if (seg1 == NULL || seg1->length == 0 || seg1->type != AS_CONFED_SEQUENCE)
  687. return 0;
  688. as1 = seg1->asval[0];
  689. /* Check as2's */
  690. if (seg2 == NULL || seg2->length == 0 || seg2->type != AS_CONFED_SEQUENCE)
  691. return 0;
  692. as2 = seg2->asval[0];
  693. if (as1 == as2)
  694. return 1;
  695. return 0;
  696. }
  697. /* Delete first sequential AS_CONFED_SEQUENCE from aspath. */
  698. struct aspath *
  699. aspath_delete_confed_seq (struct aspath *aspath)
  700. {
  701. int seglen;
  702. struct assegment *assegment;
  703. if (! aspath)
  704. return aspath;
  705. assegment = (struct assegment *) aspath->data;
  706. while (assegment)
  707. {
  708. if (assegment->type != AS_CONFED_SEQUENCE)
  709. return aspath;
  710. seglen = ASSEGMENT_LEN (assegment);
  711. if (seglen == aspath->length)
  712. {
  713. XFREE (MTYPE_AS_SEG, aspath->data);
  714. aspath->data = NULL;
  715. aspath->length = 0;
  716. }
  717. else
  718. {
  719. memcpy (aspath->data, aspath->data + seglen,
  720. aspath->length - seglen);
  721. aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data,
  722. aspath->length - seglen);
  723. aspath->length -= seglen;
  724. }
  725. assegment = (struct assegment *) aspath->data;
  726. }
  727. return aspath;
  728. }
  729. /* Add new AS number to the leftmost part of the aspath as
  730. AS_CONFED_SEQUENCE. */
  731. struct aspath*
  732. aspath_add_confed_seq (struct aspath *aspath, as_t asno)
  733. {
  734. return aspath_add_one_as (aspath, asno, AS_CONFED_SEQUENCE);
  735. }
  736. /* Add new as value to as path structure. */
  737. static void
  738. aspath_as_add (struct aspath *as, as_t asno)
  739. {
  740. caddr_t pnt;
  741. caddr_t end;
  742. struct assegment *assegment;
  743. /* Increase as->data for new as value. */
  744. as->data = XREALLOC (MTYPE_AS_SEG, as->data, as->length + 2);
  745. as->length += 2;
  746. pnt = as->data;
  747. end = as->data + as->length;
  748. assegment = (struct assegment *) pnt;
  749. /* Last segment search procedure. */
  750. while (pnt + 2 < end)
  751. {
  752. assegment = (struct assegment *) pnt;
  753. /* We add 2 for segment_type and segment_length and segment
  754. value assegment->length * 2. */
  755. pnt += (AS_HEADER_SIZE + (assegment->length * AS_VALUE_SIZE));
  756. }
  757. assegment->asval[assegment->length] = htons (asno);
  758. assegment->length++;
  759. }
  760. /* Add new as segment to the as path. */
  761. static void
  762. aspath_segment_add (struct aspath *as, int type)
  763. {
  764. struct assegment *assegment;
  765. if (as->data == NULL)
  766. {
  767. as->data = XMALLOC (MTYPE_AS_SEG, 2);
  768. assegment = (struct assegment *) as->data;
  769. as->length = 2;
  770. }
  771. else
  772. {
  773. as->data = XREALLOC (MTYPE_AS_SEG, as->data, as->length + 2);
  774. assegment = (struct assegment *) (as->data + as->length);
  775. as->length += 2;
  776. }
  777. assegment->type = type;
  778. assegment->length = 0;
  779. }
  780. struct aspath *
  781. aspath_empty (void)
  782. {
  783. return aspath_parse (NULL, 0);
  784. }
  785. struct aspath *
  786. aspath_empty_get (void)
  787. {
  788. struct aspath *aspath;
  789. aspath = aspath_new ();
  790. aspath->str = aspath_make_str_count (aspath);
  791. return aspath;
  792. }
  793. unsigned long
  794. aspath_count ()
  795. {
  796. return ashash->count;
  797. }
  798. /*
  799. Theoretically, one as path can have:
  800. One BGP packet size should be less than 4096.
  801. One BGP attribute size should be less than 4096 - BGP header size.
  802. One BGP aspath size should be less than 4096 - BGP header size -
  803. BGP mandantry attribute size.
  804. */
  805. /* AS path string lexical token enum. */
  806. enum as_token
  807. {
  808. as_token_asval,
  809. as_token_set_start,
  810. as_token_set_end,
  811. as_token_confed_start,
  812. as_token_confed_end,
  813. as_token_unknown
  814. };
  815. /* Return next token and point for string parse. */
  816. static const char *
  817. aspath_gettoken (const char *buf, enum as_token *token, u_short *asno)
  818. {
  819. const char *p = buf;
  820. /* Skip space. */
  821. while (isspace ((int) *p))
  822. p++;
  823. /* Check the end of the string and type specify characters
  824. (e.g. {}()). */
  825. switch (*p)
  826. {
  827. case '\0':
  828. return NULL;
  829. break;
  830. case '{':
  831. *token = as_token_set_start;
  832. p++;
  833. return p;
  834. break;
  835. case '}':
  836. *token = as_token_set_end;
  837. p++;
  838. return p;
  839. break;
  840. case '(':
  841. *token = as_token_confed_start;
  842. p++;
  843. return p;
  844. break;
  845. case ')':
  846. *token = as_token_confed_end;
  847. p++;
  848. return p;
  849. break;
  850. }
  851. /* Check actual AS value. */
  852. if (isdigit ((int) *p))
  853. {
  854. u_short asval;
  855. *token = as_token_asval;
  856. asval = (*p - '0');
  857. p++;
  858. while (isdigit ((int) *p))
  859. {
  860. asval *= 10;
  861. asval += (*p - '0');
  862. p++;
  863. }
  864. *asno = asval;
  865. return p;
  866. }
  867. /* There is no match then return unknown token. */
  868. *token = as_token_unknown;
  869. return p++;
  870. }
  871. struct aspath *
  872. aspath_str2aspath (const char *str)
  873. {
  874. enum as_token token;
  875. u_short as_type;
  876. u_short asno;
  877. struct aspath *aspath;
  878. int needtype;
  879. aspath = aspath_new ();
  880. /* We start default type as AS_SEQUENCE. */
  881. as_type = AS_SEQUENCE;
  882. needtype = 1;
  883. while ((str = aspath_gettoken (str, &token, &asno)) != NULL)
  884. {
  885. switch (token)
  886. {
  887. case as_token_asval:
  888. if (needtype)
  889. {
  890. aspath_segment_add (aspath, as_type);
  891. needtype = 0;
  892. }
  893. aspath_as_add (aspath, asno);
  894. break;
  895. case as_token_set_start:
  896. as_type = AS_SET;
  897. aspath_segment_add (aspath, as_type);
  898. needtype = 0;
  899. break;
  900. case as_token_set_end:
  901. as_type = AS_SEQUENCE;
  902. needtype = 1;
  903. break;
  904. case as_token_confed_start:
  905. as_type = AS_CONFED_SEQUENCE;
  906. aspath_segment_add (aspath, as_type);
  907. needtype = 0;
  908. break;
  909. case as_token_confed_end:
  910. as_type = AS_SEQUENCE;
  911. needtype = 1;
  912. break;
  913. case as_token_unknown:
  914. default:
  915. return NULL;
  916. break;
  917. }
  918. }
  919. aspath->str = aspath_make_str_count (aspath);
  920. return aspath;
  921. }
  922. /* Make hash value by raw aspath data. */
  923. unsigned int
  924. aspath_key_make (struct aspath *aspath)
  925. {
  926. unsigned int key = 0;
  927. int length;
  928. unsigned short *pnt;
  929. length = aspath->length / 2;
  930. pnt = (unsigned short *) aspath->data;
  931. while (length)
  932. {
  933. key += *pnt++;
  934. length--;
  935. }
  936. return key;
  937. }
  938. /* If two aspath have same value then return 1 else return 0 */
  939. static int
  940. aspath_cmp (struct aspath *as1, struct aspath *as2)
  941. {
  942. if (as1->length == as2->length
  943. && !memcmp (as1->data, as2->data, as1->length))
  944. return 1;
  945. else
  946. return 0;
  947. }
  948. /* AS path hash initialize. */
  949. void
  950. aspath_init (void)
  951. {
  952. ashash = hash_create_size (32767, aspath_key_make, aspath_cmp);
  953. }
  954. /* return and as path value */
  955. const char *
  956. aspath_print (struct aspath *as)
  957. {
  958. return as->str;
  959. }
  960. /* Printing functions */
  961. void
  962. aspath_print_vty (struct vty *vty, struct aspath *as)
  963. {
  964. vty_out (vty, "%s", as->str);
  965. }
  966. static void
  967. aspath_show_all_iterator (struct hash_backet *backet, struct vty *vty)
  968. {
  969. struct aspath *as;
  970. as = (struct aspath *) backet->data;
  971. vty_out (vty, "[%p:%u] (%ld) ", backet, backet->key, as->refcnt);
  972. vty_out (vty, "%s%s", as->str, VTY_NEWLINE);
  973. }
  974. /* Print all aspath and hash information. This function is used from
  975. `show ip bgp paths' command. */
  976. void
  977. aspath_print_all_vty (struct vty *vty)
  978. {
  979. hash_iterate (ashash,
  980. (void (*) (struct hash_backet *, void *))
  981. aspath_show_all_iterator,
  982. vty);
  983. }