src/vnet/ip/ip4_reassembly.c

   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
  16 /**
  17  * @file
  18  * @brief IPv4 Reassembly.
  19  *
  20  * This file contains the source code for IPv4 reassembly.
  21  */
  22
  23 #include <vppinfra/vec.h>
  24 #include <vnet/vnet.h>
  25 #include <vnet/ip/ip.h>
  26 #include <vppinfra/bihash_16_8.h>
  27 #include <vnet/ip/ip4_reassembly.h>
  28
  29 #define MSEC_PER_SEC 1000
  30 #define IP4_REASS_TIMEOUT_DEFAULT_MS 100
  31 #define IP4_REASS_EXPIRE_WALK_INTERVAL_DEFAULT_MS 10000 // 10 seconds default
  32 #define IP4_REASS_MAX_REASSEMBLIES_DEFAULT 1024
  33 #define IP4_REASS_HT_LOAD_FACTOR (0.75)
  34
  35 #define IP4_REASS_DEBUG_BUFFERS 0
  36 #if IP4_REASS_DEBUG_BUFFERS
  37 #define IP4_REASS_DEBUG_BUFFER(bi, what)             \
  38   do                                                 \
  39     {                                                \
  40       u32 _bi = bi;                                  \
  41       printf (#what "buffer %u", _bi);               \
  42       vlib_buffer_t *_b = vlib_get_buffer (vm, _bi); \
  43       while (_b->flags & VLIB_BUFFER_NEXT_PRESENT)   \
  44         {                                            \
  45           _bi = _b->next_buffer;                     \
  46           printf ("[%u]", _bi);                      \
  47           _b = vlib_get_buffer (vm, _bi);            \
  48         }                                            \
  49       printf ("\n");                                 \
  50       fflush (stdout);                               \
  51     }                                                \
  52   while (0)
  53 #else
  54 #define IP4_REASS_DEBUG_BUFFER(...)
  55 #endif
  56
  57 static vlib_node_registration_t ip4_reass_node;
  58
  59 typedef struct
  60 {
  61   union
  62   {
  63     struct
  64     {
  65       u32 xx_id;
  66       ip4_address_t src;
  67       ip4_address_t dst;
  68       u16 frag_id;
  69       u8 proto;
  70       u8 unused;
  71     };
  72     u64 as_u64[2];
  73   };
  74 } ip4_reass_key_t;
  75
  76 always_inline u32
  77 ip4_reass_buffer_get_data_offset_no_check (vlib_buffer_t * b)
  78 {
  79   vnet_buffer_opaque_t *vnb = vnet_buffer (b);
  80   return vnb->ip.reass.range_first - vnb->ip.reass.fragment_first;
  81 }
  82
  83 always_inline u32
  84 ip4_reass_buffer_get_data_offset (vlib_buffer_t * b)
  85 {
  86   vnet_buffer_opaque_t *vnb = vnet_buffer (b);
  87   ASSERT (vnb->ip.reass.range_first >= vnb->ip.reass.fragment_first);
  88   return ip4_reass_buffer_get_data_offset_no_check (b);
  89 }
  90
  91 always_inline u16
  92 ip4_reass_buffer_get_data_len_no_check (vlib_buffer_t * b)
  93 {
  94   vnet_buffer_opaque_t *vnb = vnet_buffer (b);
  95   return clib_min (vnb->ip.reass.range_last, vnb->ip.reass.fragment_last) -
  96     (vnb->ip.reass.fragment_first + ip4_reass_buffer_get_data_offset (b)) + 1;
  97 }
  98
  99 always_inline u16
 100 ip4_reass_buffer_get_data_len (vlib_buffer_t * b)
 101 {
 102   vnet_buffer_opaque_t *vnb = vnet_buffer (b);
 103   ASSERT (vnb->ip.reass.range_last > vnb->ip.reass.fragment_first);
 104   return ip4_reass_buffer_get_data_len_no_check (b);
 105 }
 106
 107 typedef struct
 108 {
 109   // hash table key
 110   ip4_reass_key_t key;
 111   // time when last packet was received
 112   f64 last_heard;
 113   // internal id of this reassembly
 114   u64 id;
 115   // buffer index of first buffer in this reassembly context
 116   u32 first_bi;
 117   // last octet of packet, ~0 until fragment without more_fragments arrives
 118   u32 last_packet_octet;
 119   // length of data collected so far
 120   u32 data_len;
 121   // trace operation counter
 122   u32 trace_op_counter;
 123   // next index - used by non-feature node
 124   u8 next_index;
 125   // minimum fragment length for this reassembly - used to estimate MTU
 126   u16 min_fragment_length;
 127 } ip4_reass_t;
 128
 129 typedef struct
 130 {
 131   ip4_reass_t *pool;
 132   u32 reass_n;
 133   u32 buffers_n;
 134   u32 id_counter;
 135   clib_spinlock_t lock;
 136 } ip4_reass_per_thread_t;
 137
 138 typedef struct
 139 {
 140   // IPv4 config
 141   u32 timeout_ms;
 142   f64 timeout;
 143   u32 expire_walk_interval_ms;
 144   u32 max_reass_n;
 145
 146   // IPv4 runtime
 147   clib_bihash_16_8_t hash;
 148   // per-thread data
 149   ip4_reass_per_thread_t *per_thread_data;
 150
 151   // convenience
 152   vlib_main_t *vlib_main;
 153   vnet_main_t *vnet_main;
 154
 155   // node index of ip4-drop node
 156   u32 ip4_drop_idx;
 157   u32 ip4_reass_expire_node_idx;
 158 } ip4_reass_main_t;
 159
 160 ip4_reass_main_t ip4_reass_main;
 161
 162 typedef enum
 163 {
 164   IP4_REASSEMBLY_NEXT_INPUT,
 165   IP4_REASSEMBLY_NEXT_DROP,
 166   IP4_REASSEMBLY_N_NEXT,
 167 } ip4_reass_next_t;
 168
 169 typedef enum
 170 {
 171   RANGE_NEW,
 172   RANGE_SHRINK,
 173   RANGE_DISCARD,
 174   RANGE_OVERLAP,
 175   FINALIZE,
 176 } ip4_reass_trace_operation_e;
 177
 178 typedef struct
 179 {
 180   u16 range_first;
 181   u16 range_last;
 182   u32 range_bi;
 183   i32 data_offset;
 184   u32 data_len;
 185   u32 first_bi;
 186 } ip4_reass_range_trace_t;
 187
 188 typedef struct
 189 {
 190   ip4_reass_trace_operation_e action;
 191   u32 reass_id;
 192   ip4_reass_range_trace_t trace_range;
 193   u32 size_diff;
 194   u32 op_id;
 195   u32 fragment_first;
 196   u32 fragment_last;
 197   u32 total_data_len;
 198 } ip4_reass_trace_t;
 199
 200 static void
 201 ip4_reass_trace_details (vlib_main_t * vm, u32 bi,
 202                          ip4_reass_range_trace_t * trace)
 203 {
 204   vlib_buffer_t *b = vlib_get_buffer (vm, bi);
 205   vnet_buffer_opaque_t *vnb = vnet_buffer (b);
 206   trace->range_first = vnb->ip.reass.range_first;
 207   trace->range_last = vnb->ip.reass.range_last;
 208   trace->data_offset = ip4_reass_buffer_get_data_offset_no_check (b);
 209   trace->data_len = ip4_reass_buffer_get_data_len_no_check (b);
 210   trace->range_bi = bi;
 211 }
 212
 213 static u8 *
 214 format_ip4_reass_range_trace (u8 * s, va_list * args)
 215 {
 216   ip4_reass_range_trace_t *trace = va_arg (*args, ip4_reass_range_trace_t *);
 217   s = format (s, "range: [%u, %u], off %d, len %u, bi %u", trace->range_first,
 218               trace->range_last, trace->data_offset, trace->data_len,
 219               trace->range_bi);
 220   return s;
 221 }
 222
 223 u8 *
 224 format_ip4_reass_trace (u8 * s, va_list * args)
 225 {
 226   CLIB_UNUSED (vlib_main_t * vm) = va_arg (*args, vlib_main_t *);
 227   CLIB_UNUSED (vlib_node_t * node) = va_arg (*args, vlib_node_t *);
 228   ip4_reass_trace_t *t = va_arg (*args, ip4_reass_trace_t *);
 229   s = format (s, "reass id: %u, op id: %u ", t->reass_id, t->op_id);
 230   u32 indent = format_get_indent (s);
 231   s = format (s, "first bi: %u, data len: %u, ip/fragment[%u, %u]",
 232               t->trace_range.first_bi, t->total_data_len, t->fragment_first,
 233               t->fragment_last);
 234   switch (t->action)
 235     {
 236     case RANGE_SHRINK:
 237       s = format (s, "\n%Ushrink %U by %u", format_white_space, indent,
 238                   format_ip4_reass_range_trace, &t->trace_range,
 239                   t->size_diff);
 240       break;
 241     case RANGE_DISCARD:
 242       s = format (s, "\n%Udiscard %U", format_white_space, indent,
 243                   format_ip4_reass_range_trace, &t->trace_range);
 244       break;
 245     case RANGE_NEW:
 246       s = format (s, "\n%Unew %U", format_white_space, indent,
 247                   format_ip4_reass_range_trace, &t->trace_range);
 248       break;
 249     case RANGE_OVERLAP:
 250       s = format (s, "\n%Uoverlapping/ignored %U", format_white_space, indent,
 251                   format_ip4_reass_range_trace, &t->trace_range);
 252       break;
 253     case FINALIZE:
 254       s = format (s, "\n%Ufinalize reassembly", format_white_space, indent);
 255       break;
 256     }
 257   return s;
 258 }
 259
 260 static void
 261 ip4_reass_add_trace (vlib_main_t * vm, vlib_node_runtime_t * node,
 262                      ip4_reass_main_t * rm, ip4_reass_t * reass, u32 bi,
 263                      ip4_reass_trace_operation_e action, u32 size_diff)
 264 {
 265   vlib_buffer_t *b = vlib_get_buffer (vm, bi);
 266   vnet_buffer_opaque_t *vnb = vnet_buffer (b);
 267   if (pool_is_free_index (vm->trace_main.trace_buffer_pool, b->trace_index))
 268     {
 269       // this buffer's trace is gone
 270       b->flags &= ~VLIB_BUFFER_IS_TRACED;
 271       return;
 272     }
 273   ip4_reass_trace_t *t = vlib_add_trace (vm, node, b, sizeof (t[0]));
 274   t->reass_id = reass->id;
 275   t->action = action;
 276   ip4_reass_trace_details (vm, bi, &t->trace_range);
 277   t->size_diff = size_diff;
 278   t->op_id = reass->trace_op_counter;
 279   ++reass->trace_op_counter;
 280   t->fragment_first = vnb->ip.reass.fragment_first;
 281   t->fragment_last = vnb->ip.reass.fragment_last;
 282   t->trace_range.first_bi = reass->first_bi;
 283   t->total_data_len = reass->data_len;
 284 #if 0
 285   static u8 *s = NULL;
 286   s = format (s, "%U", format_ip4_reass_trace, NULL, NULL, t);
 287   printf ("%.*s\n", vec_len (s), s);
 288   fflush (stdout);
 289   vec_reset_length (s);
 290 #endif
 291 }
 292
 293 always_inline void
 294 ip4_reass_free (ip4_reass_main_t * rm, ip4_reass_per_thread_t * rt,
 295                 ip4_reass_t * reass)
 296 {
 297   clib_bihash_kv_16_8_t kv;
 298   kv.key[0] = reass->key.as_u64[0];
 299   kv.key[1] = reass->key.as_u64[1];
 300   clib_bihash_add_del_16_8 (&rm->hash, &kv, 0);
 301   pool_put (rt->pool, reass);
 302   --rt->reass_n;
 303 }
 304
 305 always_inline void
 306 ip4_reass_on_timeout (vlib_main_t * vm, ip4_reass_main_t * rm,
 307                       ip4_reass_t * reass, u32 ** vec_drop_timeout)
 308 {
 309   u32 range_bi = reass->first_bi;
 310   vlib_buffer_t *range_b;
 311   vnet_buffer_opaque_t *range_vnb;
 312   while (~0 != range_bi)
 313     {
 314       range_b = vlib_get_buffer (vm, range_bi);
 315       range_vnb = vnet_buffer (range_b);
 316       u32 bi = range_bi;
 317       while (~0 != bi)
 318         {
 319           vec_add1 (*vec_drop_timeout, bi);
 320           vlib_buffer_t *b = vlib_get_buffer (vm, bi);
 321           if (b->flags & VLIB_BUFFER_NEXT_PRESENT)
 322             {
 323               bi = b->next_buffer;
 324               b->flags &= ~VLIB_BUFFER_NEXT_PRESENT;
 325             }
 326           else
 327             {
 328               bi = ~0;
 329             }
 330         }
 331       range_bi = range_vnb->ip.reass.next_range_bi;
 332     }
 333 }
 334
 335 ip4_reass_t *
 336 ip4_reass_find_or_create (vlib_main_t * vm, ip4_reass_main_t * rm,
 337                           ip4_reass_per_thread_t * rt,
 338                           ip4_reass_key_t * k, u32 ** vec_drop_timeout)
 339 {
 340   ip4_reass_t *reass = NULL;
 341   f64 now = vlib_time_now (rm->vlib_main);
 342   clib_bihash_kv_16_8_t kv, value;
 343   kv.key[0] = k->as_u64[0];
 344   kv.key[1] = k->as_u64[1];
 345
 346   if (!clib_bihash_search_16_8 (&rm->hash, &kv, &value))
 347     {
 348       reass = pool_elt_at_index (rt->pool, value.value);
 349       if (now > reass->last_heard + rm->timeout)
 350         {
 351           ip4_reass_on_timeout (vm, rm, reass, vec_drop_timeout);
 352           ip4_reass_free (rm, rt, reass);
 353           reass = NULL;
 354         }
 355     }
 356
 357   if (reass)
 358     {
 359       reass->last_heard = now;
 360       return reass;
 361     }
 362
 363   if (rt->reass_n >= rm->max_reass_n)
 364     {
 365       reass = NULL;
 366       return reass;
 367     }
 368   else
 369     {
 370       pool_get (rt->pool, reass);
 371       clib_memset (reass, 0, sizeof (*reass));
 372       reass->id =
 373         ((u64) os_get_thread_index () * 1000000000) + rt->id_counter;
 374       ++rt->id_counter;
 375       reass->first_bi = ~0;
 376       reass->last_packet_octet = ~0;
 377       reass->data_len = 0;
 378       ++rt->reass_n;
 379     }
 380
 381   reass->key.as_u64[0] = kv.key[0] = k->as_u64[0];
 382   reass->key.as_u64[1] = kv.key[1] = k->as_u64[1];
 383   kv.value = reass - rt->pool;
 384   reass->last_heard = now;
 385
 386   if (clib_bihash_add_del_16_8 (&rm->hash, &kv, 1))
 387     {
 388       ip4_reass_free (rm, rt, reass);
 389       reass = NULL;
 390     }
 391
 392   return reass;
 393 }
 394
 395 always_inline void
 396 ip4_reass_finalize (vlib_main_t * vm, vlib_node_runtime_t * node,
 397                     ip4_reass_main_t * rm, ip4_reass_per_thread_t * rt,
 398                     ip4_reass_t * reass, u32 * bi0, u32 * next0,
 399                     u32 * error0, u32 ** vec_drop_compress,
 400                     u32 ** vec_drop_overlap, bool is_feature)
 401 {
 402   ASSERT (~0 != reass->first_bi);
 403   vlib_buffer_t *first_b = vlib_get_buffer (vm, reass->first_bi);
 404   vlib_buffer_t *last_b = NULL;
 405   u32 sub_chain_bi = reass->first_bi;
 406   u32 total_length = 0;
 407   u32 buf_cnt = 0;
 408   u32 dropped_cnt = 0;
 409   do
 410     {
 411       u32 tmp_bi = sub_chain_bi;
 412       vlib_buffer_t *tmp = vlib_get_buffer (vm, tmp_bi);
 413       ip4_header_t *ip = vlib_buffer_get_current (tmp);
 414       u32 data_len = ip4_reass_buffer_get_data_len (tmp);
 415       u32 trim_front =
 416         ip4_header_bytes (ip) + ip4_reass_buffer_get_data_offset (tmp);
 417       u32 trim_end =
 418         vlib_buffer_length_in_chain (vm, tmp) - trim_front - data_len;
 419       if (tmp_bi == reass->first_bi)
 420         {
 421           /* first buffer - keep ip4 header */
 422           ASSERT (0 == ip4_reass_buffer_get_data_offset (tmp));
 423           trim_front = 0;
 424           trim_end = vlib_buffer_length_in_chain (vm, tmp) - data_len -
 425             ip4_header_bytes (ip);
 426           ASSERT (vlib_buffer_length_in_chain (vm, tmp) - trim_end > 0);
 427         }
 428       u32 keep_data =
 429         vlib_buffer_length_in_chain (vm, tmp) - trim_front - trim_end;
 430       while (1)
 431         {
 432           ++buf_cnt;
 433           if (trim_front)
 434             {
 435               if (trim_front > tmp->current_length)
 436                 {
 437                   /* drop whole buffer */
 438                   vec_add1 (*vec_drop_compress, tmp_bi);
 439                   ++dropped_cnt;
 440                   trim_front -= tmp->current_length;
 441                   ASSERT (tmp->flags & VLIB_BUFFER_NEXT_PRESENT);
 442                   tmp->flags &= ~VLIB_BUFFER_NEXT_PRESENT;
 443                   tmp_bi = tmp->next_buffer;
 444                   tmp = vlib_get_buffer (vm, tmp_bi);
 445                   continue;
 446                 }
 447               else
 448                 {
 449                   vlib_buffer_advance (tmp, trim_front);
 450                   trim_front = 0;
 451                 }
 452             }
 453           if (keep_data)
 454             {
 455               if (last_b)
 456                 {
 457                   last_b->flags |= VLIB_BUFFER_NEXT_PRESENT;
 458                   last_b->next_buffer = tmp_bi;
 459                 }
 460               last_b = tmp;
 461               if (keep_data <= tmp->current_length)
 462                 {
 463                   tmp->current_length = keep_data;
 464                   keep_data = 0;
 465                 }
 466               else
 467                 {
 468                   keep_data -= tmp->current_length;
 469                   ASSERT (tmp->flags & VLIB_BUFFER_NEXT_PRESENT);
 470                 }
 471               total_length += tmp->current_length;
 472             }
 473           else
 474             {
 475               vec_add1 (*vec_drop_overlap, tmp_bi);
 476               ASSERT (reass->first_bi != tmp_bi);
 477               ++dropped_cnt;
 478             }
 479           if (tmp->flags & VLIB_BUFFER_NEXT_PRESENT)
 480             {
 481               tmp_bi = tmp->next_buffer;
 482               tmp = vlib_get_buffer (vm, tmp->next_buffer);
 483             }
 484           else
 485             {
 486               break;
 487             }
 488         }
 489       sub_chain_bi =
 490         vnet_buffer (vlib_get_buffer (vm, sub_chain_bi))->ip.
 491         reass.next_range_bi;
 492     }
 493   while (~0 != sub_chain_bi);
 494
 495   ASSERT (last_b != NULL);
 496   last_b->flags &= ~VLIB_BUFFER_NEXT_PRESENT;
 497   ASSERT (rt->buffers_n >= (buf_cnt - dropped_cnt));
 498   rt->buffers_n -= buf_cnt - dropped_cnt;
 499   ASSERT (total_length >= first_b->current_length);
 500   total_length -= first_b->current_length;
 501   first_b->flags |= VLIB_BUFFER_TOTAL_LENGTH_VALID;
 502   first_b->total_length_not_including_first_buffer = total_length;
 503   ip4_header_t *ip = vlib_buffer_get_current (first_b);
 504   ip->flags_and_fragment_offset = 0;
 505   ip->length = clib_host_to_net_u16 (first_b->current_length + total_length);
 506   ip->checksum = ip4_header_checksum (ip);
 507   u32 before = vec_len (*vec_drop_compress);
 508   vlib_buffer_chain_compress (vm, first_b, vec_drop_compress);
 509   rt->buffers_n += vec_len (*vec_drop_compress) - before;
 510
 511   if (PREDICT_FALSE (first_b->flags & VLIB_BUFFER_IS_TRACED))
 512     {
 513       ip4_reass_add_trace (vm, node, rm, reass, reass->first_bi, FINALIZE, 0);
 514 #if 0
 515       // following code does a hexdump of packet fragments to stdout ...
 516       do
 517         {
 518           u32 bi = reass->first_bi;
 519           u8 *s = NULL;
 520           while (~0 != bi)
 521             {
 522               vlib_buffer_t *b = vlib_get_buffer (vm, bi);
 523               s = format (s, "%u: %U\n", bi, format_hexdump,
 524                           vlib_buffer_get_current (b), b->current_length);
 525               if (b->flags & VLIB_BUFFER_NEXT_PRESENT)
 526                 {
 527                   bi = b->next_buffer;
 528                 }
 529               else
 530                 {
 531                   break;
 532                 }
 533             }
 534           printf ("%.*s\n", vec_len (s), s);
 535           fflush (stdout);
 536           vec_free (s);
 537         }
 538       while (0);
 539 #endif
 540     }
 541   *bi0 = reass->first_bi;
 542   if (is_feature)
 543     {
 544       *next0 = IP4_REASSEMBLY_NEXT_INPUT;
 545     }
 546   else
 547     {
 548       *next0 = reass->next_index;
 549     }
 550   vnet_buffer (first_b)->ip.reass.estimated_mtu = reass->min_fragment_length;
 551   *error0 = IP4_ERROR_NONE;
 552   ip4_reass_free (rm, rt, reass);
 553   reass = NULL;
 554 }
 555
 556 always_inline u32
 557 ip4_reass_get_buffer_chain_length (vlib_main_t * vm, vlib_buffer_t * b)
 558 {
 559   u32 len = 0;
 560   while (b)
 561     {
 562       ++len;
 563       if (PREDICT_FALSE (b->flags & VLIB_BUFFER_NEXT_PRESENT))
 564         {
 565           b = vlib_get_buffer (vm, b->next_buffer);
 566         }
 567       else
 568         {
 569           break;
 570         }
 571     }
 572   return len;
 573 }
 574
 575 always_inline void
 576 ip4_reass_insert_range_in_chain (vlib_main_t * vm,
 577                                  ip4_reass_main_t * rm,
 578                                  ip4_reass_per_thread_t * rt,
 579                                  ip4_reass_t * reass,
 580                                  u32 prev_range_bi, u32 new_next_bi)
 581 {
 582
 583   vlib_buffer_t *new_next_b = vlib_get_buffer (vm, new_next_bi);
 584   vnet_buffer_opaque_t *new_next_vnb = vnet_buffer (new_next_b);
 585   if (~0 != prev_range_bi)
 586     {
 587       vlib_buffer_t *prev_b = vlib_get_buffer (vm, prev_range_bi);
 588       vnet_buffer_opaque_t *prev_vnb = vnet_buffer (prev_b);
 589       new_next_vnb->ip.reass.next_range_bi = prev_vnb->ip.reass.next_range_bi;
 590       prev_vnb->ip.reass.next_range_bi = new_next_bi;
 591     }
 592   else
 593     {
 594       if (~0 != reass->first_bi)
 595         {
 596           new_next_vnb->ip.reass.next_range_bi = reass->first_bi;
 597         }
 598       reass->first_bi = new_next_bi;
 599     }
 600   reass->data_len += ip4_reass_buffer_get_data_len (new_next_b);
 601   rt->buffers_n += ip4_reass_get_buffer_chain_length (vm, new_next_b);
 602 }
 603
 604 always_inline void
 605 ip4_reass_remove_range_from_chain (vlib_main_t * vm,
 606                                    vlib_node_runtime_t * node,
 607                                    ip4_reass_main_t * rm,
 608                                    u32 ** vec_drop_overlap,
 609                                    ip4_reass_t * reass, u32 prev_range_bi,
 610                                    u32 discard_bi)
 611 {
 612   vlib_buffer_t *discard_b = vlib_get_buffer (vm, discard_bi);
 613   vnet_buffer_opaque_t *discard_vnb = vnet_buffer (discard_b);
 614   if (~0 != prev_range_bi)
 615     {
 616       vlib_buffer_t *prev_b = vlib_get_buffer (vm, prev_range_bi);
 617       vnet_buffer_opaque_t *prev_vnb = vnet_buffer (prev_b);
 618       ASSERT (prev_vnb->ip.reass.next_range_bi == discard_bi);
 619       prev_vnb->ip.reass.next_range_bi = discard_vnb->ip.reass.next_range_bi;
 620     }
 621   else
 622     {
 623       reass->first_bi = discard_vnb->ip.reass.next_range_bi;
 624     }
 625   reass->data_len -= ip4_reass_buffer_get_data_len (discard_b);
 626   while (1)
 627     {
 628       vec_add1 (*vec_drop_overlap, discard_bi);
 629       if (PREDICT_FALSE (discard_b->flags & VLIB_BUFFER_IS_TRACED))
 630         {
 631           ip4_reass_add_trace (vm, node, rm, reass, discard_bi, RANGE_DISCARD,
 632                                0);
 633         }
 634       if (discard_b->flags & VLIB_BUFFER_NEXT_PRESENT)
 635         {
 636           discard_b->flags &= ~VLIB_BUFFER_NEXT_PRESENT;
 637           discard_bi = discard_b->next_buffer;
 638           discard_b = vlib_get_buffer (vm, discard_bi);
 639         }
 640       else
 641         {
 642           break;
 643         }
 644     }
 645 }
 646
 647 always_inline void
 648 ip4_reass_update (vlib_main_t * vm, vlib_node_runtime_t * node,
 649                   ip4_reass_main_t * rm, ip4_reass_per_thread_t * rt,
 650                   ip4_reass_t * reass, u32 * bi0, u32 * next0,
 651                   u32 * error0, u32 ** vec_drop_overlap,
 652                   u32 ** vec_drop_compress, bool is_feature)
 653 {
 654   int consumed = 0;
 655   vlib_buffer_t *fb = vlib_get_buffer (vm, *bi0);
 656   ip4_header_t *fip = vlib_buffer_get_current (fb);
 657   ASSERT (fb->current_length >= sizeof (*fip));
 658   vnet_buffer_opaque_t *fvnb = vnet_buffer (fb);
 659   reass->next_index = fvnb->ip.reass.next_index;        // store next_index before it's overwritten
 660   const u32 fragment_first = ip4_get_fragment_offset_bytes (fip);
 661   const u32 fragment_length =
 662     clib_net_to_host_u16 (fip->length) - ip4_header_bytes (fip);
 663   const u32 fragment_last = fragment_first + fragment_length - 1;
 664   fvnb->ip.reass.fragment_first = fragment_first;
 665   fvnb->ip.reass.fragment_last = fragment_last;
 666   int more_fragments = ip4_get_fragment_more (fip);
 667   u32 candidate_range_bi = reass->first_bi;
 668   u32 prev_range_bi = ~0;
 669   fvnb->ip.reass.range_first = fragment_first;
 670   fvnb->ip.reass.range_last = fragment_last;
 671   fvnb->ip.reass.next_range_bi = ~0;
 672   if (!more_fragments)
 673     {
 674       reass->last_packet_octet = fragment_last;
 675     }
 676   if (~0 == reass->first_bi)
 677     {
 678       // starting a new reassembly
 679       ip4_reass_insert_range_in_chain (vm, rm, rt, reass, prev_range_bi,
 680                                        *bi0);
 681       if (PREDICT_FALSE (fb->flags & VLIB_BUFFER_IS_TRACED))
 682         {
 683           ip4_reass_add_trace (vm, node, rm, reass, *bi0, RANGE_NEW, 0);
 684         }
 685       *bi0 = ~0;
 686       reass->min_fragment_length = clib_net_to_host_u16 (fip->length);
 687       return;
 688     }
 689   reass->min_fragment_length = clib_min (clib_net_to_host_u16 (fip->length),
 690                                          fvnb->ip.reass.estimated_mtu);
 691   while (~0 != candidate_range_bi)
 692     {
 693       vlib_buffer_t *candidate_b = vlib_get_buffer (vm, candidate_range_bi);
 694       vnet_buffer_opaque_t *candidate_vnb = vnet_buffer (candidate_b);
 695       if (fragment_first > candidate_vnb->ip.reass.range_last)
 696         {
 697           // this fragments starts after candidate range
 698           prev_range_bi = candidate_range_bi;
 699           candidate_range_bi = candidate_vnb->ip.reass.next_range_bi;
 700           if (candidate_vnb->ip.reass.range_last < fragment_last &&
 701               ~0 == candidate_range_bi)
 702             {
 703               // special case - this fragment falls beyond all known ranges
 704               ip4_reass_insert_range_in_chain (vm, rm, rt, reass,
 705                                                prev_range_bi, *bi0);
 706               consumed = 1;
 707               break;
 708             }
 709           continue;
 710         }
 711       if (fragment_last < candidate_vnb->ip.reass.range_first)
 712         {
 713           // this fragment ends before candidate range without any overlap
 714           ip4_reass_insert_range_in_chain (vm, rm, rt, reass, prev_range_bi,
 715                                            *bi0);
 716           consumed = 1;
 717         }
 718       else
 719         {
 720           if (fragment_first >= candidate_vnb->ip.reass.range_first &&
 721               fragment_last <= candidate_vnb->ip.reass.range_last)
 722             {
 723               // this fragment is a (sub)part of existing range, ignore it
 724               if (PREDICT_FALSE (fb->flags & VLIB_BUFFER_IS_TRACED))
 725                 {
 726                   ip4_reass_add_trace (vm, node, rm, reass, *bi0,
 727                                        RANGE_OVERLAP, 0);
 728                 }
 729               break;
 730             }
 731           int discard_candidate = 0;
 732           if (fragment_first < candidate_vnb->ip.reass.range_first)
 733             {
 734               u32 overlap =
 735                 fragment_last - candidate_vnb->ip.reass.range_first + 1;
 736               if (overlap < ip4_reass_buffer_get_data_len (candidate_b))
 737                 {
 738                   candidate_vnb->ip.reass.range_first += overlap;
 739                   ASSERT (reass->data_len >= overlap);
 740                   reass->data_len -= overlap;
 741                   if (PREDICT_FALSE (fb->flags & VLIB_BUFFER_IS_TRACED))
 742                     {
 743                       ip4_reass_add_trace (vm, node, rm, reass,
 744                                            candidate_range_bi, RANGE_SHRINK,
 745                                            overlap);
 746                     }
 747                   ip4_reass_insert_range_in_chain (vm, rm, rt, reass,
 748                                                    prev_range_bi, *bi0);
 749                   consumed = 1;
 750                 }
 751               else
 752                 {
 753                   discard_candidate = 1;
 754                 }
 755             }
 756           else if (fragment_last > candidate_vnb->ip.reass.range_last)
 757             {
 758               u32 overlap =
 759                 candidate_vnb->ip.reass.range_last - fragment_first + 1;
 760               if (overlap < ip4_reass_buffer_get_data_len (candidate_b))
 761                 {
 762                   fvnb->ip.reass.range_first += overlap;
 763                   if (~0 != candidate_vnb->ip.reass.next_range_bi)
 764                     {
 765                       prev_range_bi = candidate_range_bi;
 766                       candidate_range_bi =
 767                         candidate_vnb->ip.reass.next_range_bi;
 768                       continue;
 769                     }
 770                   else
 771                     {
 772                       // special case - last range discarded
 773                       ip4_reass_insert_range_in_chain (vm, rm, rt, reass,
 774                                                        candidate_range_bi,
 775                                                        *bi0);
 776                       consumed = 1;
 777                     }
 778                 }
 779               else
 780                 {
 781                   discard_candidate = 1;
 782                 }
 783             }
 784           else
 785             {
 786               discard_candidate = 1;
 787             }
 788           if (discard_candidate)
 789             {
 790               u32 next_range_bi = candidate_vnb->ip.reass.next_range_bi;
 791               // discard candidate range, probe next range
 792               ip4_reass_remove_range_from_chain (vm, node, rm,
 793                                                  vec_drop_overlap, reass,
 794                                                  prev_range_bi,
 795                                                  candidate_range_bi);
 796               if (~0 != next_range_bi)
 797                 {
 798                   candidate_range_bi = next_range_bi;
 799                   continue;
 800                 }
 801               else
 802                 {
 803                   // special case - last range discarded
 804                   ip4_reass_insert_range_in_chain (vm, rm, rt, reass,
 805                                                    prev_range_bi, *bi0);
 806                   consumed = 1;
 807                 }
 808             }
 809         }
 810       break;
 811     }
 812   if (consumed)
 813     {
 814       if (PREDICT_FALSE (fb->flags & VLIB_BUFFER_IS_TRACED))
 815         {
 816           ip4_reass_add_trace (vm, node, rm, reass, *bi0, RANGE_NEW, 0);
 817         }
 818     }
 819   if (~0 != reass->last_packet_octet &&
 820       reass->data_len == reass->last_packet_octet + 1)
 821     {
 822       ip4_reass_finalize (vm, node, rm, rt, reass, bi0, next0, error0,
 823                           vec_drop_compress, vec_drop_overlap, is_feature);
 824     }
 825   else
 826     {
 827       if (consumed)
 828         {
 829           *bi0 = ~0;
 830         }
 831       else
 832         {
 833           *next0 = IP4_REASSEMBLY_NEXT_DROP;
 834           *error0 = IP4_ERROR_REASS_DUPLICATE_FRAGMENT;
 835         }
 836     }
 837 }
 838
 839 always_inline uword
 840 ip4_reassembly_inline (vlib_main_t * vm,
 841                        vlib_node_runtime_t * node,
 842                        vlib_frame_t * frame, bool is_feature)
 843 {
 844   u32 *from = vlib_frame_vector_args (frame);
 845   u32 n_left_from, n_left_to_next, *to_next, next_index;
 846   ip4_reass_main_t *rm = &ip4_reass_main;
 847   ip4_reass_per_thread_t *rt = &rm->per_thread_data[os_get_thread_index ()];
 848   clib_spinlock_lock (&rt->lock);
 849
 850   n_left_from = frame->n_vectors;
 851   next_index = node->cached_next_index;
 852   static u32 *vec_drop_timeout = NULL;  // indexes of buffers which timed out
 853   static u32 *vec_drop_overlap = NULL;  // indexes of buffers which were discarded due to overlap
 854   static u32 *vec_drop_compress = NULL; // indexes of buffers dicarded due to buffer compression
 855   while (n_left_from > 0 || vec_len (vec_drop_timeout) > 0 ||
 856          vec_len (vec_drop_overlap) > 0 || vec_len (vec_drop_compress) > 0)
 857     {
 858       vlib_get_next_frame (vm, node, next_index, to_next, n_left_to_next);
 859
 860       while (vec_len (vec_drop_timeout) > 0 && n_left_to_next > 0)
 861         {
 862           u32 bi = vec_pop (vec_drop_timeout);
 863           vlib_buffer_t *b = vlib_get_buffer (vm, bi);
 864           b->error = node->errors[IP4_ERROR_REASS_TIMEOUT];
 865           to_next[0] = bi;
 866           to_next += 1;
 867           n_left_to_next -= 1;
 868           vlib_validate_buffer_enqueue_x1 (vm, node, next_index, to_next,
 869                                            n_left_to_next, bi,
 870                                            IP4_REASSEMBLY_NEXT_DROP);
 871           IP4_REASS_DEBUG_BUFFER (bi, enqueue_drop_timeout);
 872           ASSERT (rt->buffers_n > 0);
 873           --rt->buffers_n;
 874         }
 875
 876       while (vec_len (vec_drop_overlap) > 0 && n_left_to_next > 0)
 877         {
 878           u32 bi = vec_pop (vec_drop_overlap);
 879           vlib_buffer_t *b = vlib_get_buffer (vm, bi);
 880           b->error = node->errors[IP4_ERROR_REASS_DUPLICATE_FRAGMENT];
 881           to_next[0] = bi;
 882           to_next += 1;
 883           n_left_to_next -= 1;
 884           vlib_validate_buffer_enqueue_x1 (vm, node, next_index, to_next,
 885                                            n_left_to_next, bi,
 886                                            IP4_REASSEMBLY_NEXT_DROP);
 887           IP4_REASS_DEBUG_BUFFER (bi, enqueue_drop_duplicate_fragment);
 888           ASSERT (rt->buffers_n > 0);
 889           --rt->buffers_n;
 890         }
 891
 892       while (vec_len (vec_drop_compress) > 0 && n_left_to_next > 0)
 893         {
 894           u32 bi = vec_pop (vec_drop_compress);
 895           vlib_buffer_t *b = vlib_get_buffer (vm, bi);
 896           b->error = node->errors[IP4_ERROR_NONE];
 897           to_next[0] = bi;
 898           to_next += 1;
 899           n_left_to_next -= 1;
 900           vlib_validate_buffer_enqueue_x1 (vm, node, next_index, to_next,
 901                                            n_left_to_next, bi,
 902                                            IP4_REASSEMBLY_NEXT_DROP);
 903           IP4_REASS_DEBUG_BUFFER (bi, enqueue_drop_compress);
 904           ASSERT (rt->buffers_n > 0);
 905           --rt->buffers_n;
 906         }
 907
 908       while (n_left_from > 0 && n_left_to_next > 0)
 909         {
 910           u32 bi0;
 911           vlib_buffer_t *b0;
 912           u32 next0;
 913           u32 error0 = IP4_ERROR_NONE;
 914
 915           bi0 = from[0];
 916           b0 = vlib_get_buffer (vm, bi0);
 917
 918           ip4_header_t *ip0 = vlib_buffer_get_current (b0);
 919           if (!ip4_get_fragment_more (ip0) && !ip4_get_fragment_offset (ip0))
 920             {
 921               // this is a whole packet - no fragmentation
 922               if (is_feature)
 923                 {
 924                   next0 = IP4_REASSEMBLY_NEXT_INPUT;
 925                 }
 926               else
 927                 {
 928                   next0 = vnet_buffer (b0)->ip.reass.next_index;
 929                 }
 930             }
 931           else
 932             {
 933               const u32 fragment_first = ip4_get_fragment_offset_bytes (ip0);
 934               const u32 fragment_length =
 935                 clib_net_to_host_u16 (ip0->length) - ip4_header_bytes (ip0);
 936               const u32 fragment_last = fragment_first + fragment_length - 1;
 937               if (fragment_first > fragment_last || fragment_first + fragment_length > UINT16_MAX - 20 || (fragment_length < 8 && ip4_get_fragment_more (ip0))) // 8 is minimum frag length per RFC 791
 938                 {
 939                   next0 = IP4_REASSEMBLY_NEXT_DROP;
 940                   error0 = IP4_ERROR_REASS_MALFORMED_PACKET;
 941                 }
 942               else
 943                 {
 944                   ip4_reass_key_t k;
 945                   k.as_u64[0] =
 946                     (u64) vnet_buffer (b0)->sw_if_index[VLIB_RX] << 32 | (u64)
 947                     ip0->src_address.as_u32;
 948                   k.as_u64[1] =
 949                     (u64) ip0->dst_address.
 950                     as_u32 << 32 | (u64) ip0->fragment_id << 16 | (u64) ip0->
 951                     protocol << 8;
 952
 953                   ip4_reass_t *reass =
 954                     ip4_reass_find_or_create (vm, rm, rt, &k,
 955                                               &vec_drop_timeout);
 956
 957                   if (reass)
 958                     {
 959                       ip4_reass_update (vm, node, rm, rt, reass, &bi0, &next0,
 960                                         &error0, &vec_drop_overlap,
 961                                         &vec_drop_compress, is_feature);
 962                     }
 963                   else
 964                     {
 965                       next0 = IP4_REASSEMBLY_NEXT_DROP;
 966                       error0 = IP4_ERROR_REASS_LIMIT_REACHED;
 967                     }
 968                 }
 969
 970               b0->error = node->errors[error0];
 971             }
 972
 973           if (bi0 != ~0)
 974             {
 975               to_next[0] = bi0;
 976               to_next += 1;
 977               n_left_to_next -= 1;
 978               if (is_feature && IP4_ERROR_NONE == error0)
 979                 {
 980                   b0 = vlib_get_buffer (vm, bi0);
 981                   vnet_feature_next (&next0, b0);
 982                 }
 983               vlib_validate_buffer_enqueue_x1 (vm, node, next_index, to_next,
 984                                                n_left_to_next, bi0, next0);
 985               IP4_REASS_DEBUG_BUFFER (bi0, enqueue_next);
 986             }
 987
 988           from += 1;
 989           n_left_from -= 1;
 990         }
 991
 992       vlib_put_next_frame (vm, node, next_index, n_left_to_next);
 993     }
 994
 995   clib_spinlock_unlock (&rt->lock);
 996   return frame->n_vectors;
 997 }
 998
 999 static char *ip4_reassembly_error_strings[] = {
1000 #define _(sym, string) string,
1001   foreach_ip4_error
1002 #undef _
1003 };
1004
1005 static uword
1006 ip4_reassembly (vlib_main_t * vm, vlib_node_runtime_t * node,
1007                 vlib_frame_t * frame)
1008 {
1009   return ip4_reassembly_inline (vm, node, frame, false /* is_feature */ );
1010 }
1011
1012 /* *INDENT-OFF* */
1013 VLIB_REGISTER_NODE (ip4_reass_node, static) = {
1014     .function = ip4_reassembly,
1015     .name = "ip4-reassembly",
1016     .vector_size = sizeof (u32),
1017     .format_trace = format_ip4_reass_trace,
1018     .n_errors = ARRAY_LEN (ip4_reassembly_error_strings),
1019     .error_strings = ip4_reassembly_error_strings,
1020     .n_next_nodes = IP4_REASSEMBLY_N_NEXT,
1021     .next_nodes =
1022         {
1023                 [IP4_REASSEMBLY_NEXT_INPUT] = "ip4-input",
1024                 [IP4_REASSEMBLY_NEXT_DROP] = "ip4-drop",
1025         },
1026 };
1027 /* *INDENT-ON* */
1028
1029 VLIB_NODE_FUNCTION_MULTIARCH (ip4_reass_node, ip4_reassembly);
1030
1031 static uword
1032 ip4_reassembly_feature (vlib_main_t * vm,
1033                         vlib_node_runtime_t * node, vlib_frame_t * frame)
1034 {
1035   return ip4_reassembly_inline (vm, node, frame, true /* is_feature */ );
1036 }
1037
1038 /* *INDENT-OFF* */
1039 VLIB_REGISTER_NODE (ip4_reass_node_feature, static) = {
1040     .function = ip4_reassembly_feature,
1041     .name = "ip4-reassembly-feature",
1042     .vector_size = sizeof (u32),
1043     .format_trace = format_ip4_reass_trace,
1044     .n_errors = ARRAY_LEN (ip4_reassembly_error_strings),
1045     .error_strings = ip4_reassembly_error_strings,
1046     .n_next_nodes = IP4_REASSEMBLY_N_NEXT,
1047     .next_nodes =
1048         {
1049                 [IP4_REASSEMBLY_NEXT_INPUT] = "ip4-input",
1050                 [IP4_REASSEMBLY_NEXT_DROP] = "ip4-drop",
1051         },
1052 };
1053 /* *INDENT-ON* */
1054
1055 VLIB_NODE_FUNCTION_MULTIARCH (ip4_reass_node_feature, ip4_reassembly_feature);
1056
1057 /* *INDENT-OFF* */
1058 VNET_FEATURE_INIT (ip4_reassembly_feature, static) = {
1059     .arc_name = "ip4-unicast",
1060     .node_name = "ip4-reassembly-feature",
1061     .runs_before = VNET_FEATURES ("ip4-lookup"),
1062     .runs_after = 0,
1063 };
1064 /* *INDENT-ON* */
1065
1066 always_inline u32
1067 ip4_reass_get_nbuckets ()
1068 {
1069   ip4_reass_main_t *rm = &ip4_reass_main;
1070   u32 nbuckets;
1071   u8 i;
1072
1073   nbuckets = (u32) (rm->max_reass_n / IP4_REASS_HT_LOAD_FACTOR);
1074
1075   for (i = 0; i < 31; i++)
1076     if ((1 << i) >= nbuckets)
1077       break;
1078   nbuckets = 1 << i;
1079
1080   return nbuckets;
1081 }
1082
1083 typedef enum
1084 {
1085   IP4_EVENT_CONFIG_CHANGED = 1,
1086 } ip4_reass_event_t;
1087
1088 typedef struct
1089 {
1090   int failure;
1091   clib_bihash_16_8_t *new_hash;
1092 } ip4_rehash_cb_ctx;
1093
1094 static void
1095 ip4_rehash_cb (clib_bihash_kv_16_8_t * kv, void *_ctx)
1096 {
1097   ip4_rehash_cb_ctx *ctx = _ctx;
1098   if (clib_bihash_add_del_16_8 (ctx->new_hash, kv, 1))
1099     {
1100       ctx->failure = 1;
1101     }
1102 }
1103
1104 static void
1105 ip4_reass_set_params (u32 timeout_ms, u32 max_reassemblies,
1106                       u32 expire_walk_interval_ms)
1107 {
1108   ip4_reass_main.timeout_ms = timeout_ms;
1109   ip4_reass_main.timeout = (f64) timeout_ms / (f64) MSEC_PER_SEC;
1110   ip4_reass_main.max_reass_n = max_reassemblies;
1111   ip4_reass_main.expire_walk_interval_ms = expire_walk_interval_ms;
1112 }
1113
1114 vnet_api_error_t
1115 ip4_reass_set (u32 timeout_ms, u32 max_reassemblies,
1116                u32 expire_walk_interval_ms)
1117 {
1118   u32 old_nbuckets = ip4_reass_get_nbuckets ();
1119   ip4_reass_set_params (timeout_ms, max_reassemblies,
1120                         expire_walk_interval_ms);
1121   vlib_process_signal_event (ip4_reass_main.vlib_main,
1122                              ip4_reass_main.ip4_reass_expire_node_idx,
1123                              IP4_EVENT_CONFIG_CHANGED, 0);
1124   u32 new_nbuckets = ip4_reass_get_nbuckets ();
1125   if (ip4_reass_main.max_reass_n > 0 && new_nbuckets > old_nbuckets)
1126     {
1127       clib_bihash_16_8_t new_hash;
1128       clib_memset (&new_hash, 0, sizeof (new_hash));
1129       ip4_rehash_cb_ctx ctx;
1130       ctx.failure = 0;
1131       ctx.new_hash = &new_hash;
1132       clib_bihash_init_16_8 (&new_hash, "ip4-reass", new_nbuckets,
1133                              new_nbuckets * 1024);
1134       clib_bihash_foreach_key_value_pair_16_8 (&ip4_reass_main.hash,
1135                                                ip4_rehash_cb, &ctx);
1136       if (ctx.failure)
1137         {
1138           clib_bihash_free_16_8 (&new_hash);
1139           return -1;
1140         }
1141       else
1142         {
1143           clib_bihash_free_16_8 (&ip4_reass_main.hash);
1144           clib_memcpy_fast (&ip4_reass_main.hash, &new_hash,
1145                             sizeof (ip4_reass_main.hash));
1146         }
1147     }
1148   return 0;
1149 }
1150
1151 vnet_api_error_t
1152 ip4_reass_get (u32 * timeout_ms, u32 * max_reassemblies,
1153                u32 * expire_walk_interval_ms)
1154 {
1155   *timeout_ms = ip4_reass_main.timeout_ms;
1156   *max_reassemblies = ip4_reass_main.max_reass_n;
1157   *expire_walk_interval_ms = ip4_reass_main.expire_walk_interval_ms;
1158   return 0;
1159 }
1160
1161 static clib_error_t *
1162 ip4_reass_init_function (vlib_main_t * vm)
1163 {
1164   ip4_reass_main_t *rm = &ip4_reass_main;
1165   clib_error_t *error = 0;
1166   u32 nbuckets;
1167   vlib_node_t *node;
1168
1169   rm->vlib_main = vm;
1170   rm->vnet_main = vnet_get_main ();
1171
1172   vec_validate (rm->per_thread_data, vlib_num_workers ());
1173   ip4_reass_per_thread_t *rt;
1174   vec_foreach (rt, rm->per_thread_data)
1175   {
1176     clib_spinlock_init (&rt->lock);
1177     pool_alloc (rt->pool, rm->max_reass_n);
1178   }
1179
1180   node = vlib_get_node_by_name (vm, (u8 *) "ip4-reassembly-expire-walk");
1181   ASSERT (node);
1182   rm->ip4_reass_expire_node_idx = node->index;
1183
1184   ip4_reass_set_params (IP4_REASS_TIMEOUT_DEFAULT_MS,
1185                         IP4_REASS_MAX_REASSEMBLIES_DEFAULT,
1186                         IP4_REASS_EXPIRE_WALK_INTERVAL_DEFAULT_MS);
1187
1188   nbuckets = ip4_reass_get_nbuckets ();
1189   clib_bihash_init_16_8 (&rm->hash, "ip4-reass", nbuckets, nbuckets * 1024);
1190
1191   node = vlib_get_node_by_name (vm, (u8 *) "ip4-drop");
1192   ASSERT (node);
1193   rm->ip4_drop_idx = node->index;
1194
1195   return error;
1196 }
1197
1198 VLIB_INIT_FUNCTION (ip4_reass_init_function);
1199
1200 static uword
1201 ip4_reass_walk_expired (vlib_main_t * vm,
1202                         vlib_node_runtime_t * node, vlib_frame_t * f)
1203 {
1204   ip4_reass_main_t *rm = &ip4_reass_main;
1205   uword event_type, *event_data = 0;
1206
1207   while (true)
1208     {
1209       vlib_process_wait_for_event_or_clock (vm,
1210                                             (f64) rm->expire_walk_interval_ms
1211                                             / (f64) MSEC_PER_SEC);
1212       event_type = vlib_process_get_events (vm, &event_data);
1213
1214       switch (event_type)
1215         {
1216         case ~0:                /* no events => timeout */
1217           /* nothing to do here */
1218           break;
1219         case IP4_EVENT_CONFIG_CHANGED:
1220           break;
1221         default:
1222           clib_warning ("BUG: event type 0x%wx", event_type);
1223           break;
1224         }
1225       f64 now = vlib_time_now (vm);
1226
1227       ip4_reass_t *reass;
1228       u32 *vec_drop_timeout = NULL;
1229       int *pool_indexes_to_free = NULL;
1230
1231       uword thread_index = 0;
1232       int index;
1233       const uword nthreads = vlib_num_workers () + 1;
1234       for (thread_index = 0; thread_index < nthreads; ++thread_index)
1235         {
1236           ip4_reass_per_thread_t *rt = &rm->per_thread_data[thread_index];
1237           clib_spinlock_lock (&rt->lock);
1238
1239           vec_reset_length (pool_indexes_to_free);
1240           /* *INDENT-OFF* */
1241           pool_foreach_index (index, rt->pool, ({
1242                                 reass = pool_elt_at_index (rt->pool, index);
1243                                 if (now > reass->last_heard + rm->timeout)
1244                                   {
1245                                     vec_add1 (pool_indexes_to_free, index);
1246                                   }
1247                               }));
1248           /* *INDENT-ON* */
1249           int *i;
1250           /* *INDENT-OFF* */
1251           vec_foreach (i, pool_indexes_to_free)
1252           {
1253             ip4_reass_t *reass = pool_elt_at_index (rt->pool, i[0]);
1254             u32 before = vec_len (vec_drop_timeout);
1255             vlib_buffer_t *b = vlib_get_buffer (vm, reass->first_bi);
1256             if (PREDICT_FALSE (b->flags & VLIB_BUFFER_IS_TRACED))
1257               {
1258                 if (pool_is_free_index (vm->trace_main.trace_buffer_pool,
1259                                         b->trace_index))
1260                   {
1261                     /* the trace is gone, don't trace this buffer anymore */
1262                     b->flags &= ~VLIB_BUFFER_IS_TRACED;
1263                   }
1264               }
1265             ip4_reass_on_timeout (vm, rm, reass, &vec_drop_timeout);
1266             u32 after = vec_len (vec_drop_timeout);
1267             ASSERT (rt->buffers_n >= (after - before));
1268             rt->buffers_n -= (after - before);
1269             ip4_reass_free (rm, rt, reass);
1270           }
1271           /* *INDENT-ON* */
1272
1273           clib_spinlock_unlock (&rt->lock);
1274         }
1275
1276       while (vec_len (vec_drop_timeout) > 0)
1277         {
1278           vlib_frame_t *f = vlib_get_frame_to_node (vm, rm->ip4_drop_idx);
1279           u32 *to_next = vlib_frame_vector_args (f);
1280           u32 n_left_to_next = VLIB_FRAME_SIZE - f->n_vectors;
1281           int trace_frame = 0;
1282           while (vec_len (vec_drop_timeout) > 0 && n_left_to_next > 0)
1283             {
1284               u32 bi = vec_pop (vec_drop_timeout);
1285               vlib_buffer_t *b = vlib_get_buffer (vm, bi);
1286               if (PREDICT_FALSE (b->flags & VLIB_BUFFER_IS_TRACED))
1287                 {
1288                   if (pool_is_free_index (vm->trace_main.trace_buffer_pool,
1289                                           b->trace_index))
1290                     {
1291                       /* the trace is gone, don't trace this buffer anymore */
1292                       b->flags &= ~VLIB_BUFFER_IS_TRACED;
1293                     }
1294                   else
1295                     {
1296                       trace_frame = 1;
1297                     }
1298                 }
1299               b->error = node->errors[IP4_ERROR_REASS_TIMEOUT];
1300               to_next[0] = bi;
1301               ++f->n_vectors;
1302               to_next += 1;
1303               n_left_to_next -= 1;
1304               IP4_REASS_DEBUG_BUFFER (bi, enqueue_drop_timeout_walk);
1305             }
1306           f->frame_flags |= (trace_frame * VLIB_FRAME_TRACE);
1307           vlib_put_frame_to_node (vm, rm->ip4_drop_idx, f);
1308         }
1309
1310       vec_free (pool_indexes_to_free);
1311       vec_free (vec_drop_timeout);
1312       if (event_data)
1313         {
1314           _vec_len (event_data) = 0;
1315         }
1316     }
1317
1318   return 0;
1319 }
1320
1321 static vlib_node_registration_t ip4_reass_expire_node;
1322
1323 /* *INDENT-OFF* */
1324 VLIB_REGISTER_NODE (ip4_reass_expire_node, static) = {
1325     .function = ip4_reass_walk_expired,
1326     .type = VLIB_NODE_TYPE_PROCESS,
1327     .name = "ip4-reassembly-expire-walk",
1328     .format_trace = format_ip4_reass_trace,
1329     .n_errors = ARRAY_LEN (ip4_reassembly_error_strings),
1330     .error_strings = ip4_reassembly_error_strings,
1331
1332 };
1333 /* *INDENT-ON* */
1334
1335 static u8 *
1336 format_ip4_reass_key (u8 * s, va_list * args)
1337 {
1338   ip4_reass_key_t *key = va_arg (*args, ip4_reass_key_t *);
1339   s = format (s, "xx_id: %u, src: %U, dst: %U, frag_id: %u, proto: %u",
1340               key->xx_id, format_ip4_address, &key->src, format_ip4_address,
1341               &key->dst, clib_net_to_host_u16 (key->frag_id), key->proto);
1342   return s;
1343 }
1344
1345 static u8 *
1346 format_ip4_reass (u8 * s, va_list * args)
1347 {
1348   vlib_main_t *vm = va_arg (*args, vlib_main_t *);
1349   ip4_reass_t *reass = va_arg (*args, ip4_reass_t *);
1350
1351   s = format (s, "ID: %lu, key: %U\n  first_bi: %u, data_len: %u, "
1352               "last_packet_octet: %u, trace_op_counter: %u\n",
1353               reass->id, format_ip4_reass_key, &reass->key, reass->first_bi,
1354               reass->data_len, reass->last_packet_octet,
1355               reass->trace_op_counter);
1356   u32 bi = reass->first_bi;
1357   u32 counter = 0;
1358   while (~0 != bi)
1359     {
1360       vlib_buffer_t *b = vlib_get_buffer (vm, bi);
1361       vnet_buffer_opaque_t *vnb = vnet_buffer (b);
1362       s = format (s, "  #%03u: range: [%u, %u], bi: %u, off: %d, len: %u, "
1363                   "fragment[%u, %u]\n",
1364                   counter, vnb->ip.reass.range_first,
1365                   vnb->ip.reass.range_last, bi,
1366                   ip4_reass_buffer_get_data_offset_no_check (b),
1367                   ip4_reass_buffer_get_data_len_no_check (b),
1368                   vnb->ip.reass.fragment_first, vnb->ip.reass.fragment_last);
1369       if (b->flags & VLIB_BUFFER_NEXT_PRESENT)
1370         {
1371           bi = b->next_buffer;
1372         }
1373       else
1374         {
1375           bi = ~0;
1376         }
1377     }
1378   return s;
1379 }
1380
1381 static clib_error_t *
1382 show_ip4_reass (vlib_main_t * vm, unformat_input_t * input,
1383                 CLIB_UNUSED (vlib_cli_command_t * lmd))
1384 {
1385   ip4_reass_main_t *rm = &ip4_reass_main;
1386
1387   vlib_cli_output (vm, "---------------------");
1388   vlib_cli_output (vm, "IP4 reassembly status");
1389   vlib_cli_output (vm, "---------------------");
1390   bool details = false;
1391   if (unformat (input, "details"))
1392     {
1393       details = true;
1394     }
1395
1396   u32 sum_reass_n = 0;
1397   u64 sum_buffers_n = 0;
1398   ip4_reass_t *reass;
1399   uword thread_index;
1400   const uword nthreads = vlib_num_workers () + 1;
1401   for (thread_index = 0; thread_index < nthreads; ++thread_index)
1402     {
1403       ip4_reass_per_thread_t *rt = &rm->per_thread_data[thread_index];
1404       clib_spinlock_lock (&rt->lock);
1405       if (details)
1406         {
1407           /* *INDENT-OFF* */
1408           pool_foreach (reass, rt->pool, {
1409             vlib_cli_output (vm, "%U", format_ip4_reass, vm, reass);
1410           });
1411           /* *INDENT-ON* */
1412         }
1413       sum_reass_n += rt->reass_n;
1414       sum_buffers_n += rt->buffers_n;
1415       clib_spinlock_unlock (&rt->lock);
1416     }
1417   vlib_cli_output (vm, "---------------------");
1418   vlib_cli_output (vm, "Current IP4 reassemblies count: %lu\n",
1419                    (long unsigned) sum_reass_n);
1420   vlib_cli_output (vm,
1421                    "Maximum configured concurrent IP4 reassemblies per worker-thread: %lu\n",
1422                    (long unsigned) rm->max_reass_n);
1423   vlib_cli_output (vm, "Buffers in use: %lu\n",
1424                    (long unsigned) sum_buffers_n);
1425   return 0;
1426 }
1427
1428 /* *INDENT-OFF* */
1429 VLIB_CLI_COMMAND (show_ip4_reassembly_cmd, static) = {
1430     .path = "show ip4-reassembly",
1431     .short_help = "show ip4-reassembly [details]",
1432     .function = show_ip4_reass,
1433 };
1434 /* *INDENT-ON* */
1435
1436 vnet_api_error_t
1437 ip4_reass_enable_disable (u32 sw_if_index, u8 enable_disable)
1438 {
1439   return vnet_feature_enable_disable ("ip4-unicast", "ip4-reassembly-feature",
1440                                       sw_if_index, enable_disable, 0, 0);
1441 }
1442
1443 /*
1444  * fd.io coding-style-patch-verification: ON
1445  *
1446  * Local Variables:
1447  * eval: (c-set-style "gnu")
1448  * End:
1449  */