src/plugins/ioam/ip6/ioam_cache.h

   1 /*
   2  * Copyright (c) 2017 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 #ifndef __included_ioam_cache_h__
  16 #define __included_ioam_cache_h__
  17
  18 #include <vnet/vnet.h>
  19 #include <vnet/ip/ip.h>
  20 #include <vnet/ip/ip_packet.h>
  21 #include <vnet/ip/ip4_packet.h>
  22 #include <vnet/ip/ip6_packet.h>
  23 #include <vnet/srv6/sr.h>
  24
  25 #include <vppinfra/pool.h>
  26 #include <vppinfra/hash.h>
  27 #include <vppinfra/error.h>
  28 #include <vppinfra/elog.h>
  29 #include <vppinfra/bihash_8_8.h>
  30 #include <ioam/analyse/ip6/ip6_ioam_analyse.h>
  31 #include <vppinfra/tw_timer_16t_2w_512sl.h>
  32 /*
  33  * ioam_cache.h
  34  * This header contains routines for caching of ioam header and
  35  * buffer:
  36  * 1 - On application facing node: to cache ioam header recvd
  37  *     in request and reattach in response to provide round
  38  *     trip path visibility. Since request response matching
  39  *     is needed works with TCP and relies on (5 tuples,seq no)
  40  * 2 - On M-Anycast server node: This node replicates requests
  41  *    towards multiple anycast service nodes serving anycast
  42  *    IP6 address. It evaluates response and forwards the best
  43  *    response towards the client of requesting the service.
  44  *    Again since request-response matching is needed, works
  45  *    with TCP  and relies on (5 tuples,seq no) for matching.
  46  *    To do this it caches SYN-ACK responses for a short time to
  47  *    evaluate multiple responses received before the selected
  48  *    SYN-ACK response is forwared and others dropped.
  49  *
  50  * M-Anycast server cache:
  51  *   - There is a pool of cache entries per worker thread.
  52  *   - Cache entry is created when SYN is received expected
  53  *     number of responses are marked based on number of
  54  *     SR tunnels for the anycast destination address
  55  *   - The pool/thread id and pool index are attached in the
  56  *    message as an ioam option for quick look up.
  57  *   - When is received SYN-ACK the ioam option containing
  58  *     thread id + pool index of the cache entry is used to
  59  *     look up cache entry.
  60  *   - Cache synchronization:
  61  *      - This is achieved by cache entry add/del/update all handled
  62  *        by the same worker/main thread
  63  *      - Packets from client to threads - syn packets, can be disctributed
  64  *        based on incoming interface affinity to the cpu core pinned to
  65  *        the thread or a simple sequence number based distribution
  66  *        if thread per interface is not scaling
  67  *      - Response packets from server towards clients - syn-acks, are
  68  *        forced to the same thread that created the cache entry
  69  *        using SR and the destination of SR v6 address assigned
  70  *        to the core/thread. This adderss is sent as an ioam option
  71  *        in the syn that can be then used on the other side to
  72  *        populate v6 dst address in the response
  73  *      - Timeout: timer wheel per thread is used to track the syn-ack wait
  74  *        time. The timer wheel tick is updated via an input node per thread.
  75  *
  76  * Application facing node/Service side cache:
  77  *  - Single pool of cache entries.
  78  *  - Cache entry is created when SYN is received. Caches the ioam
  79  *    header. Hash table entry is created based on 5 tuple and
  80  *    TCP seq no to pool index
  81  *  - Response SYN-ACK processed by looking up pool index in hash table
  82  *    and cache entry in the pool is used to get the ioam header rewrite
  83  *    string. Entry is freed from pool and hash table after use.
  84  *  - Locking/Synchronization: Currently this functionality is deployed
  85  *    with main/single thread only. Hence no locking is used.
  86  *  - Deployment: A VPP node per application server servicing anycast
  87  *    address is expected. Locking/synchronization needed when the server
  88  *    /application facing node is started with multiple worker threads.
  89  *
  90  */
  91
  92 /*
  93  * Application facing server side caching:
  94  * Cache entry for ioam header
  95  * Currently caters to TCP and relies on
  96  * TCP - 5 tuples + seqno to cache and reinsert
  97  * ioam header b/n TCP request response
  98  */
  99 typedef struct
 100 {
 101   /** Required for pool_get_aligned */
 102   CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
 103   ip6_address_t src_address;
 104   ip6_address_t dst_address;
 105   u16 src_port;
 106   u16 dst_port;
 107   u8 protocol;
 108   u32 seq_no;
 109   ip6_address_t next_hop;
 110   u16 my_address_offset;
 111   u8 *ioam_rewrite_string;
 112 } ioam_cache_entry_t;
 113
 114 /*
 115  * Cache entry for anycast server selection
 116  * Works for TCP as 5 tuple + sequence number
 117  * is required for request response matching
 118  * max_responses expected is set based on number
 119  *              of SR tunnels for the dst_address
 120  * Timeout or all response_received = max_responses
 121  *            will clear the entry
 122  * buffer_index index of the response msg vlib buffer
 123  *           that is currently the best response
 124  */
 125 typedef struct
 126 {
 127   /** Required for pool_get_aligned */
 128   CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
 129   u32 pool_id;
 130   u32 pool_index;
 131   ip6_address_t src_address;
 132   ip6_address_t dst_address;
 133   u16 src_port;
 134   u16 dst_port;
 135   u8 protocol;
 136   u32 seq_no;
 137   u32 buffer_index;
 138   ip6_hop_by_hop_header_t *hbh; //pointer to hbh header in the buffer
 139   u64 created_at;
 140   u8 response_received;
 141   u8 max_responses;
 142   u32 stop_timer_handle;
 143   /** Handle returned from tw_start_timer */
 144   u32 timer_handle;
 145   /** entry should expire at this clock tick */
 146   u32 expected_to_expire;
 147 } ioam_cache_ts_entry_t;
 148
 149 /*
 150  * Per thread tunnel selection cache stats
 151  */
 152 typedef struct
 153 {
 154   u64 inuse;
 155   u64 add_failed;
 156 } ioam_cache_ts_pool_stats_t;
 157
 158 /* Server side: iOAM header caching */
 159 #define MAX_CACHE_ENTRIES 4096
 160 /* M-Anycast: Cache for SR tunnel selection */
 161 #define MAX_CACHE_TS_ENTRIES 1048576
 162
 163 #define IOAM_CACHE_TABLE_DEFAULT_HASH_NUM_BUCKETS (4 * 1024)
 164 #define IOAM_CACHE_TABLE_DEFAULT_HASH_MEMORY_SIZE (2<<20)
 165
 166 typedef struct
 167 {
 168   /* API message ID base */
 169   u16 msg_id_base;
 170
 171   /* Pool of ioam_cache_buffer_t */
 172   ioam_cache_entry_t *ioam_rewrite_pool;
 173
 174   /* For steering packets ioam cache entry is followed by
 175    * SR header. This is the SR rewrite template */
 176   u8 *sr_rewrite_template;
 177   /* The current rewrite string being used */
 178   u8 *rewrite;
 179   u8 rewrite_pool_index_offset;
 180   ip6_address_t sr_localsid_cache;
 181
 182   u64 lookup_table_nbuckets;
 183   u64 lookup_table_size;
 184   clib_bihash_8_8_t ioam_rewrite_cache_table;
 185
 186   /* M-Anycast: Pool of ioam_cache_ts_entry_t per thread */
 187   ioam_cache_ts_entry_t **ioam_ts_pool;
 188   ioam_cache_ts_pool_stats_t *ts_stats;
 189   /** per thread single-wheel */
 190   tw_timer_wheel_16t_2w_512sl_t *timer_wheels;
 191
 192   /*
 193    * Selection criteria: oneway delay: Server to M-Anycast
 194    * or RTT
 195    */
 196   bool criteria_oneway;
 197   u8 wait_for_responses;
 198   ip6_address_t sr_localsid_ts;
 199
 200   /* convenience */
 201   vlib_main_t *vlib_main;
 202
 203   uword cache_hbh_slot;
 204   uword ts_hbh_slot;
 205   u32 ip6_hbh_pop_node_index;
 206   u32 error_node_index;
 207   u32 cleanup_process_node_index;
 208 } ioam_cache_main_t;
 209
 210 extern ioam_cache_main_t ioam_cache_main;
 211
 212 extern vlib_node_registration_t ioam_cache_node;
 213 extern vlib_node_registration_t ioam_cache_ts_node;
 214
 215 /*  Compute flow hash.  We'll use it to select which Sponge to use for this
 216  *  flow.  And other things.
 217  *  ip6_compute_flow_hash in ip6.h doesnt locate tcp/udp when
 218  *  ext headers are present. While it could be made to it will be a
 219  *  performance hit for ECMP flows.
 220  *  HEnce this function here, with L4 information directly input
 221  *  Useful when tcp/udp headers are already located in presence of
 222  *  ext headers
 223  */
 224 always_inline u32
 225 ip6_compute_flow_hash_ext (const ip6_header_t * ip,
 226                            u8 protocol,
 227                            u16 src_port,
 228                            u16 dst_port, flow_hash_config_t flow_hash_config)
 229 {
 230   u64 a, b, c;
 231   u64 t1, t2;
 232
 233   t1 = (ip->src_address.as_u64[0] ^ ip->src_address.as_u64[1]);
 234   t1 = (flow_hash_config & IP_FLOW_HASH_SRC_ADDR) ? t1 : 0;
 235
 236   t2 = (ip->dst_address.as_u64[0] ^ ip->dst_address.as_u64[1]);
 237   t2 = (flow_hash_config & IP_FLOW_HASH_DST_ADDR) ? t2 : 0;
 238
 239   a = (flow_hash_config & IP_FLOW_HASH_REVERSE_SRC_DST) ? t2 : t1;
 240   b = (flow_hash_config & IP_FLOW_HASH_REVERSE_SRC_DST) ? t1 : t2;
 241   b ^= (flow_hash_config & IP_FLOW_HASH_PROTO) ? protocol : 0;
 242
 243   t1 = src_port;
 244   t2 = dst_port;
 245
 246   t1 = (flow_hash_config & IP_FLOW_HASH_SRC_PORT) ? t1 : 0;
 247   t2 = (flow_hash_config & IP_FLOW_HASH_DST_PORT) ? t2 : 0;
 248
 249   c = (flow_hash_config & IP_FLOW_HASH_REVERSE_SRC_DST) ?
 250     ((t1 << 16) | t2) : ((t2 << 16) | t1);
 251
 252   hash_mix64 (a, b, c);
 253   return (u32) c;
 254 }
 255
 256
 257 /* 2 new ioam E2E options :
 258  * 1. HBH_OPTION_TYPE_IOAM_EDGE_TO_EDGE_ID: IP6 address
 259  *                of ioam node that inserted ioam header
 260  * 2. HBH_OPTION_TYPE_IOAM_E2E_CACHE_ID: Pool id and index
 261  *                   to look up tunnel select cache entry
 262  */
 263 #define HBH_OPTION_TYPE_IOAM_EDGE_TO_EDGE_ID 30
 264 #define HBH_OPTION_TYPE_IOAM_E2E_CACHE_ID 31
 265
 266 typedef CLIB_PACKED (struct
 267                      {
 268                      ip6_hop_by_hop_option_t hdr; u8 e2e_type; u8 reserved[5];
 269                      ip6_address_t id;
 270                      }) ioam_e2e_id_option_t;
 271
 272 typedef CLIB_PACKED (struct
 273                      {
 274                      ip6_hop_by_hop_option_t hdr; u8 e2e_type; u8 pool_id;
 275                      u32 pool_index;
 276                      }) ioam_e2e_cache_option_t;
 277
 278 #define IOAM_E2E_ID_OPTION_RND ((sizeof(ioam_e2e_id_option_t) + 7) & ~7)
 279 #define IOAM_E2E_ID_HBH_EXT_LEN (IOAM_E2E_ID_OPTION_RND >> 3)
 280 #define IOAM_E2E_CACHE_OPTION_RND ((sizeof(ioam_e2e_cache_option_t) + 7) & ~7)
 281 #define IOAM_E2E_CACHE_HBH_EXT_LEN (IOAM_E2E_CACHE_OPTION_RND >> 3)
 282
 283 static inline void
 284 ioam_e2e_id_rewrite_handler (ioam_e2e_id_option_t * e2e_option,
 285                              ip6_address_t * address)
 286 {
 287   e2e_option->id.as_u64[0] = address->as_u64[0];
 288   e2e_option->id.as_u64[1] = address->as_u64[1];
 289
 290 }
 291
 292 /* Following functions are for the caching of ioam header
 293  * to enable reattaching it for a complete request-response
 294  * message exchange */
 295 inline static void
 296 ioam_cache_entry_free (ioam_cache_entry_t * entry)
 297 {
 298   ioam_cache_main_t *cm = &ioam_cache_main;
 299   if (entry)
 300     {
 301       vec_free (entry->ioam_rewrite_string);
 302       clib_memset (entry, 0, sizeof (*entry));
 303       pool_put (cm->ioam_rewrite_pool, entry);
 304     }
 305 }
 306
 307 inline static ioam_cache_entry_t *
 308 ioam_cache_entry_cleanup (u32 pool_index)
 309 {
 310   ioam_cache_main_t *cm = &ioam_cache_main;
 311   ioam_cache_entry_t *entry = 0;
 312
 313   entry = pool_elt_at_index (cm->ioam_rewrite_pool, pool_index);
 314   ioam_cache_entry_free (entry);
 315   return (0);
 316 }
 317
 318 inline static ioam_cache_entry_t *
 319 ioam_cache_lookup (ip6_header_t * ip0, u16 src_port, u16 dst_port, u32 seq_no)
 320 {
 321   ioam_cache_main_t *cm = &ioam_cache_main;
 322   u32 flow_hash = ip6_compute_flow_hash_ext (ip0, ip0->protocol,
 323                                              src_port, dst_port,
 324                                              IP_FLOW_HASH_DEFAULT |
 325                                              IP_FLOW_HASH_REVERSE_SRC_DST);
 326   clib_bihash_kv_8_8_t kv, value;
 327
 328   kv.key = (u64) flow_hash << 32 | seq_no;
 329   kv.value = 0;
 330   value.key = 0;
 331   value.value = 0;
 332
 333   if (clib_bihash_search_8_8 (&cm->ioam_rewrite_cache_table, &kv, &value) >=
 334       0)
 335     {
 336       ioam_cache_entry_t *entry = 0;
 337
 338       entry = pool_elt_at_index (cm->ioam_rewrite_pool, value.value);
 339       /* match */
 340       if (ip6_address_compare (&ip0->src_address, &entry->dst_address) == 0 &&
 341           ip6_address_compare (&ip0->dst_address, &entry->src_address) == 0 &&
 342           entry->src_port == dst_port &&
 343           entry->dst_port == src_port && entry->seq_no == seq_no)
 344         {
 345           /* If lookup is successful remove it from the hash */
 346           clib_bihash_add_del_8_8 (&cm->ioam_rewrite_cache_table, &kv, 0);
 347           return (entry);
 348         }
 349       else
 350         return (0);
 351
 352     }
 353   return (0);
 354 }
 355
 356 /*
 357  * Caches ioam hbh header
 358  * Extends the hbh header with option to contain IP6 address of the node
 359  * that caches it
 360  */
 361 inline static int
 362 ioam_cache_add (vlib_buffer_t * b0,
 363                 ip6_header_t * ip0,
 364                 u16 src_port,
 365                 u16 dst_port, ip6_hop_by_hop_header_t * hbh0, u32 seq_no)
 366 {
 367   ioam_cache_main_t *cm = &ioam_cache_main;
 368   ioam_cache_entry_t *entry = 0;
 369   u32 rewrite_len = 0, e2e_id_offset = 0;
 370   u32 pool_index = 0;
 371   ioam_e2e_id_option_t *e2e = 0;
 372
 373   pool_get_aligned (cm->ioam_rewrite_pool, entry, CLIB_CACHE_LINE_BYTES);
 374   clib_memset (entry, 0, sizeof (*entry));
 375   pool_index = entry - cm->ioam_rewrite_pool;
 376
 377   clib_memcpy (entry->dst_address.as_u64, ip0->dst_address.as_u64,
 378                sizeof (ip6_address_t));
 379   clib_memcpy (entry->src_address.as_u64, ip0->src_address.as_u64,
 380                sizeof (ip6_address_t));
 381   entry->src_port = src_port;
 382   entry->dst_port = dst_port;
 383   entry->seq_no = seq_no;
 384   rewrite_len = ((hbh0->length + 1) << 3);
 385   vec_validate (entry->ioam_rewrite_string, rewrite_len - 1);
 386   e2e = ip6_ioam_find_hbh_option (hbh0, HBH_OPTION_TYPE_IOAM_EDGE_TO_EDGE_ID);
 387   if (e2e)
 388     {
 389       entry->next_hop.as_u64[0] = e2e->id.as_u64[0];
 390       entry->next_hop.as_u64[1] = e2e->id.as_u64[1];
 391     }
 392   else
 393     {
 394       return (-1);
 395     }
 396   e2e_id_offset = (u8 *) e2e - (u8 *) hbh0;
 397   /* setup e2e id option to insert v6 address of the node caching it */
 398   clib_memcpy (entry->ioam_rewrite_string, hbh0, rewrite_len);
 399   hbh0 = (ip6_hop_by_hop_header_t *) entry->ioam_rewrite_string;
 400
 401   /* suffix rewrite string with e2e ID option */
 402   e2e = (ioam_e2e_id_option_t *) (entry->ioam_rewrite_string + e2e_id_offset);
 403   ioam_e2e_id_rewrite_handler (e2e, &cm->sr_localsid_cache);
 404   entry->my_address_offset = (u8 *) (&e2e->id) - (u8 *) hbh0;
 405
 406   /* add it to hash, replacing and freeing any collision for now */
 407   u32 flow_hash =
 408     ip6_compute_flow_hash_ext (ip0, hbh0->protocol, src_port, dst_port,
 409                                IP_FLOW_HASH_DEFAULT);
 410   clib_bihash_kv_8_8_t kv, value;
 411   kv.key = (u64) flow_hash << 32 | seq_no;
 412   kv.value = 0;
 413   if (clib_bihash_search_8_8 (&cm->ioam_rewrite_cache_table, &kv, &value) >=
 414       0)
 415     {
 416       /* replace */
 417       ioam_cache_entry_cleanup (value.value);
 418     }
 419   kv.value = pool_index;
 420   clib_bihash_add_del_8_8 (&cm->ioam_rewrite_cache_table, &kv, 1);
 421   return (0);
 422 }
 423
 424 /* Creates SR rewrite string
 425  * This is appended with ioam header on the server facing
 426  * node.
 427  * This SR header is necessary to attract packets towards
 428  * selected Anycast server.
 429  */
 430 inline static void
 431 ioam_cache_sr_rewrite_template_create (void)
 432 {
 433   ioam_cache_main_t *cm = &ioam_cache_main;
 434   ip6_address_t *segments = 0;
 435   ip6_address_t *this_seg = 0;
 436
 437   /* This nodes address and the original dest will be
 438    * filled when the packet is processed */
 439   vec_add2 (segments, this_seg, 1);
 440   clib_memset (this_seg, 0xfe, sizeof (ip6_address_t));
 441   cm->sr_rewrite_template = ip6_sr_compute_rewrite_string_insert (segments);
 442   vec_free (segments);
 443 }
 444
 445 inline static int
 446 ioam_cache_table_init (vlib_main_t * vm)
 447 {
 448   ioam_cache_main_t *cm = &ioam_cache_main;
 449
 450   pool_alloc_aligned (cm->ioam_rewrite_pool,
 451                       MAX_CACHE_ENTRIES, CLIB_CACHE_LINE_BYTES);
 452   cm->lookup_table_nbuckets = IOAM_CACHE_TABLE_DEFAULT_HASH_NUM_BUCKETS;
 453   cm->lookup_table_nbuckets = 1 << max_log2 (cm->lookup_table_nbuckets);
 454   cm->lookup_table_size = IOAM_CACHE_TABLE_DEFAULT_HASH_MEMORY_SIZE;
 455
 456   clib_bihash_init_8_8 (&cm->ioam_rewrite_cache_table,
 457                         "ioam rewrite cache table",
 458                         cm->lookup_table_nbuckets, cm->lookup_table_size);
 459   /* Create SR rewrite template */
 460   ioam_cache_sr_rewrite_template_create ();
 461   return (1);
 462 }
 463
 464 inline static int
 465 ioam_cache_table_destroy (vlib_main_t * vm)
 466 {
 467   ioam_cache_main_t *cm = &ioam_cache_main;
 468   ioam_cache_entry_t *entry = 0;
 469   /* free pool and hash table */
 470   clib_bihash_free_8_8 (&cm->ioam_rewrite_cache_table);
 471   pool_foreach (entry, cm->ioam_rewrite_pool, (
 472                                                 {
 473                                                 ioam_cache_entry_free (entry);
 474                                                 }));
 475   pool_free (cm->ioam_rewrite_pool);
 476   cm->ioam_rewrite_pool = 0;
 477   vec_free (cm->sr_rewrite_template);
 478   cm->sr_rewrite_template = 0;
 479   return (0);
 480 }
 481
 482 inline static u8 *
 483 format_ioam_cache_entry (u8 * s, va_list * args)
 484 {
 485   ioam_cache_entry_t *e = va_arg (*args, ioam_cache_entry_t *);
 486   ioam_cache_main_t *cm = &ioam_cache_main;
 487   int rewrite_len = vec_len (e->ioam_rewrite_string);
 488
 489   s = format (s, "%d: %U:%d to  %U:%d seq_no %lu\n",
 490               (e - cm->ioam_rewrite_pool),
 491               format_ip6_address, &e->src_address,
 492               e->src_port,
 493               format_ip6_address, &e->dst_address, e->dst_port, e->seq_no);
 494
 495   if (rewrite_len)
 496     {
 497       s = format (s, "  %U",
 498                   format_ip6_hop_by_hop_ext_hdr,
 499                   (ip6_hop_by_hop_header_t *) e->ioam_rewrite_string,
 500                   rewrite_len - 1);
 501     }
 502   return s;
 503 }
 504
 505 void ioam_cache_ts_timer_node_enable (vlib_main_t * vm, u8 enable);
 506
 507 #define IOAM_CACHE_TS_TIMEOUT 1.0       //SYN timeout 1 sec
 508 #define IOAM_CACHE_TS_TICK 100e-3
 509 /* Timer delays as multiples of 100ms */
 510 #define IOAM_CACHE_TS_TIMEOUT_TICKS IOAM_CACHE_TS_TICK*9
 511 #define TIMER_HANDLE_INVALID ((u32) ~0)
 512
 513
 514 void expired_cache_ts_timer_callback (u32 * expired_timers);
 515
 516 /*
 517  * Following functions are to manage M-Anycast server selection
 518  * cache
 519  * There is a per worker thread pool to create a cache entry
 520  * for a TCP SYN received. TCP SYN-ACK contians ioam header
 521  * with HBH_OPTION_TYPE_IOAM_E2E_CACHE_ID option to point to the
 522  * entry.
 523  */
 524 inline static int
 525 ioam_cache_ts_table_init (vlib_main_t * vm)
 526 {
 527   ioam_cache_main_t *cm = &ioam_cache_main;
 528   int no_of_threads = vec_len (vlib_worker_threads);
 529   int i;
 530
 531   vec_validate_aligned (cm->ioam_ts_pool, no_of_threads - 1,
 532                         CLIB_CACHE_LINE_BYTES);
 533   vec_validate_aligned (cm->ts_stats, no_of_threads - 1,
 534                         CLIB_CACHE_LINE_BYTES);
 535   vec_validate (cm->timer_wheels, no_of_threads - 1);
 536   cm->lookup_table_nbuckets = IOAM_CACHE_TABLE_DEFAULT_HASH_NUM_BUCKETS;
 537   cm->lookup_table_nbuckets = 1 << max_log2 (cm->lookup_table_nbuckets);
 538   cm->lookup_table_size = IOAM_CACHE_TABLE_DEFAULT_HASH_MEMORY_SIZE;
 539   for (i = 0; i < no_of_threads; i++)
 540     {
 541       pool_alloc_aligned (cm->ioam_ts_pool[i],
 542                           MAX_CACHE_TS_ENTRIES, CLIB_CACHE_LINE_BYTES);
 543       clib_memset (&cm->ts_stats[i], 0, sizeof (ioam_cache_ts_pool_stats_t));
 544       tw_timer_wheel_init_16t_2w_512sl (&cm->timer_wheels[i],
 545                                         expired_cache_ts_timer_callback,
 546                                         IOAM_CACHE_TS_TICK
 547                                         /* timer period 100ms */ ,
 548                                         10e4);
 549       cm->timer_wheels[i].last_run_time = vlib_time_now (vm);
 550     }
 551   ioam_cache_ts_timer_node_enable (vm, 1);
 552   return (1);
 553 }
 554
 555 always_inline void
 556 ioam_cache_ts_timer_set (ioam_cache_main_t * cm,
 557                          ioam_cache_ts_entry_t * entry, u32 interval)
 558 {
 559   entry->timer_handle
 560     = tw_timer_start_16t_2w_512sl (&cm->timer_wheels[entry->pool_id],
 561                                    entry->pool_index, 1, interval);
 562 }
 563
 564 always_inline void
 565 ioam_cache_ts_timer_reset (ioam_cache_main_t * cm,
 566                            ioam_cache_ts_entry_t * entry)
 567 {
 568   tw_timer_stop_16t_2w_512sl (&cm->timer_wheels[entry->pool_id],
 569                               entry->timer_handle);
 570   entry->timer_handle = TIMER_HANDLE_INVALID;
 571 }
 572
 573 inline static void
 574 ioam_cache_ts_entry_free (u32 thread_id,
 575                           ioam_cache_ts_entry_t * entry, u32 node_index)
 576 {
 577   ioam_cache_main_t *cm = &ioam_cache_main;
 578   vlib_main_t *vm = cm->vlib_main;
 579   vlib_frame_t *nf = 0;
 580   u32 *to_next;
 581
 582   if (entry)
 583     {
 584       if (entry->hbh != 0)
 585         {
 586           nf = vlib_get_frame_to_node (vm, node_index);
 587           nf->n_vectors = 0;
 588           to_next = vlib_frame_vector_args (nf);
 589           nf->n_vectors = 1;
 590           to_next[0] = entry->buffer_index;
 591           vlib_put_frame_to_node (vm, node_index, nf);
 592         }
 593       pool_put (cm->ioam_ts_pool[thread_id], entry);
 594       cm->ts_stats[thread_id].inuse--;
 595       clib_memset (entry, 0, sizeof (*entry));
 596     }
 597 }
 598
 599 inline static int
 600 ioam_cache_ts_table_destroy (vlib_main_t * vm)
 601 {
 602   ioam_cache_main_t *cm = &ioam_cache_main;
 603   ioam_cache_ts_entry_t *entry = 0;
 604   int no_of_threads = vec_len (vlib_worker_threads);
 605   int i;
 606
 607   /* free pool and hash table */
 608   for (i = 0; i < no_of_threads; i++)
 609     {
 610       pool_foreach (entry, cm->ioam_ts_pool[i], (
 611                                                   {
 612                                                   ioam_cache_ts_entry_free (i,
 613                                                                             entry,
 614                                                                             cm->error_node_index);
 615                                                   }
 616                     ));
 617       pool_free (cm->ioam_ts_pool[i]);
 618       cm->ioam_ts_pool = 0;
 619       tw_timer_wheel_free_16t_2w_512sl (&cm->timer_wheels[i]);
 620     }
 621   vec_free (cm->ioam_ts_pool);
 622   return (0);
 623 }
 624
 625 inline static int
 626 ioam_cache_ts_entry_cleanup (u32 thread_id, u32 pool_index)
 627 {
 628   ioam_cache_main_t *cm = &ioam_cache_main;
 629   ioam_cache_ts_entry_t *entry = 0;
 630
 631   entry = pool_elt_at_index (cm->ioam_ts_pool[thread_id], pool_index);
 632   ioam_cache_ts_entry_free (thread_id, entry, cm->error_node_index);
 633   return (0);
 634 }
 635
 636 /*
 637  * Caches buffer for ioam SR tunnel select for Anycast service
 638  */
 639 inline static int
 640 ioam_cache_ts_add (ip6_header_t * ip0,
 641                    u16 src_port,
 642                    u16 dst_port,
 643                    u32 seq_no,
 644                    u8 max_responses, u64 now, u32 thread_id, u32 * pool_index)
 645 {
 646   ioam_cache_main_t *cm = &ioam_cache_main;
 647   ioam_cache_ts_entry_t *entry = 0;
 648
 649   if (cm->ts_stats[thread_id].inuse == MAX_CACHE_TS_ENTRIES)
 650     {
 651       cm->ts_stats[thread_id].add_failed++;
 652       return (-1);
 653     }
 654
 655   pool_get_aligned (cm->ioam_ts_pool[thread_id], entry,
 656                     CLIB_CACHE_LINE_BYTES);
 657   clib_memset (entry, 0, sizeof (*entry));
 658   *pool_index = entry - cm->ioam_ts_pool[thread_id];
 659
 660   clib_memcpy (entry->dst_address.as_u64, ip0->dst_address.as_u64,
 661                sizeof (ip6_address_t));
 662   clib_memcpy (entry->src_address.as_u64, ip0->src_address.as_u64,
 663                sizeof (ip6_address_t));
 664   entry->src_port = src_port;
 665   entry->dst_port = dst_port;
 666   entry->seq_no = seq_no;
 667   entry->response_received = 0;
 668   entry->max_responses = max_responses;
 669   entry->created_at = now;
 670   entry->hbh = 0;
 671   entry->buffer_index = 0;
 672   entry->pool_id = thread_id;
 673   entry->pool_index = *pool_index;
 674   ioam_cache_ts_timer_set (cm, entry, IOAM_CACHE_TS_TIMEOUT);
 675   cm->ts_stats[thread_id].inuse++;
 676   return (0);
 677 }
 678
 679 inline static void
 680 ioam_cache_ts_send (u32 thread_id, i32 pool_index)
 681 {
 682   ioam_cache_main_t *cm = &ioam_cache_main;
 683   ioam_cache_ts_entry_t *entry = 0;
 684
 685   entry = pool_elt_at_index (cm->ioam_ts_pool[thread_id], pool_index);
 686   if (!pool_is_free (cm->ioam_ts_pool[thread_id], entry) && entry)
 687     {
 688       /* send and free pool entry */
 689       ioam_cache_ts_entry_free (thread_id, entry, cm->ip6_hbh_pop_node_index);
 690     }
 691 }
 692
 693 inline static void
 694 ioam_cache_ts_check_and_send (u32 thread_id, i32 pool_index)
 695 {
 696   ioam_cache_main_t *cm = &ioam_cache_main;
 697   ioam_cache_ts_entry_t *entry = 0;
 698   entry = pool_elt_at_index (cm->ioam_ts_pool[thread_id], pool_index);
 699   if (entry && entry->hbh)
 700     {
 701       if (entry->response_received == entry->max_responses ||
 702           entry->created_at + IOAM_CACHE_TS_TIMEOUT <=
 703           vlib_time_now (cm->vlib_main))
 704         {
 705           ioam_cache_ts_timer_reset (cm, entry);
 706           ioam_cache_ts_send (thread_id, pool_index);
 707         }
 708     }
 709 }
 710
 711 inline static int
 712 ioam_cache_ts_update (u32 thread_id,
 713                       i32 pool_index,
 714                       u32 buffer_index, ip6_hop_by_hop_header_t * hbh)
 715 {
 716   ioam_cache_main_t *cm = &ioam_cache_main;
 717   ioam_cache_ts_entry_t *entry = 0;
 718   vlib_main_t *vm = cm->vlib_main;
 719   vlib_frame_t *nf = 0;
 720   u32 *to_next;
 721
 722   entry = pool_elt_at_index (cm->ioam_ts_pool[thread_id], pool_index);
 723   if (!pool_is_free (cm->ioam_ts_pool[thread_id], entry) && entry)
 724     {
 725       /* drop existing buffer */
 726       if (entry->hbh != 0)
 727         {
 728           nf = vlib_get_frame_to_node (vm, cm->error_node_index);
 729           nf->n_vectors = 0;
 730           to_next = vlib_frame_vector_args (nf);
 731           nf->n_vectors = 1;
 732           to_next[0] = entry->buffer_index;
 733           vlib_put_frame_to_node (vm, cm->error_node_index, nf);
 734         }
 735       /* update */
 736       entry->buffer_index = buffer_index;
 737       entry->hbh = hbh;
 738       /* check and send */
 739       ioam_cache_ts_check_and_send (thread_id, pool_index);
 740       return (0);
 741     }
 742   return (-1);
 743 }
 744
 745 /*
 746  * looks up the entry based on the e2e option pool index
 747  * result = 0 found the entry
 748  * result < 0 indicates failture to find an entry
 749  */
 750 inline static int
 751 ioam_cache_ts_lookup (ip6_header_t * ip0,
 752                       u8 protocol,
 753                       u16 src_port,
 754                       u16 dst_port,
 755                       u32 seq_no,
 756                       ip6_hop_by_hop_header_t ** hbh,
 757                       u32 * pool_index, u8 * thread_id, u8 response_seen)
 758 {
 759   ioam_cache_main_t *cm = &ioam_cache_main;
 760   ip6_hop_by_hop_header_t *hbh0 = 0;
 761   ioam_e2e_cache_option_t *e2e = 0;
 762
 763   hbh0 = (ip6_hop_by_hop_header_t *) (ip0 + 1);
 764   e2e =
 765     (ioam_e2e_cache_option_t *) ((u8 *) hbh0 + cm->rewrite_pool_index_offset);
 766   if ((u8 *) e2e < ((u8 *) hbh0 + ((hbh0->length + 1) << 3))
 767       && e2e->hdr.type == HBH_OPTION_TYPE_IOAM_E2E_CACHE_ID)
 768     {
 769       ioam_cache_ts_entry_t *entry = 0;
 770       *pool_index = e2e->pool_index;
 771       *thread_id = e2e->pool_id;
 772       entry = pool_elt_at_index (cm->ioam_ts_pool[*thread_id], *pool_index);
 773       /* match */
 774       if (entry &&
 775           ip6_address_compare (&ip0->src_address, &entry->dst_address) == 0 &&
 776           ip6_address_compare (&ip0->dst_address, &entry->src_address) == 0 &&
 777           entry->src_port == dst_port &&
 778           entry->dst_port == src_port && entry->seq_no == seq_no)
 779         {
 780           *hbh = entry->hbh;
 781           entry->response_received += response_seen;
 782           return (0);
 783         }
 784       else if (entry)
 785         {
 786           return (-1);
 787         }
 788     }
 789   return (-1);
 790 }
 791
 792 inline static u8 *
 793 format_ioam_cache_ts_entry (u8 * s, va_list * args)
 794 {
 795   ioam_cache_ts_entry_t *e = va_arg (*args, ioam_cache_ts_entry_t *);
 796   u32 thread_id = va_arg (*args, u32);
 797   ioam_cache_main_t *cm = &ioam_cache_main;
 798   ioam_e2e_id_option_t *e2e = 0;
 799   vlib_main_t *vm = cm->vlib_main;
 800   clib_time_t *ct = &vm->clib_time;
 801
 802   if (!e)
 803     goto end;
 804
 805   if (e->hbh)
 806     {
 807       e2e =
 808         ip6_ioam_find_hbh_option (e->hbh,
 809                                   HBH_OPTION_TYPE_IOAM_EDGE_TO_EDGE_ID);
 810
 811       s =
 812         format (s,
 813                 "%d: %U:%d to  %U:%d seq_no %u buffer %u %U \n\t\tCreated at %U Received %d\n",
 814                 (e - cm->ioam_ts_pool[thread_id]), format_ip6_address,
 815                 &e->src_address, e->src_port, format_ip6_address,
 816                 &e->dst_address, e->dst_port, e->seq_no, e->buffer_index,
 817                 format_ip6_address, e2e ? &e2e->id : 0, format_time_interval,
 818                 "h:m:s:u",
 819                 (e->created_at -
 820                  vm->cpu_time_main_loop_start) * ct->seconds_per_clock,
 821                 e->response_received);
 822     }
 823   else
 824     {
 825       s =
 826         format (s,
 827                 "%d: %U:%d to  %U:%d seq_no %u Buffer %u \n\t\tCreated at %U Received %d\n",
 828                 (e - cm->ioam_ts_pool[thread_id]), format_ip6_address,
 829                 &e->src_address, e->src_port, format_ip6_address,
 830                 &e->dst_address, e->dst_port, e->seq_no, e->buffer_index,
 831                 format_time_interval, "h:m:s:u",
 832                 (e->created_at -
 833                  vm->cpu_time_main_loop_start) * ct->seconds_per_clock,
 834                 e->response_received);
 835     }
 836
 837 end:
 838   return s;
 839 }
 840
 841 /*
 842  * Get extended rewrite string for iOAM data in v6
 843  * This makes space for an e2e options to carry cache pool info
 844  * and manycast server address.
 845  * It set the rewrite string per configs in ioam ip6 + new option
 846  * for cache along with offset to the option to populate cache
 847  * pool id and index
 848  */
 849 static inline int
 850 ip6_ioam_ts_cache_set_rewrite (void)
 851 {
 852   ip6_hop_by_hop_ioam_main_t *hm = &ip6_hop_by_hop_ioam_main;
 853   ioam_cache_main_t *cm = &ioam_cache_main;
 854   ip6_hop_by_hop_header_t *hbh;
 855   u32 rewrite_len = 0;
 856   ioam_e2e_cache_option_t *e2e = 0;
 857   ioam_e2e_id_option_t *e2e_id = 0;
 858
 859   vec_free (cm->rewrite);
 860   ip6_ioam_set_rewrite (&(cm->rewrite), hm->has_trace_option,
 861                         hm->has_pot_option, hm->has_seqno_option);
 862   hbh = (ip6_hop_by_hop_header_t *) cm->rewrite;
 863   rewrite_len = ((hbh->length + 1) << 3);
 864   vec_validate (cm->rewrite,
 865                 rewrite_len - 1 + IOAM_E2E_CACHE_OPTION_RND +
 866                 IOAM_E2E_ID_OPTION_RND);
 867   hbh = (ip6_hop_by_hop_header_t *) cm->rewrite;
 868   /* setup e2e id option to insert pool id and index of the node caching it */
 869   hbh->length += IOAM_E2E_CACHE_HBH_EXT_LEN + IOAM_E2E_ID_HBH_EXT_LEN;
 870   cm->rewrite_pool_index_offset = rewrite_len;
 871   e2e = (ioam_e2e_cache_option_t *) (cm->rewrite + rewrite_len);
 872   e2e->hdr.type = HBH_OPTION_TYPE_IOAM_E2E_CACHE_ID
 873     | HBH_OPTION_TYPE_SKIP_UNKNOWN;
 874   e2e->hdr.length = sizeof (ioam_e2e_cache_option_t) -
 875     sizeof (ip6_hop_by_hop_option_t);
 876   e2e->e2e_type = 2;
 877   e2e_id =
 878     (ioam_e2e_id_option_t *) ((u8 *) e2e + sizeof (ioam_e2e_cache_option_t));
 879   e2e_id->hdr.type =
 880     HBH_OPTION_TYPE_IOAM_EDGE_TO_EDGE_ID | HBH_OPTION_TYPE_SKIP_UNKNOWN;
 881   e2e_id->hdr.length =
 882     sizeof (ioam_e2e_id_option_t) - sizeof (ip6_hop_by_hop_option_t);
 883   e2e_id->e2e_type = 1;
 884
 885   return (0);
 886 }
 887
 888 static inline int
 889 ip6_ioam_ts_cache_cleanup_rewrite (void)
 890 {
 891   ioam_cache_main_t *cm = &ioam_cache_main;
 892
 893   vec_free (cm->rewrite);
 894   cm->rewrite = 0;
 895   cm->rewrite_pool_index_offset = 0;
 896   return (0);
 897 }
 898 #endif /* __included_ioam_cache_h__ */
 899
 900 /*
 901  * fd.io coding-style-patch-verification: ON
 902  *
 903  * Local Variables:
 904  * eval: (c-set-style "gnu")
 905  * End:
 906  */