f2fe23b32319fbd81550a6a819fe2e486ba4e613
[vpp.git] / src / vnet / classify / vnet_classify.c
1 /*
2  * Copyright (c) 2015 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 #include <vnet/classify/vnet_classify.h>
16 #include <vnet/classify/input_acl.h>
17 #include <vnet/ip/ip.h>
18 #include <vnet/api_errno.h>     /* for API error numbers */
19 #include <vnet/l2/l2_classify.h> /* for L2_INPUT_CLASSIFY_NEXT_xxx */
20 #include <vnet/fib/fib_table.h>
21
22 vnet_classify_main_t vnet_classify_main;
23
24 #if VALIDATION_SCAFFOLDING
25 /* Validation scaffolding */
26 void mv (vnet_classify_table_t * t)
27 {
28   void * oldheap;
29
30   oldheap = clib_mem_set_heap (t->mheap);
31   clib_mem_validate();
32   clib_mem_set_heap (oldheap);
33 }
34
35 void rogue (vnet_classify_table_t * t)
36 {
37   int i, j, k;
38   vnet_classify_entry_t * v, * save_v;
39   u32 active_elements = 0;
40   vnet_classify_bucket_t * b;
41   
42   for (i = 0; i < t->nbuckets; i++)
43     {
44       b = &t->buckets [i];
45       if (b->offset == 0)
46         continue;
47       save_v = vnet_classify_get_entry (t, b->offset);
48       for (j = 0; j < (1<<b->log2_pages); j++)
49         {
50           for (k = 0; k < t->entries_per_page; k++)
51             {
52               v = vnet_classify_entry_at_index 
53                 (t, save_v, j*t->entries_per_page + k);
54
55               if (vnet_classify_entry_is_busy (v))
56                 active_elements++;
57             }
58         }
59     }
60
61   if (active_elements != t->active_elements)
62     clib_warning ("found %u expected %u elts", active_elements, 
63                   t->active_elements);
64 }
65 #else
66 void mv (vnet_classify_table_t * t) { }
67 void rogue (vnet_classify_table_t * t) { }
68 #endif
69
70 void vnet_classify_register_unformat_l2_next_index_fn (unformat_function_t * fn)
71 {
72   vnet_classify_main_t * cm = &vnet_classify_main;
73
74   vec_add1 (cm->unformat_l2_next_index_fns, fn);
75 }
76
77 void vnet_classify_register_unformat_ip_next_index_fn (unformat_function_t * fn)
78 {
79   vnet_classify_main_t * cm = &vnet_classify_main;
80
81   vec_add1 (cm->unformat_ip_next_index_fns, fn);
82 }
83
84 void 
85 vnet_classify_register_unformat_acl_next_index_fn (unformat_function_t * fn)
86 {
87   vnet_classify_main_t * cm = &vnet_classify_main;
88
89   vec_add1 (cm->unformat_acl_next_index_fns, fn);
90 }
91
92 void
93 vnet_classify_register_unformat_policer_next_index_fn (unformat_function_t * fn)
94 {
95   vnet_classify_main_t * cm = &vnet_classify_main;
96
97   vec_add1 (cm->unformat_policer_next_index_fns, fn);
98 }
99
100 void vnet_classify_register_unformat_opaque_index_fn (unformat_function_t * fn)
101 {
102   vnet_classify_main_t * cm = &vnet_classify_main;
103
104   vec_add1 (cm->unformat_opaque_index_fns, fn);
105 }
106
107 vnet_classify_table_t * 
108 vnet_classify_new_table (vnet_classify_main_t *cm,
109                          u8 * mask, u32 nbuckets, u32 memory_size,
110                          u32 skip_n_vectors,
111                          u32 match_n_vectors)
112 {
113   vnet_classify_table_t * t;
114   void * oldheap;
115     
116   nbuckets = 1 << (max_log2 (nbuckets));
117
118   pool_get_aligned (cm->tables, t, CLIB_CACHE_LINE_BYTES);
119   memset(t, 0, sizeof (*t));
120   
121   vec_validate_aligned (t->mask, match_n_vectors - 1, sizeof(u32x4));
122   clib_memcpy (t->mask, mask, match_n_vectors * sizeof (u32x4));
123
124   t->next_table_index = ~0;
125   t->nbuckets = nbuckets;
126   t->log2_nbuckets = max_log2 (nbuckets);
127   t->match_n_vectors = match_n_vectors;
128   t->skip_n_vectors = skip_n_vectors;
129   t->entries_per_page = 2;
130
131   t->mheap = mheap_alloc (0 /* use VM */, memory_size);
132
133   vec_validate_aligned (t->buckets, nbuckets - 1, CLIB_CACHE_LINE_BYTES);
134   oldheap = clib_mem_set_heap (t->mheap);
135
136   t->writer_lock = clib_mem_alloc_aligned (CLIB_CACHE_LINE_BYTES, 
137                                            CLIB_CACHE_LINE_BYTES);
138   t->writer_lock[0] = 0;
139
140   clib_mem_set_heap (oldheap);
141   return (t);
142 }
143
144 void vnet_classify_delete_table_index (vnet_classify_main_t *cm, 
145                                        u32 table_index, int del_chain)
146 {
147   vnet_classify_table_t * t;
148
149   /* Tolerate multiple frees, up to a point */
150   if (pool_is_free_index (cm->tables, table_index))
151     return;
152
153   t = pool_elt_at_index (cm->tables, table_index);
154   if (del_chain && t->next_table_index != ~0)
155     /* Recursively delete the entire chain */
156     vnet_classify_delete_table_index (cm, t->next_table_index, del_chain);
157
158   vec_free (t->mask);
159   vec_free (t->buckets);
160   mheap_free (t->mheap);
161   
162   pool_put (cm->tables, t);
163 }
164
165 static vnet_classify_entry_t *
166 vnet_classify_entry_alloc (vnet_classify_table_t * t, u32 log2_pages)
167 {
168   vnet_classify_entry_t * rv = 0;
169   u32 required_length;
170   void * oldheap;
171
172   ASSERT (t->writer_lock[0]);
173   required_length = 
174     (sizeof(vnet_classify_entry_t) + (t->match_n_vectors*sizeof(u32x4)))
175     * t->entries_per_page * (1<<log2_pages);
176
177   if (log2_pages >= vec_len (t->freelists) || t->freelists [log2_pages] == 0)
178     {
179       oldheap = clib_mem_set_heap (t->mheap);
180       
181       vec_validate (t->freelists, log2_pages);
182
183       rv = clib_mem_alloc_aligned (required_length, CLIB_CACHE_LINE_BYTES);
184       clib_mem_set_heap (oldheap);
185       goto initialize;
186     }
187   rv = t->freelists[log2_pages];
188   t->freelists[log2_pages] = rv->next_free;
189   
190 initialize:
191   ASSERT(rv);
192
193   memset (rv, 0xff, required_length);
194   return rv;
195 }
196
197 static void
198 vnet_classify_entry_free (vnet_classify_table_t * t,
199                           vnet_classify_entry_t * v, u32 log2_pages)
200 {
201     ASSERT (t->writer_lock[0]);
202
203     ASSERT(vec_len (t->freelists) > log2_pages);
204
205     v->next_free = t->freelists[log2_pages];
206     t->freelists[log2_pages] = v;
207 }
208
209 static inline void make_working_copy
210 (vnet_classify_table_t * t, vnet_classify_bucket_t * b)
211 {
212   vnet_classify_entry_t * v;
213   vnet_classify_bucket_t working_bucket __attribute__((aligned (8)));
214   void * oldheap;
215   vnet_classify_entry_t * working_copy;
216   u32 thread_index = vlib_get_thread_index();
217   int working_copy_length, required_length;
218
219   if (thread_index >= vec_len (t->working_copies))
220     {
221       oldheap = clib_mem_set_heap (t->mheap);
222       vec_validate (t->working_copies, thread_index);
223       vec_validate (t->working_copy_lengths, thread_index);
224       t->working_copy_lengths[thread_index] = -1;
225       clib_mem_set_heap (oldheap);
226     }
227
228   /* 
229    * working_copies are per-cpu so that near-simultaneous
230    * updates from multiple threads will not result in sporadic, spurious
231    * lookup failures. 
232    */
233   working_copy = t->working_copies[thread_index];
234   working_copy_length = t->working_copy_lengths[thread_index];
235   required_length = 
236     (sizeof(vnet_classify_entry_t) + (t->match_n_vectors*sizeof(u32x4)))
237     * t->entries_per_page * (1<<b->log2_pages);
238
239   t->saved_bucket.as_u64 = b->as_u64;
240   oldheap = clib_mem_set_heap (t->mheap);
241
242   if (required_length > working_copy_length)
243     {
244       if (working_copy)
245         clib_mem_free (working_copy);
246       working_copy =
247         clib_mem_alloc_aligned (required_length, CLIB_CACHE_LINE_BYTES);
248       t->working_copies[thread_index] = working_copy;
249     }
250
251   clib_mem_set_heap (oldheap);
252
253   v = vnet_classify_get_entry (t, b->offset);
254   
255   clib_memcpy (working_copy, v, required_length);
256   
257   working_bucket.as_u64 = b->as_u64;
258   working_bucket.offset = vnet_classify_get_offset (t, working_copy);
259   CLIB_MEMORY_BARRIER();
260   b->as_u64 = working_bucket.as_u64;
261   t->working_copies[thread_index] = working_copy;
262 }
263
264 static vnet_classify_entry_t *
265 split_and_rehash (vnet_classify_table_t * t,
266                   vnet_classify_entry_t * old_values, u32 old_log2_pages,
267                   u32 new_log2_pages)
268 {
269   vnet_classify_entry_t * new_values, * v, * new_v;
270   int i, j, length_in_entries;
271   
272   new_values = vnet_classify_entry_alloc (t, new_log2_pages);
273   length_in_entries = (1<<old_log2_pages) * t->entries_per_page;
274   
275   for (i = 0; i < length_in_entries; i++)
276     {
277       u64 new_hash;
278       
279       v = vnet_classify_entry_at_index (t, old_values, i);
280           
281       if (vnet_classify_entry_is_busy (v))
282         {
283           /* Hack so we can use the packet hash routine */
284           u8 * key_minus_skip;
285           key_minus_skip = (u8 *) v->key;
286           key_minus_skip -= t->skip_n_vectors * sizeof (u32x4);
287           
288           new_hash = vnet_classify_hash_packet (t, key_minus_skip);
289           new_hash >>= t->log2_nbuckets;
290           new_hash &= (1<<new_log2_pages) - 1;
291           
292           for (j = 0; j < t->entries_per_page; j++)
293             {
294               new_v = vnet_classify_entry_at_index (t, new_values, 
295                                                     new_hash + j);
296                   
297               if (vnet_classify_entry_is_free (new_v))
298                 {
299                   clib_memcpy (new_v, v, sizeof (vnet_classify_entry_t) 
300                                + (t->match_n_vectors * sizeof (u32x4)));
301                   new_v->flags &= ~(VNET_CLASSIFY_ENTRY_FREE);
302                   goto doublebreak;
303                 }
304             }
305           /* Crap. Tell caller to try again */
306           vnet_classify_entry_free (t, new_values, new_log2_pages);
307           return 0;
308         doublebreak:
309           ;
310         }
311     }
312   return new_values;
313 }
314
315 static vnet_classify_entry_t *
316 split_and_rehash_linear (vnet_classify_table_t * t,
317                          vnet_classify_entry_t * old_values, 
318                          u32 old_log2_pages,
319                          u32 new_log2_pages)
320 {
321   vnet_classify_entry_t * new_values, * v, * new_v;
322   int i, j, new_length_in_entries, old_length_in_entries;
323   
324   new_values = vnet_classify_entry_alloc (t, new_log2_pages);
325   new_length_in_entries = (1<<new_log2_pages) * t->entries_per_page;
326   old_length_in_entries = (1<<old_log2_pages) * t->entries_per_page;
327   
328   j = 0;
329   for (i = 0; i < old_length_in_entries; i++)
330     {
331       v = vnet_classify_entry_at_index (t, old_values, i);
332           
333       if (vnet_classify_entry_is_busy (v))
334         {
335           for (; j < new_length_in_entries; j++)
336             {
337               new_v = vnet_classify_entry_at_index (t, new_values, j);
338               
339               if (vnet_classify_entry_is_busy (new_v))
340                 {
341                   clib_warning ("BUG: linear rehash new entry not free!");
342                   continue;
343                 }
344               clib_memcpy (new_v, v, sizeof (vnet_classify_entry_t) 
345                            + (t->match_n_vectors * sizeof (u32x4)));
346               new_v->flags &= ~(VNET_CLASSIFY_ENTRY_FREE);
347               j++;
348               goto doublebreak;
349             }
350           /* 
351            * Crap. Tell caller to try again.
352            * This should never happen... 
353            */
354           clib_warning ("BUG: linear rehash failed!");
355           vnet_classify_entry_free (t, new_values, new_log2_pages);
356           return 0;
357         }
358     doublebreak:
359       ;
360     }
361
362   return new_values;
363 }
364
365 static void
366 vnet_classify_entry_claim_resource (vnet_classify_entry_t *e)
367 {
368     switch (e->action)
369     {
370     case CLASSIFY_ACTION_SET_IP4_FIB_INDEX:
371         fib_table_lock (e->metadata, FIB_PROTOCOL_IP4, FIB_SOURCE_CLASSIFY);
372         break;
373     case CLASSIFY_ACTION_SET_IP6_FIB_INDEX:
374         fib_table_lock (e->metadata, FIB_PROTOCOL_IP6, FIB_SOURCE_CLASSIFY);
375         break;
376     }
377 }
378
379 static void
380 vnet_classify_entry_release_resource (vnet_classify_entry_t *e)
381 {
382     switch (e->action)
383     {
384     case CLASSIFY_ACTION_SET_IP4_FIB_INDEX:
385         fib_table_unlock (e->metadata, FIB_PROTOCOL_IP4, FIB_SOURCE_CLASSIFY);
386         break;
387     case CLASSIFY_ACTION_SET_IP6_FIB_INDEX:
388         fib_table_unlock (e->metadata, FIB_PROTOCOL_IP6, FIB_SOURCE_CLASSIFY);
389         break;
390     }
391 }
392
393 int vnet_classify_add_del (vnet_classify_table_t * t, 
394                            vnet_classify_entry_t * add_v,
395                            int is_add)
396 {
397   u32 bucket_index;
398   vnet_classify_bucket_t * b, tmp_b;
399   vnet_classify_entry_t * v, * new_v, * save_new_v, * working_copy, * save_v;
400   u32 value_index;
401   int rv = 0;
402   int i;
403   u64 hash, new_hash;
404   u32 limit;
405   u32 old_log2_pages, new_log2_pages;
406   u32 thread_index = vlib_get_thread_index();
407   u8 * key_minus_skip;
408   int resplit_once = 0;
409   int mark_bucket_linear;
410
411   ASSERT ((add_v->flags & VNET_CLASSIFY_ENTRY_FREE) == 0);
412
413   key_minus_skip = (u8 *) add_v->key;
414   key_minus_skip -= t->skip_n_vectors * sizeof (u32x4);
415
416   hash = vnet_classify_hash_packet (t, key_minus_skip);
417
418   bucket_index = hash & (t->nbuckets-1);
419   b = &t->buckets[bucket_index];
420
421   hash >>= t->log2_nbuckets;
422
423   while (__sync_lock_test_and_set (t->writer_lock, 1))
424     ; 
425
426   /* First elt in the bucket? */
427   if (b->offset == 0)
428     {
429       if (is_add == 0)
430         {
431           rv = -1;
432           goto unlock;
433         }
434
435       v = vnet_classify_entry_alloc (t, 0 /* new_log2_pages */);
436       clib_memcpy (v, add_v, sizeof (vnet_classify_entry_t) +
437               t->match_n_vectors * sizeof (u32x4));
438       v->flags &= ~(VNET_CLASSIFY_ENTRY_FREE);
439       vnet_classify_entry_claim_resource (v);
440
441       tmp_b.as_u64 = 0;
442       tmp_b.offset = vnet_classify_get_offset (t, v);
443
444       b->as_u64 = tmp_b.as_u64;
445       t->active_elements ++;
446
447       goto unlock;
448     }
449   
450   make_working_copy (t, b);
451   
452   save_v = vnet_classify_get_entry (t, t->saved_bucket.offset);
453   value_index = hash & ((1<<t->saved_bucket.log2_pages)-1);
454   limit = t->entries_per_page;
455   if (PREDICT_FALSE (b->linear_search))
456     {
457       value_index = 0;
458       limit *= (1<<b->log2_pages);
459     }
460   
461   if (is_add)
462     {
463       /* 
464        * For obvious (in hindsight) reasons, see if we're supposed to
465        * replace an existing key, then look for an empty slot.
466        */
467
468       for (i = 0; i < limit; i++)
469         {
470           v = vnet_classify_entry_at_index (t, save_v, value_index + i);
471
472           if (!memcmp (v->key, add_v->key, t->match_n_vectors * sizeof (u32x4)))
473             {
474               clib_memcpy (v, add_v, sizeof (vnet_classify_entry_t) +
475                       t->match_n_vectors * sizeof(u32x4));
476               v->flags &= ~(VNET_CLASSIFY_ENTRY_FREE);
477               vnet_classify_entry_claim_resource (v);
478
479               CLIB_MEMORY_BARRIER();
480               /* Restore the previous (k,v) pairs */
481               b->as_u64 = t->saved_bucket.as_u64;
482               goto unlock;
483             }
484         }
485       for (i = 0; i < limit; i++)
486         {
487           v = vnet_classify_entry_at_index (t, save_v, value_index + i);
488
489           if (vnet_classify_entry_is_free (v))
490             {
491               clib_memcpy (v, add_v, sizeof (vnet_classify_entry_t) +
492                       t->match_n_vectors * sizeof(u32x4));
493               v->flags &= ~(VNET_CLASSIFY_ENTRY_FREE);
494               vnet_classify_entry_claim_resource (v);
495
496               CLIB_MEMORY_BARRIER();
497               b->as_u64 = t->saved_bucket.as_u64;
498               t->active_elements ++;
499               goto unlock;
500             }
501         }
502       /* no room at the inn... split case... */
503     }
504   else
505     {
506       for (i = 0; i < limit; i++)
507         {
508           v = vnet_classify_entry_at_index (t, save_v, value_index + i);
509
510           if (!memcmp (v->key, add_v->key, t->match_n_vectors * sizeof (u32x4)))
511             {
512               vnet_classify_entry_release_resource (v);
513               memset (v, 0xff, sizeof (vnet_classify_entry_t) +
514                       t->match_n_vectors * sizeof(u32x4));
515               v->flags |= VNET_CLASSIFY_ENTRY_FREE;
516
517               CLIB_MEMORY_BARRIER();
518               b->as_u64 = t->saved_bucket.as_u64;
519               t->active_elements --;
520               goto unlock;
521             }
522         }
523       rv = -3;
524       b->as_u64 = t->saved_bucket.as_u64;
525       goto unlock;
526     }
527
528   old_log2_pages = t->saved_bucket.log2_pages;
529   new_log2_pages = old_log2_pages + 1;
530   working_copy = t->working_copies[thread_index];
531
532   if (t->saved_bucket.linear_search)
533     goto linear_resplit;
534
535   mark_bucket_linear = 0;
536
537   new_v = split_and_rehash (t, working_copy, old_log2_pages, new_log2_pages);
538
539   if (new_v == 0)
540     {
541     try_resplit:
542       resplit_once = 1;
543       new_log2_pages++;
544
545       new_v = split_and_rehash (t, working_copy, old_log2_pages, 
546                                 new_log2_pages);
547       if (new_v == 0)
548         {
549         mark_linear:
550           new_log2_pages--;
551
552         linear_resplit:
553           /* pinned collisions, use linear search */
554           new_v = split_and_rehash_linear (t, working_copy, old_log2_pages,
555                                            new_log2_pages);
556           /* A new linear-search bucket? */
557           if (!t->saved_bucket.linear_search)
558             t->linear_buckets ++;
559           mark_bucket_linear = 1;
560         }
561     }
562
563   /* Try to add the new entry */
564   save_new_v = new_v;
565
566   key_minus_skip = (u8 *) add_v->key;
567   key_minus_skip -= t->skip_n_vectors * sizeof (u32x4);
568
569   new_hash = vnet_classify_hash_packet_inline (t, key_minus_skip);
570   new_hash >>= t->log2_nbuckets;
571   new_hash &= (1<<new_log2_pages) - 1;
572
573   limit = t->entries_per_page;
574   if (mark_bucket_linear)
575     {
576       limit *= (1<<new_log2_pages);
577       new_hash = 0;
578     }
579   
580   for (i = 0; i < limit; i++)
581     {
582       new_v = vnet_classify_entry_at_index (t, save_new_v, new_hash + i);
583
584       if (vnet_classify_entry_is_free (new_v))
585         {
586           clib_memcpy (new_v, add_v, sizeof (vnet_classify_entry_t) +
587                   t->match_n_vectors * sizeof(u32x4));
588           new_v->flags &= ~(VNET_CLASSIFY_ENTRY_FREE);
589           vnet_classify_entry_claim_resource (new_v);
590
591           goto expand_ok;
592         }
593     }
594   /* Crap. Try again */
595   vnet_classify_entry_free (t, save_new_v, new_log2_pages);
596   new_log2_pages++;
597
598   if (resplit_once)
599     goto mark_linear;
600   else 
601     goto try_resplit;
602
603  expand_ok:
604   tmp_b.log2_pages = new_log2_pages;
605   tmp_b.offset = vnet_classify_get_offset (t, save_new_v);
606   tmp_b.linear_search = mark_bucket_linear;
607
608   CLIB_MEMORY_BARRIER();
609   b->as_u64 = tmp_b.as_u64;
610   t->active_elements ++;
611   v = vnet_classify_get_entry (t, t->saved_bucket.offset);
612   vnet_classify_entry_free (t, v, old_log2_pages);
613
614  unlock:
615   CLIB_MEMORY_BARRIER();
616   t->writer_lock[0] = 0;
617   return rv;
618 }
619
620 typedef CLIB_PACKED(struct {
621   ethernet_header_t eh;
622   ip4_header_t ip;
623 }) classify_data_or_mask_t;
624
625 u64 vnet_classify_hash_packet (vnet_classify_table_t * t, u8 * h)
626 {
627   return vnet_classify_hash_packet_inline (t, h);      
628 }
629
630 vnet_classify_entry_t * 
631 vnet_classify_find_entry (vnet_classify_table_t * t,
632                           u8 * h, u64 hash, f64 now)
633 {
634   return vnet_classify_find_entry_inline (t, h, hash, now);
635 }
636
637 static u8 * format_classify_entry (u8 * s, va_list * args)
638   {
639   vnet_classify_table_t * t = va_arg (*args, vnet_classify_table_t *);
640   vnet_classify_entry_t * e = va_arg (*args, vnet_classify_entry_t *);
641
642   s = format
643     (s, "[%u]: next_index %d advance %d opaque %d action %d metadata %d\n",
644      vnet_classify_get_offset (t, e), e->next_index, e->advance, 
645      e->opaque_index, e->action, e->metadata);
646
647
648   s = format (s, "        k: %U\n", format_hex_bytes, e->key,
649               t->match_n_vectors * sizeof(u32x4));
650   
651   if (vnet_classify_entry_is_busy (e))
652     s = format (s, "        hits %lld, last_heard %.2f\n",
653                 e->hits, e->last_heard);
654   else
655     s = format (s, "  entry is free\n");
656   return s;
657   }
658  
659 u8 * format_classify_table (u8 * s, va_list * args)
660 {
661   vnet_classify_table_t * t = va_arg (*args, vnet_classify_table_t *);
662   int verbose = va_arg (*args, int);
663   vnet_classify_bucket_t * b;
664   vnet_classify_entry_t * v, * save_v;
665   int i, j, k;
666   u64 active_elements = 0;
667   
668   for (i = 0; i < t->nbuckets; i++)
669     {
670       b = &t->buckets [i];
671       if (b->offset == 0)
672         {
673           if (verbose > 1)
674             s = format (s, "[%d]: empty\n", i);
675           continue;
676         }
677
678       if (verbose)
679         {
680           s = format (s, "[%d]: heap offset %d, elts %d, %s\n", i, 
681                       b->offset, (1<<b->log2_pages)*t->entries_per_page,
682                       b->linear_search ? "LINEAR" : "normal");
683         }
684
685       save_v = vnet_classify_get_entry (t, b->offset);
686       for (j = 0; j < (1<<b->log2_pages); j++)
687         {
688           for (k = 0; k < t->entries_per_page; k++)
689             {
690   
691               v = vnet_classify_entry_at_index (t, save_v, 
692                                                 j*t->entries_per_page + k);
693
694               if (vnet_classify_entry_is_free (v))
695                 {
696                   if (verbose > 1)
697                     s = format (s, "    %d: empty\n", 
698                                 j * t->entries_per_page + k);
699                   continue;
700                 }
701               if (verbose)
702                 {
703                   s = format (s, "    %d: %U\n", 
704                               j * t->entries_per_page + k,
705                               format_classify_entry, t, v);
706                 }
707               active_elements++;
708             }
709         }
710     }
711
712   s = format (s, "    %lld active elements\n", active_elements);
713   s = format (s, "    %d free lists\n", vec_len (t->freelists));
714   s = format (s, "    %d linear-search buckets\n", t->linear_buckets);
715   return s;
716 }
717
718 int vnet_classify_add_del_table (vnet_classify_main_t * cm,
719                                  u8 * mask, 
720                                  u32 nbuckets,
721                                  u32 memory_size,
722                                  u32 skip,
723                                  u32 match,
724                                  u32 next_table_index,
725                                  u32 miss_next_index,
726                                  u32 * table_index,
727                                  u8 current_data_flag,
728                                  i16 current_data_offset,
729                                  int is_add,
730                                  int del_chain)
731 {
732   vnet_classify_table_t * t;
733
734   if (is_add)
735     {
736       if (*table_index == ~0) /* add */
737         {
738           if (memory_size == 0)
739             return VNET_API_ERROR_INVALID_MEMORY_SIZE;
740
741           if (nbuckets == 0)
742             return VNET_API_ERROR_INVALID_VALUE;
743
744           t = vnet_classify_new_table (cm, mask, nbuckets, memory_size,
745             skip, match);
746           t->next_table_index = next_table_index;
747           t->miss_next_index = miss_next_index;
748           t->current_data_flag = current_data_flag;
749           t->current_data_offset = current_data_offset;
750           *table_index = t - cm->tables;
751         }
752       else /* update */
753         {
754           vnet_classify_main_t *cm = &vnet_classify_main;
755           t = pool_elt_at_index (cm->tables, *table_index);
756
757           t->next_table_index = next_table_index;
758         }
759       return 0;
760     }
761   
762   vnet_classify_delete_table_index (cm, *table_index, del_chain);
763   return 0;
764 }
765
766 #define foreach_tcp_proto_field                 \
767 _(src)                                          \
768 _(dst)
769
770 #define foreach_udp_proto_field                 \
771 _(src_port)                                     \
772 _(dst_port)
773
774 #define foreach_ip4_proto_field                 \
775 _(src_address)                                  \
776 _(dst_address)                                  \
777 _(tos)                                          \
778 _(length)                                       \
779 _(fragment_id)                                  \
780 _(ttl)                                          \
781 _(protocol)                                     \
782 _(checksum)
783
784 uword unformat_tcp_mask (unformat_input_t * input, va_list * args)
785 {
786   u8 ** maskp = va_arg (*args, u8 **);
787   u8 * mask = 0;
788   u8 found_something = 0;
789   tcp_header_t * tcp;
790
791 #define _(a) u8 a=0;
792   foreach_tcp_proto_field;
793 #undef _
794
795   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
796     {
797       if (0) ;
798 #define _(a) else if (unformat (input, #a)) a=1;
799       foreach_tcp_proto_field
800 #undef _
801       else
802         break;
803     }
804
805 #define _(a) found_something += a;
806   foreach_tcp_proto_field;
807 #undef _
808
809   if (found_something == 0)
810     return 0;
811
812   vec_validate (mask, sizeof (*tcp) - 1);
813
814   tcp = (tcp_header_t *) mask;
815
816 #define _(a) if (a) memset (&tcp->a, 0xff, sizeof (tcp->a));
817   foreach_tcp_proto_field;
818 #undef _
819
820   *maskp = mask;
821   return 1;
822 }
823
824 uword unformat_udp_mask (unformat_input_t * input, va_list * args)
825 {
826   u8 ** maskp = va_arg (*args, u8 **);
827   u8 * mask = 0;
828   u8 found_something = 0;
829   udp_header_t * udp;
830
831 #define _(a) u8 a=0;
832   foreach_udp_proto_field;
833 #undef _
834
835   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
836     {
837       if (0) ;
838 #define _(a) else if (unformat (input, #a)) a=1;
839       foreach_udp_proto_field
840 #undef _
841       else
842         break;
843     }
844
845 #define _(a) found_something += a;
846   foreach_udp_proto_field;
847 #undef _
848
849   if (found_something == 0)
850     return 0;
851
852   vec_validate (mask, sizeof (*udp) - 1);
853
854   udp = (udp_header_t *) mask;
855
856 #define _(a) if (a) memset (&udp->a, 0xff, sizeof (udp->a));
857   foreach_udp_proto_field;
858 #undef _
859
860   *maskp = mask;
861   return 1;
862 }
863
864 typedef struct {
865   u16 src_port, dst_port;
866 } tcpudp_header_t;
867
868 uword unformat_l4_mask (unformat_input_t * input, va_list * args)
869 {
870   u8 ** maskp = va_arg (*args, u8 **);
871   u16 src_port = 0, dst_port = 0;
872   tcpudp_header_t * tcpudp;
873
874   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
875     {
876       if (unformat (input, "tcp %U", unformat_tcp_mask, maskp))
877         return 1;
878       else if (unformat (input, "udp %U", unformat_udp_mask, maskp))
879         return 1;
880       else if (unformat (input, "src_port"))
881         src_port = 0xFFFF;
882       else if (unformat (input, "dst_port"))
883         dst_port = 0xFFFF;
884       else
885         return 0;
886     }
887
888   if (!src_port && !dst_port)
889     return 0;
890
891   u8 * mask = 0;
892   vec_validate (mask, sizeof (tcpudp_header_t) - 1);
893
894   tcpudp = (tcpudp_header_t *) mask;
895   tcpudp->src_port = src_port;
896   tcpudp->dst_port = dst_port;
897
898   *maskp = mask;
899
900   return 1;
901 }
902
903 uword unformat_ip4_mask (unformat_input_t * input, va_list * args)
904 {
905   u8 ** maskp = va_arg (*args, u8 **);
906   u8 * mask = 0;
907   u8 found_something = 0;
908   ip4_header_t * ip;
909   
910 #define _(a) u8 a=0;
911   foreach_ip4_proto_field;
912 #undef _
913   u8 version = 0;
914   u8 hdr_length = 0;
915   
916   
917   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) 
918     {
919       if (unformat (input, "version")) 
920         version = 1;
921       else if (unformat (input, "hdr_length"))
922         hdr_length = 1;
923       else if (unformat (input, "src"))
924         src_address = 1;
925       else if (unformat (input, "dst"))
926         dst_address = 1;
927       else if (unformat (input, "proto"))
928         protocol = 1;
929       
930 #define _(a) else if (unformat (input, #a)) a=1;
931       foreach_ip4_proto_field
932 #undef _
933       else
934         break;
935     }
936   
937 #define _(a) found_something += a;
938   foreach_ip4_proto_field;
939 #undef _
940   
941   if (found_something == 0)
942     return 0;
943   
944   vec_validate (mask, sizeof (*ip) - 1);
945   
946   ip = (ip4_header_t *) mask;
947   
948 #define _(a) if (a) memset (&ip->a, 0xff, sizeof (ip->a));
949   foreach_ip4_proto_field;
950 #undef _
951   
952   ip->ip_version_and_header_length = 0;
953   
954   if (version)
955     ip->ip_version_and_header_length |= 0xF0;
956   
957   if (hdr_length)
958     ip->ip_version_and_header_length |= 0x0F;
959   
960   *maskp = mask;
961   return 1;
962 }
963
964 #define foreach_ip6_proto_field                 \
965 _(src_address)                                  \
966 _(dst_address)                                  \
967 _(payload_length)                               \
968 _(hop_limit)                                    \
969 _(protocol)
970
971 uword unformat_ip6_mask (unformat_input_t * input, va_list * args)
972 {
973   u8 ** maskp = va_arg (*args, u8 **);
974   u8 * mask = 0;
975   u8 found_something = 0;
976   ip6_header_t * ip;
977   u32 ip_version_traffic_class_and_flow_label;
978   
979 #define _(a) u8 a=0;
980   foreach_ip6_proto_field;
981 #undef _
982   u8 version = 0;
983   u8 traffic_class = 0;
984   u8 flow_label = 0;
985   
986   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) 
987     {
988       if (unformat (input, "version")) 
989         version = 1;
990       else if (unformat (input, "traffic-class"))
991         traffic_class = 1;
992       else if (unformat (input, "flow-label"))
993         flow_label = 1;
994       else if (unformat (input, "src"))
995         src_address = 1;
996       else if (unformat (input, "dst"))
997         dst_address = 1;
998       else if (unformat (input, "proto"))
999         protocol = 1;
1000       
1001 #define _(a) else if (unformat (input, #a)) a=1;
1002       foreach_ip6_proto_field
1003 #undef _
1004       else
1005         break;
1006     }
1007   
1008 #define _(a) found_something += a;
1009   foreach_ip6_proto_field;
1010 #undef _
1011   
1012   if (found_something == 0)
1013     return 0;
1014   
1015   vec_validate (mask, sizeof (*ip) - 1);
1016   
1017   ip = (ip6_header_t *) mask;
1018   
1019 #define _(a) if (a) memset (&ip->a, 0xff, sizeof (ip->a));
1020   foreach_ip6_proto_field;
1021 #undef _
1022   
1023   ip_version_traffic_class_and_flow_label = 0;
1024   
1025   if (version)
1026     ip_version_traffic_class_and_flow_label |= 0xF0000000;
1027
1028   if (traffic_class)
1029     ip_version_traffic_class_and_flow_label |= 0x0FF00000;
1030
1031   if (flow_label)
1032     ip_version_traffic_class_and_flow_label |= 0x000FFFFF;
1033
1034   ip->ip_version_traffic_class_and_flow_label = 
1035     clib_host_to_net_u32 (ip_version_traffic_class_and_flow_label);
1036   
1037   *maskp = mask;
1038   return 1;
1039 }
1040
1041 uword unformat_l3_mask (unformat_input_t * input, va_list * args)
1042 {
1043   u8 ** maskp = va_arg (*args, u8 **);
1044
1045   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
1046     if (unformat (input, "ip4 %U", unformat_ip4_mask, maskp))
1047       return 1;
1048     else if (unformat (input, "ip6 %U", unformat_ip6_mask, maskp))
1049       return 1;
1050     else
1051       break;
1052   }
1053   return 0;
1054 }
1055
1056 uword unformat_l2_mask (unformat_input_t * input, va_list * args)
1057 {
1058   u8 ** maskp = va_arg (*args, u8 **);
1059   u8 * mask = 0;
1060   u8 src = 0;
1061   u8 dst = 0;
1062   u8 proto = 0;
1063   u8 tag1 = 0;
1064   u8 tag2 = 0;
1065   u8 ignore_tag1 = 0;
1066   u8 ignore_tag2 = 0;
1067   u8 cos1 = 0;
1068   u8 cos2 = 0;
1069   u8 dot1q = 0;
1070   u8 dot1ad = 0;
1071   int len = 14;
1072
1073   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
1074     if (unformat (input, "src"))
1075       src = 1;
1076     else if (unformat (input, "dst"))
1077       dst = 1;
1078     else if (unformat (input, "proto"))
1079       proto = 1;
1080     else if (unformat (input, "tag1"))
1081       tag1 = 1;
1082     else if (unformat (input, "tag2"))
1083       tag2 = 1;
1084     else if (unformat (input, "ignore-tag1"))
1085       ignore_tag1 = 1;
1086     else if (unformat (input, "ignore-tag2"))
1087       ignore_tag2 = 1;
1088     else if (unformat (input, "cos1"))
1089       cos1 = 1;
1090     else if (unformat (input, "cos2"))
1091       cos2 = 1;
1092     else if (unformat (input, "dot1q"))
1093       dot1q = 1;
1094     else if (unformat (input, "dot1ad"))
1095       dot1ad = 1;
1096     else
1097       break;
1098   }
1099   if ((src + dst + proto + tag1 + tag2 + dot1q + dot1ad +
1100       ignore_tag1 + ignore_tag2 + cos1 + cos2) == 0)
1101     return 0;
1102
1103   if (tag1 || ignore_tag1 || cos1 || dot1q)
1104     len = 18;
1105   if (tag2 || ignore_tag2 || cos2 || dot1ad)
1106     len = 22;
1107
1108   vec_validate (mask, len-1);
1109
1110   if (dst)
1111     memset (mask, 0xff, 6);
1112
1113   if (src)
1114     memset (mask + 6, 0xff, 6);
1115   
1116   if (tag2 || dot1ad)
1117     {
1118       /* inner vlan tag */
1119       if (tag2)
1120         {
1121           mask[19] = 0xff;
1122           mask[18] = 0x0f;
1123         }
1124       if (cos2)
1125         mask[18] |= 0xe0;
1126       if (proto)
1127         mask[21] = mask [20] = 0xff;
1128       if (tag1)
1129         {
1130           mask [15] = 0xff;
1131           mask [14] = 0x0f;
1132         }
1133       if (cos1)
1134         mask[14] |= 0xe0;
1135       *maskp = mask;
1136       return 1;
1137     }
1138   if (tag1 | dot1q)
1139     {
1140       if (tag1)
1141         {
1142           mask [15] = 0xff;
1143           mask [14] = 0x0f;
1144         }
1145       if (cos1)
1146         mask[14] |= 0xe0;
1147       if (proto)
1148         mask[16] = mask [17] = 0xff;
1149       *maskp = mask;
1150       return 1;
1151     }
1152   if (cos2)
1153     mask[18] |= 0xe0;
1154   if (cos1)
1155     mask[14] |= 0xe0;
1156   if (proto)
1157     mask[12] = mask [13] = 0xff;
1158     
1159   *maskp = mask;
1160   return 1;
1161 }
1162
1163 uword unformat_classify_mask (unformat_input_t * input, va_list * args)
1164 {
1165   u8 ** maskp = va_arg (*args, u8 **);
1166   u32 * skipp = va_arg (*args, u32 *);
1167   u32 * matchp = va_arg (*args, u32 *);
1168   u32 match;
1169   u8 * mask = 0;
1170   u8 * l2 = 0;
1171   u8 * l3 = 0;
1172   u8 * l4 = 0;
1173   int i;
1174   
1175   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
1176     if (unformat (input, "hex %U", unformat_hex_string, &mask))
1177       ;
1178     else if (unformat (input, "l2 %U", unformat_l2_mask, &l2))
1179       ;
1180     else if (unformat (input, "l3 %U", unformat_l3_mask, &l3))
1181       ;
1182     else if (unformat (input, "l4 %U", unformat_l4_mask, &l4))
1183       ;
1184     else
1185       break;
1186   }
1187
1188   if (l4 && !l3) {
1189     vec_free (mask);
1190     vec_free (l2);
1191     vec_free (l4);
1192     return 0;
1193   }
1194
1195   if (mask || l2 || l3 || l4)
1196     {
1197       if (l2 || l3 || l4)
1198         {
1199           /* "With a free Ethernet header in every package" */
1200           if (l2 == 0)
1201             vec_validate (l2, 13);
1202           mask = l2;
1203           if (l3)
1204             {
1205               vec_append (mask, l3);
1206               vec_free (l3);
1207             }
1208           if (l4)
1209             {
1210               vec_append (mask, l4);
1211               vec_free (l4);
1212             }
1213         }
1214
1215       /* Scan forward looking for the first significant mask octet */
1216       for (i = 0; i < vec_len (mask); i++)
1217         if (mask[i])
1218           break;
1219
1220       /* compute (skip, match) params */
1221       *skipp = i / sizeof(u32x4);
1222       vec_delete (mask, *skipp * sizeof(u32x4), 0);
1223
1224       /* Pad mask to an even multiple of the vector size */
1225       while (vec_len (mask) % sizeof (u32x4))
1226         vec_add1 (mask, 0);
1227
1228       match = vec_len (mask) / sizeof (u32x4);
1229
1230       for (i = match*sizeof(u32x4); i > 0; i-= sizeof(u32x4))
1231         {
1232           u64 *tmp = (u64 *)(mask + (i-sizeof(u32x4)));
1233           if (*tmp || *(tmp+1))
1234             break;
1235           match--;
1236         }
1237       if (match == 0)
1238         clib_warning ("BUG: match 0");
1239
1240       _vec_len (mask) = match * sizeof(u32x4);
1241
1242       *matchp = match;
1243       *maskp = mask;
1244
1245       return 1;
1246     }
1247
1248   return 0;
1249 }
1250
1251 #define foreach_l2_input_next                   \
1252 _(drop, DROP)                                   \
1253 _(ethernet, ETHERNET_INPUT)                     \
1254 _(ip4, IP4_INPUT)                               \
1255 _(ip6, IP6_INPUT)                               \
1256 _(li, LI)
1257
1258 uword unformat_l2_input_next_index (unformat_input_t * input, va_list * args)
1259 {
1260   vnet_classify_main_t * cm = &vnet_classify_main;
1261   u32 * miss_next_indexp = va_arg (*args, u32 *);
1262   u32 next_index = 0;
1263   u32 tmp;
1264   int i;
1265   
1266   /* First try registered unformat fns, allowing override... */
1267   for (i = 0; i < vec_len (cm->unformat_l2_next_index_fns); i++)
1268     {
1269       if (unformat (input, "%U", cm->unformat_l2_next_index_fns[i], &tmp))
1270         {
1271           next_index = tmp;
1272           goto out;
1273         }
1274     }
1275
1276 #define _(n,N) \
1277   if (unformat (input, #n)) { next_index = L2_INPUT_CLASSIFY_NEXT_##N; goto out;}
1278   foreach_l2_input_next;
1279 #undef _
1280   
1281   if (unformat (input, "%d", &tmp))
1282     { 
1283       next_index = tmp; 
1284       goto out; 
1285     }
1286   
1287   return 0;
1288
1289  out:
1290   *miss_next_indexp = next_index;
1291   return 1;
1292 }
1293
1294 #define foreach_l2_output_next                   \
1295 _(drop, DROP)
1296
1297 uword unformat_l2_output_next_index (unformat_input_t * input, va_list * args)
1298 {
1299   vnet_classify_main_t * cm = &vnet_classify_main;
1300   u32 * miss_next_indexp = va_arg (*args, u32 *);
1301   u32 next_index = 0;
1302   u32 tmp;
1303   int i;
1304   
1305   /* First try registered unformat fns, allowing override... */
1306   for (i = 0; i < vec_len (cm->unformat_l2_next_index_fns); i++)
1307     {
1308       if (unformat (input, "%U", cm->unformat_l2_next_index_fns[i], &tmp))
1309         {
1310           next_index = tmp;
1311           goto out;
1312         }
1313     }
1314
1315 #define _(n,N) \
1316   if (unformat (input, #n)) { next_index = L2_OUTPUT_CLASSIFY_NEXT_##N; goto out;}
1317   foreach_l2_output_next;
1318 #undef _
1319   
1320   if (unformat (input, "%d", &tmp))
1321     { 
1322       next_index = tmp; 
1323       goto out; 
1324     }
1325   
1326   return 0;
1327
1328  out:
1329   *miss_next_indexp = next_index;
1330   return 1;
1331 }
1332
1333 #define foreach_ip_next                         \
1334 _(drop, DROP)                                   \
1335 _(rewrite, REWRITE)
1336
1337 uword unformat_ip_next_index (unformat_input_t * input, va_list * args)
1338 {
1339   u32 * miss_next_indexp = va_arg (*args, u32 *);
1340   vnet_classify_main_t * cm = &vnet_classify_main;
1341   u32 next_index = 0;
1342   u32 tmp;
1343   int i;
1344   
1345   /* First try registered unformat fns, allowing override... */
1346   for (i = 0; i < vec_len (cm->unformat_ip_next_index_fns); i++)
1347     {
1348       if (unformat (input, "%U", cm->unformat_ip_next_index_fns[i], &tmp))
1349         {
1350           next_index = tmp;
1351           goto out;
1352         }
1353     }
1354
1355 #define _(n,N) \
1356   if (unformat (input, #n)) { next_index = IP_LOOKUP_NEXT_##N; goto out;}
1357   foreach_ip_next;
1358 #undef _
1359   
1360   if (unformat (input, "%d", &tmp))
1361     { 
1362       next_index = tmp; 
1363       goto out; 
1364     }
1365   
1366   return 0;
1367
1368  out:
1369   *miss_next_indexp = next_index;
1370   return 1;
1371 }
1372
1373 #define foreach_acl_next                        \
1374 _(deny, DENY)
1375
1376 uword unformat_acl_next_index (unformat_input_t * input, va_list * args)
1377 {
1378   u32 * next_indexp = va_arg (*args, u32 *);
1379   vnet_classify_main_t * cm = &vnet_classify_main;
1380   u32 next_index = 0;
1381   u32 tmp;
1382   int i;
1383
1384   /* First try registered unformat fns, allowing override... */
1385   for (i = 0; i < vec_len (cm->unformat_acl_next_index_fns); i++)
1386     {
1387       if (unformat (input, "%U", cm->unformat_acl_next_index_fns[i], &tmp))
1388         {
1389           next_index = tmp;
1390           goto out;
1391         }
1392     }
1393
1394 #define _(n,N) \
1395   if (unformat (input, #n)) { next_index = ACL_NEXT_INDEX_##N; goto out;}
1396   foreach_acl_next;
1397 #undef _
1398
1399   if (unformat (input, "permit"))
1400     {
1401       next_index = ~0;
1402       goto out;
1403     }
1404   else if (unformat (input, "%d", &tmp))
1405     {
1406       next_index = tmp;
1407       goto out;
1408     }
1409
1410   return 0;
1411
1412  out:
1413   *next_indexp = next_index;
1414   return 1;
1415 }
1416
1417 uword unformat_policer_next_index (unformat_input_t * input, va_list * args)
1418 {
1419   u32 * next_indexp = va_arg (*args, u32 *);
1420   vnet_classify_main_t * cm = &vnet_classify_main;
1421   u32 next_index = 0;
1422   u32 tmp;
1423   int i;
1424
1425   /* First try registered unformat fns, allowing override... */
1426   for (i = 0; i < vec_len (cm->unformat_policer_next_index_fns); i++)
1427     {
1428       if (unformat (input, "%U", cm->unformat_policer_next_index_fns[i], &tmp))
1429         {
1430           next_index = tmp;
1431           goto out;
1432         }
1433     }
1434
1435   if (unformat (input, "%d", &tmp))
1436     {
1437       next_index = tmp;
1438       goto out;
1439     }
1440
1441   return 0;
1442
1443  out:
1444   *next_indexp = next_index;
1445   return 1;
1446 }
1447
1448 static clib_error_t *
1449 classify_table_command_fn (vlib_main_t * vm,
1450                            unformat_input_t * input,
1451                            vlib_cli_command_t * cmd)
1452 {
1453   u32 nbuckets = 2;
1454   u32 skip = ~0;
1455   u32 match = ~0;
1456   int is_add = 1;
1457   int del_chain = 0;
1458   u32 table_index = ~0;
1459   u32 next_table_index = ~0;
1460   u32 miss_next_index = ~0;
1461   u32 memory_size = 2<<20;
1462   u32 tmp;
1463   u32 current_data_flag = 0;
1464   int current_data_offset = 0;
1465
1466   u8 * mask = 0;
1467   vnet_classify_main_t * cm = &vnet_classify_main;
1468   int rv;
1469
1470   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
1471     if (unformat (input, "del"))
1472       is_add = 0;
1473     else if (unformat (input, "del-chain"))
1474       {
1475         is_add = 0;
1476         del_chain = 1;
1477       }
1478     else if (unformat (input, "buckets %d", &nbuckets))
1479       ;
1480     else if (unformat (input, "skip %d", &skip))
1481       ;
1482     else if (unformat (input, "match %d", &match))
1483       ;
1484     else if (unformat (input, "table %d", &table_index))
1485       ;
1486     else if (unformat (input, "mask %U", unformat_classify_mask, 
1487                        &mask, &skip, &match))
1488       ;
1489     else if (unformat (input, "memory-size %uM", &tmp))
1490       memory_size = tmp<<20;
1491     else if (unformat (input, "memory-size %uG", &tmp))
1492       memory_size = tmp<<30;
1493     else if (unformat (input, "next-table %d", &next_table_index))
1494       ;
1495     else if (unformat (input, "miss-next %U", unformat_ip_next_index,
1496                        &miss_next_index))
1497       ;
1498     else if (unformat (input, "l2-input-miss-next %U", unformat_l2_input_next_index,
1499                        &miss_next_index))
1500         ;
1501     else if (unformat (input, "l2-output-miss-next %U", unformat_l2_output_next_index,
1502                        &miss_next_index))
1503       ;
1504     else if (unformat (input, "acl-miss-next %U", unformat_acl_next_index,
1505                        &miss_next_index))
1506       ;
1507     else if (unformat (input, "current-data-flag %d", &current_data_flag))
1508       ;
1509     else if (unformat (input, "current-data-offset %d", &current_data_offset))
1510       ;
1511
1512     else
1513       break;
1514   }
1515   
1516   if (is_add && mask == 0 && table_index == ~0)
1517     return clib_error_return (0, "Mask required");
1518
1519   if (is_add && skip == ~0 && table_index == ~0)
1520     return clib_error_return (0, "skip count required");
1521
1522   if (is_add && match == ~0 && table_index == ~0)
1523     return clib_error_return (0, "match count required");
1524       
1525   if (!is_add && table_index == ~0)
1526     return clib_error_return (0, "table index required for delete");
1527
1528   rv = vnet_classify_add_del_table (cm, mask, nbuckets, memory_size,
1529         skip, match, next_table_index, miss_next_index, &table_index,
1530         current_data_flag, current_data_offset, is_add, del_chain);
1531   switch (rv)
1532     {
1533     case 0:
1534       break;
1535
1536     default:
1537       return clib_error_return (0, "vnet_classify_add_del_table returned %d",
1538                                 rv);
1539     }
1540   return 0;
1541 }
1542
1543 VLIB_CLI_COMMAND (classify_table, static) = {
1544   .path = "classify table",
1545   .short_help = 
1546   "classify table [miss-next|l2-miss_next|acl-miss-next <next_index>]"
1547   "\n mask <mask-value> buckets <nn> [skip <n>] [match <n>]"
1548   "\n [current-data-flag <n>] [current-data-offset <n>] [table <n>]"
1549   "\n [memory-size <nn>[M][G]] [next-table <n>]"
1550   "\n [del] [del-chain]",
1551   .function = classify_table_command_fn,
1552 };
1553
1554 static u8 * format_vnet_classify_table (u8 * s, va_list * args)
1555 {
1556   vnet_classify_main_t * cm = va_arg (*args, vnet_classify_main_t *);
1557   int verbose = va_arg (*args, int);
1558   u32 index = va_arg (*args, u32);
1559   vnet_classify_table_t * t;
1560
1561   if (index == ~0)
1562     {
1563       s = format (s, "%10s%10s%10s%10s", "TableIdx", "Sessions", "NextTbl",
1564                   "NextNode", verbose ? "Details" : "");
1565       return s;
1566     }
1567
1568   t = pool_elt_at_index (cm->tables, index);
1569   s = format (s, "%10u%10d%10d%10d", index, t->active_elements,
1570               t->next_table_index, t->miss_next_index);
1571
1572   s = format (s, "\n  Heap: %U", format_mheap, t->mheap, 0 /*verbose*/);
1573
1574   s = format (s, "\n  nbuckets %d, skip %d match %d flag %d offset %d",
1575               t->nbuckets, t->skip_n_vectors, t->match_n_vectors,
1576               t->current_data_flag, t->current_data_offset);
1577   s = format (s, "\n  mask %U", format_hex_bytes, t->mask, 
1578               t->match_n_vectors * sizeof (u32x4));
1579   s = format (s, "\n  linear-search buckets %d\n", t->linear_buckets);
1580
1581   if (verbose == 0)
1582     return s;
1583
1584   s = format (s, "\n%U", format_classify_table, t, verbose);
1585   
1586   return s;
1587 }
1588
1589 static clib_error_t *
1590 show_classify_tables_command_fn (vlib_main_t * vm,
1591                                  unformat_input_t * input,
1592                                  vlib_cli_command_t * cmd)
1593 {
1594   vnet_classify_main_t * cm = &vnet_classify_main;
1595   vnet_classify_table_t * t;
1596   u32 match_index = ~0;
1597   u32 * indices = 0;
1598   int verbose = 0;
1599   int i;
1600
1601   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) 
1602     {
1603       if (unformat (input, "index %d", &match_index))
1604         ;
1605       else if (unformat (input, "verbose %d", &verbose))
1606         ;
1607       else if (unformat (input, "verbose"))
1608         verbose = 1;
1609       else 
1610         break;
1611     }
1612   
1613   pool_foreach (t, cm->tables, 
1614   ({
1615     if (match_index == ~0 || (match_index == t - cm->tables))
1616       vec_add1 (indices, t - cm->tables);
1617   }));
1618
1619   if (vec_len(indices))
1620     {
1621       vlib_cli_output (vm, "%U", format_vnet_classify_table, cm, verbose,
1622                        ~0 /* hdr */);
1623       for (i = 0; i < vec_len (indices); i++)
1624         vlib_cli_output (vm, "%U", format_vnet_classify_table, cm, 
1625                          verbose, indices[i]);
1626     }
1627   else
1628     vlib_cli_output (vm, "No classifier tables configured");
1629
1630   vec_free (indices);
1631
1632   return 0;
1633 }
1634
1635 VLIB_CLI_COMMAND (show_classify_table_command, static) = {
1636   .path = "show classify tables",
1637   .short_help = "show classify tables [index <nn>]",
1638   .function = show_classify_tables_command_fn,
1639 };
1640
1641 uword unformat_l4_match (unformat_input_t * input, va_list * args)
1642 {
1643   u8 ** matchp = va_arg (*args, u8 **);
1644
1645   u8 * proto_header = 0;
1646   int src_port = 0;
1647   int dst_port = 0;
1648
1649   tcpudp_header_t h;
1650
1651   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
1652     {
1653       if (unformat (input, "src_port %d", &src_port))
1654         ;
1655       else if (unformat (input, "dst_port %d", &dst_port))
1656         ;
1657       else
1658         return 0;
1659     }
1660
1661   h.src_port = clib_host_to_net_u16(src_port);
1662   h.dst_port = clib_host_to_net_u16(dst_port);
1663   vec_validate(proto_header, sizeof(h)-1);
1664   memcpy(proto_header, &h, sizeof(h));
1665
1666   *matchp = proto_header;
1667
1668   return 1;
1669 }
1670
1671 uword unformat_ip4_match (unformat_input_t * input, va_list * args)
1672 {
1673   u8 ** matchp = va_arg (*args, u8 **);
1674   u8 * match = 0;
1675   ip4_header_t * ip;
1676   int version = 0;
1677   u32 version_val;
1678   int hdr_length = 0;
1679   u32 hdr_length_val;
1680   int src = 0, dst = 0;
1681   ip4_address_t src_val, dst_val;
1682   int proto = 0;
1683   u32 proto_val;
1684   int tos = 0;
1685   u32 tos_val;
1686   int length = 0;
1687   u32 length_val;
1688   int fragment_id = 0;
1689   u32 fragment_id_val;
1690   int ttl = 0;
1691   int ttl_val;
1692   int checksum = 0;
1693   u32 checksum_val;
1694
1695   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) 
1696     {
1697       if (unformat (input, "version %d", &version_val)) 
1698         version = 1;
1699       else if (unformat (input, "hdr_length %d", &hdr_length_val))
1700         hdr_length = 1;
1701       else if (unformat (input, "src %U", unformat_ip4_address, &src_val))
1702         src = 1;
1703       else if (unformat (input, "dst %U", unformat_ip4_address, &dst_val))
1704         dst = 1;
1705       else if (unformat (input, "proto %d", &proto_val))
1706         proto = 1;
1707       else if (unformat (input, "tos %d", &tos_val))
1708         tos = 1;
1709       else if (unformat (input, "length %d", &length_val))
1710         length = 1;
1711       else if (unformat (input, "fragment_id %d", &fragment_id_val))
1712         fragment_id = 1;
1713       else if (unformat (input, "ttl %d", &ttl_val))
1714         ttl = 1;
1715       else if (unformat (input, "checksum %d", &checksum_val))
1716         checksum = 1;
1717       else
1718         break;
1719     }
1720   
1721   if (version + hdr_length + src + dst + proto + tos + length + fragment_id
1722       + ttl + checksum == 0)
1723     return 0;
1724
1725   /* 
1726    * Aligned because we use the real comparison functions
1727    */
1728   vec_validate_aligned (match, sizeof (*ip) - 1, sizeof(u32x4));
1729   
1730   ip = (ip4_header_t *) match;
1731   
1732   /* These are realistically matched in practice */
1733   if (src)
1734     ip->src_address.as_u32 = src_val.as_u32;
1735
1736   if (dst)
1737     ip->dst_address.as_u32 = dst_val.as_u32;
1738   
1739   if (proto)
1740     ip->protocol = proto_val;
1741     
1742
1743   /* These are not, but they're included for completeness */
1744   if (version)
1745     ip->ip_version_and_header_length |= (version_val & 0xF)<<4;
1746
1747   if (hdr_length)
1748     ip->ip_version_and_header_length |= (hdr_length_val & 0xF);
1749     
1750   if (tos)
1751     ip->tos = tos_val;
1752   
1753   if (length)
1754     ip->length = clib_host_to_net_u16 (length_val);
1755   
1756   if (ttl)
1757     ip->ttl = ttl_val;
1758
1759   if (checksum)
1760     ip->checksum = clib_host_to_net_u16 (checksum_val);
1761
1762   *matchp = match;
1763   return 1;
1764 }
1765
1766 uword unformat_ip6_match (unformat_input_t * input, va_list * args)
1767 {
1768   u8 ** matchp = va_arg (*args, u8 **);
1769   u8 * match = 0;
1770   ip6_header_t * ip;
1771   int version = 0;
1772   u32 version_val;
1773   u8  traffic_class = 0;
1774   u32 traffic_class_val;
1775   u8  flow_label = 0;
1776   u8  flow_label_val;
1777   int src = 0, dst = 0;
1778   ip6_address_t src_val, dst_val;
1779   int proto = 0;
1780   u32 proto_val;
1781   int payload_length = 0;
1782   u32 payload_length_val;
1783   int hop_limit = 0;
1784   int hop_limit_val;
1785   u32 ip_version_traffic_class_and_flow_label;
1786
1787   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) 
1788     {
1789       if (unformat (input, "version %d", &version_val)) 
1790         version = 1;
1791       else if (unformat (input, "traffic_class %d", &traffic_class_val))
1792         traffic_class = 1;
1793       else if (unformat (input, "flow_label %d", &flow_label_val))
1794         flow_label = 1;
1795       else if (unformat (input, "src %U", unformat_ip6_address, &src_val))
1796         src = 1;
1797       else if (unformat (input, "dst %U", unformat_ip6_address, &dst_val))
1798         dst = 1;
1799       else if (unformat (input, "proto %d", &proto_val))
1800         proto = 1;
1801       else if (unformat (input, "payload_length %d", &payload_length_val))
1802         payload_length = 1;
1803       else if (unformat (input, "hop_limit %d", &hop_limit_val))
1804         hop_limit = 1;
1805       else
1806         break;
1807     }
1808   
1809   if (version + traffic_class + flow_label + src + dst + proto +
1810       payload_length + hop_limit == 0)
1811     return 0;
1812
1813   /* 
1814    * Aligned because we use the real comparison functions
1815    */
1816   vec_validate_aligned (match, sizeof (*ip) - 1, sizeof(u32x4));
1817   
1818   ip = (ip6_header_t *) match;
1819   
1820   if (src)
1821     clib_memcpy (&ip->src_address, &src_val, sizeof (ip->src_address));
1822
1823   if (dst)
1824     clib_memcpy (&ip->dst_address, &dst_val, sizeof (ip->dst_address));
1825   
1826   if (proto)
1827     ip->protocol = proto_val;
1828     
1829   ip_version_traffic_class_and_flow_label = 0;
1830
1831   if (version)
1832     ip_version_traffic_class_and_flow_label |= (version_val & 0xF) << 28;
1833
1834   if (traffic_class)
1835     ip_version_traffic_class_and_flow_label |= (traffic_class_val & 0xFF) << 20;
1836
1837   if (flow_label)
1838     ip_version_traffic_class_and_flow_label |= (flow_label_val & 0xFFFFF);
1839     
1840   ip->ip_version_traffic_class_and_flow_label = 
1841     clib_host_to_net_u32 (ip_version_traffic_class_and_flow_label);
1842
1843   if (payload_length)
1844     ip->payload_length = clib_host_to_net_u16 (payload_length_val);
1845   
1846   if (hop_limit)
1847     ip->hop_limit = hop_limit_val;
1848
1849   *matchp = match;
1850   return 1;
1851 }
1852
1853 uword unformat_l3_match (unformat_input_t * input, va_list * args)
1854 {
1855   u8 ** matchp = va_arg (*args, u8 **);
1856
1857   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
1858     if (unformat (input, "ip4 %U", unformat_ip4_match, matchp))
1859       return 1;
1860     else if (unformat (input, "ip6 %U", unformat_ip6_match, matchp))
1861       return 1;
1862     /* $$$$ add mpls */
1863     else
1864       break;
1865   }
1866   return 0;
1867 }
1868
1869 uword unformat_vlan_tag (unformat_input_t * input, va_list * args)
1870 {
1871   u8 * tagp = va_arg (*args, u8 *);
1872   u32 tag;
1873
1874   if (unformat(input, "%d", &tag))
1875     {
1876       tagp[0] = (tag>>8) & 0x0F;
1877       tagp[1] = tag & 0xFF;
1878       return 1;
1879     }
1880
1881   return 0;
1882 }
1883
1884 uword unformat_l2_match (unformat_input_t * input, va_list * args)
1885 {
1886   u8 ** matchp = va_arg (*args, u8 **);
1887   u8 * match = 0;
1888   u8 src = 0;
1889   u8 src_val[6];
1890   u8 dst = 0;
1891   u8 dst_val[6];
1892   u8 proto = 0;
1893   u16 proto_val;
1894   u8 tag1 = 0;
1895   u8 tag1_val [2];
1896   u8 tag2 = 0;
1897   u8 tag2_val [2];
1898   int len = 14;
1899   u8 ignore_tag1 = 0;
1900   u8 ignore_tag2 = 0;
1901   u8 cos1 = 0;
1902   u8 cos2 = 0;
1903   u32 cos1_val = 0;
1904   u32 cos2_val = 0;
1905
1906   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
1907     if (unformat (input, "src %U", unformat_ethernet_address, &src_val))
1908       src = 1;
1909     else if (unformat (input, "dst %U", unformat_ethernet_address, &dst_val))
1910       dst = 1;
1911     else if (unformat (input, "proto %U", 
1912                        unformat_ethernet_type_host_byte_order, &proto_val))
1913       proto = 1;
1914     else if (unformat (input, "tag1 %U", unformat_vlan_tag, tag1_val))
1915       tag1 = 1;
1916     else if (unformat (input, "tag2 %U", unformat_vlan_tag, tag2_val))
1917       tag2 = 1;
1918     else if (unformat (input, "ignore-tag1"))
1919       ignore_tag1 = 1;
1920     else if (unformat (input, "ignore-tag2"))
1921       ignore_tag2 = 1;
1922     else if (unformat (input, "cos1 %d", &cos1_val))
1923       cos1 = 1;
1924     else if (unformat (input, "cos2 %d", &cos2_val))
1925       cos2 = 1;
1926     else
1927       break;
1928   }
1929   if ((src + dst + proto + tag1 + tag2 +
1930       ignore_tag1 + ignore_tag2 + cos1 + cos2) == 0)
1931     return 0;
1932
1933   if (tag1 || ignore_tag1 || cos1)
1934     len = 18;
1935   if (tag2 || ignore_tag2 || cos2)
1936     len = 22;
1937
1938   vec_validate_aligned (match, len-1, sizeof(u32x4));
1939
1940   if (dst)
1941     clib_memcpy (match, dst_val, 6);
1942
1943   if (src)
1944     clib_memcpy (match + 6, src_val, 6);
1945   
1946   if (tag2)
1947     {
1948       /* inner vlan tag */
1949       match[19] = tag2_val[1];
1950       match[18] = tag2_val[0];
1951       if (cos2)
1952         match [18] |= (cos2_val & 0x7) << 5;
1953       if (proto)
1954         {
1955           match[21] = proto_val & 0xff;
1956           match[20] = proto_val >> 8;
1957         }
1958       if (tag1)
1959         {
1960           match [15] = tag1_val[1];
1961           match [14] = tag1_val[0];
1962         }
1963       if (cos1)
1964         match [14] |= (cos1_val & 0x7) << 5;
1965       *matchp = match;
1966       return 1;
1967     }
1968   if (tag1)
1969     {
1970       match [15] = tag1_val[1];
1971       match [14] = tag1_val[0];
1972       if (proto)
1973         {
1974           match[17] = proto_val & 0xff;
1975           match[16] = proto_val >> 8;
1976         }
1977       if (cos1)
1978         match [14] |= (cos1_val & 0x7) << 5;
1979
1980       *matchp = match;
1981       return 1;
1982     }
1983   if (cos2)
1984     match [18] |= (cos2_val & 0x7) << 5;
1985   if (cos1)
1986     match [14] |= (cos1_val & 0x7) << 5;
1987   if (proto)
1988     {
1989       match[13] = proto_val & 0xff;
1990       match[12] = proto_val >> 8;
1991     }
1992   
1993   *matchp = match;
1994   return 1;
1995 }
1996
1997
1998 uword unformat_classify_match (unformat_input_t * input, va_list * args)
1999 {
2000   vnet_classify_main_t * cm = va_arg (*args, vnet_classify_main_t *);
2001   u8 ** matchp = va_arg (*args, u8 **);
2002   u32 table_index = va_arg (*args, u32);
2003   vnet_classify_table_t * t;
2004   
2005   u8 * match = 0;
2006   u8 * l2 = 0;
2007   u8 * l3 = 0;
2008   u8 * l4 = 0;
2009
2010   if (pool_is_free_index (cm->tables, table_index))
2011     return 0;
2012
2013   t = pool_elt_at_index (cm->tables, table_index);
2014
2015   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
2016     if (unformat (input, "hex %U", unformat_hex_string, &match))
2017       ;
2018     else if (unformat (input, "l2 %U", unformat_l2_match, &l2))
2019       ;
2020     else if (unformat (input, "l3 %U", unformat_l3_match, &l3))
2021       ;
2022     else if (unformat (input, "l4 %U", unformat_l4_match, &l4))
2023       ;
2024     else
2025       break;
2026   }
2027
2028   if (l4 && !l3) {
2029     vec_free (match);
2030     vec_free (l2);
2031     vec_free (l4);
2032     return 0;
2033   }
2034
2035   if (match || l2 || l3 || l4)
2036     {
2037       if (l2 || l3 || l4)
2038         {
2039           /* "Win a free Ethernet header in every packet" */
2040           if (l2 == 0)
2041             vec_validate_aligned (l2, 13, sizeof(u32x4));
2042           match = l2;
2043           if (l3)
2044             {
2045               vec_append_aligned (match, l3, sizeof(u32x4));
2046               vec_free (l3);
2047             }
2048           if (l4)
2049             {
2050               vec_append_aligned (match, l4, sizeof(u32x4));
2051               vec_free (l4);
2052             }
2053         }
2054
2055       /* Make sure the vector is big enough even if key is all 0's */
2056       vec_validate_aligned 
2057         (match, ((t->match_n_vectors + t->skip_n_vectors) * sizeof(u32x4)) - 1,
2058          sizeof(u32x4));
2059       
2060       /* Set size, include skipped vectors*/
2061       _vec_len (match) = (t->match_n_vectors+t->skip_n_vectors) * sizeof(u32x4);
2062
2063       *matchp = match;
2064
2065       return 1;
2066     }
2067
2068   return 0;
2069 }
2070
2071 int vnet_classify_add_del_session (vnet_classify_main_t * cm, 
2072                                    u32 table_index, 
2073                                    u8 * match, 
2074                                    u32 hit_next_index,
2075                                    u32 opaque_index, 
2076                                    i32 advance,
2077                                    u8 action,
2078                                    u32 metadata,
2079                                    int is_add)
2080 {
2081   vnet_classify_table_t * t;
2082   vnet_classify_entry_5_t _max_e __attribute__((aligned (16)));
2083   vnet_classify_entry_t * e;
2084   int i, rv;
2085
2086   if (pool_is_free_index (cm->tables, table_index))
2087     return VNET_API_ERROR_NO_SUCH_TABLE;
2088   
2089   t = pool_elt_at_index (cm->tables, table_index);
2090   
2091   e = (vnet_classify_entry_t *)&_max_e;
2092   e->next_index = hit_next_index;
2093   e->opaque_index = opaque_index;
2094   e->advance = advance;
2095   e->hits = 0;
2096   e->last_heard = 0;
2097   e->flags = 0;
2098   e->action = action;
2099   if (e->action == CLASSIFY_ACTION_SET_IP4_FIB_INDEX)
2100     e->metadata = fib_table_find_or_create_and_lock (FIB_PROTOCOL_IP4,
2101                                                      metadata,
2102                                                      FIB_SOURCE_CLASSIFY);
2103   else if (e->action == CLASSIFY_ACTION_SET_IP6_FIB_INDEX)
2104     e->metadata = fib_table_find_or_create_and_lock (FIB_PROTOCOL_IP6,
2105                                                      metadata,
2106                                                      FIB_SOURCE_CLASSIFY);
2107   else
2108     e->metadata = 0;
2109
2110   /* Copy key data, honoring skip_n_vectors */
2111   clib_memcpy (&e->key, match + t->skip_n_vectors * sizeof (u32x4),
2112           t->match_n_vectors * sizeof (u32x4));
2113
2114   /* Clear don't-care bits; likely when dynamically creating sessions */
2115   for (i = 0; i < t->match_n_vectors; i++)
2116     e->key[i] &= t->mask[i];
2117
2118   rv = vnet_classify_add_del (t, e, is_add);
2119
2120   vnet_classify_entry_release_resource(e);
2121
2122   if (rv)
2123     return VNET_API_ERROR_NO_SUCH_ENTRY;
2124   return 0;
2125 }
2126
2127 static clib_error_t *
2128 classify_session_command_fn (vlib_main_t * vm,
2129                              unformat_input_t * input,
2130                              vlib_cli_command_t * cmd)
2131 {
2132   vnet_classify_main_t * cm = &vnet_classify_main;
2133   int is_add = 1;
2134   u32 table_index = ~0;
2135   u32 hit_next_index = ~0;
2136   u64 opaque_index = ~0;
2137   u8 * match = 0;
2138   i32 advance = 0;
2139   u32 action = 0;
2140   u32 metadata = 0;
2141   int i, rv;
2142
2143   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) 
2144     {
2145       if (unformat (input, "del"))
2146         is_add = 0;
2147       else if (unformat (input, "hit-next %U", unformat_ip_next_index,
2148                          &hit_next_index))
2149         ;
2150       else if (unformat (input, "l2-input-hit-next %U", unformat_l2_input_next_index,
2151                          &hit_next_index))
2152         ;
2153       else if (unformat (input, "l2-output-hit-next %U", unformat_l2_output_next_index,
2154                          &hit_next_index))
2155         ;
2156       else if (unformat (input, "acl-hit-next %U", unformat_acl_next_index,
2157                          &hit_next_index))
2158         ;
2159       else if (unformat (input, "policer-hit-next %U",
2160                          unformat_policer_next_index, &hit_next_index))
2161         ;
2162       else if (unformat (input, "opaque-index %lld", &opaque_index))
2163         ;
2164       else if (unformat (input, "match %U", unformat_classify_match,
2165                          cm, &match, table_index))
2166         ;
2167       else if (unformat (input, "advance %d", &advance))
2168         ;
2169       else if (unformat (input, "table-index %d", &table_index))
2170         ;
2171       else if (unformat (input, "action set-ip4-fib-id %d", &metadata))
2172         action = 1;
2173       else if (unformat (input, "action set-ip6-fib-id %d", &metadata))
2174         action = 2;
2175       else
2176         {
2177           /* Try registered opaque-index unformat fns */
2178           for (i = 0; i < vec_len (cm->unformat_opaque_index_fns); i++)
2179             {
2180               if (unformat (input, "%U", cm->unformat_opaque_index_fns[i], 
2181                             &opaque_index))
2182                 goto found_opaque;
2183             }
2184           break;
2185         }
2186     found_opaque:
2187       ;
2188     }
2189
2190   if (table_index == ~0)
2191     return clib_error_return (0, "Table index required");
2192
2193   if (is_add && match == 0)
2194     return clib_error_return (0, "Match value required");
2195
2196   rv = vnet_classify_add_del_session (cm, table_index, match, 
2197                                       hit_next_index,
2198                                       opaque_index, advance,
2199                                       action, metadata, is_add);
2200
2201   switch(rv)
2202     {
2203     case 0:
2204       break;
2205
2206     default:
2207       return clib_error_return (0, "vnet_classify_add_del_session returned %d",
2208                                 rv);
2209     }
2210
2211   return 0;
2212 }
2213
2214 VLIB_CLI_COMMAND (classify_session_command, static) = {
2215     .path = "classify session",
2216     .short_help =
2217     "classify session [hit-next|l2-hit-next|"
2218     "acl-hit-next <next_index>|policer-hit-next <policer_name>]"
2219     "\n table-index <nn> match [hex] [l2] [l3 ip4] [opaque-index <index>]"
2220     "\n [action set-ip4-fib-id <n>] [action set-ip6-fib-id <n>] [del]",
2221     .function = classify_session_command_fn,
2222 };
2223
2224 static uword 
2225 unformat_opaque_sw_if_index (unformat_input_t * input, va_list * args)
2226 {
2227   u64 * opaquep = va_arg (*args, u64 *);
2228   u32 sw_if_index;
2229
2230   if (unformat (input, "opaque-sw_if_index %U", unformat_vnet_sw_interface,
2231                 vnet_get_main(), &sw_if_index))
2232     {
2233       *opaquep = sw_if_index;
2234       return 1;
2235     }
2236   return 0;
2237 }
2238
2239 static uword
2240 unformat_ip_next_node (unformat_input_t * input, va_list * args)
2241 {
2242   vnet_classify_main_t * cm = &vnet_classify_main;
2243   u32 * next_indexp = va_arg (*args, u32 *);
2244   u32 node_index;
2245   u32 next_index = ~0;
2246
2247   if (unformat (input, "ip6-node %U", unformat_vlib_node,
2248                 cm->vlib_main, &node_index))
2249     {
2250       next_index = vlib_node_add_next (cm->vlib_main,
2251                                        ip6_classify_node.index, node_index);
2252     }
2253   else if (unformat (input, "ip4-node %U", unformat_vlib_node,
2254                      cm->vlib_main, &node_index))
2255     {
2256       next_index = vlib_node_add_next (cm->vlib_main,
2257                                        ip4_classify_node.index, node_index);
2258     }
2259   else
2260     return 0;
2261
2262   *next_indexp = next_index;
2263   return 1;
2264 }
2265
2266 static uword 
2267 unformat_acl_next_node (unformat_input_t * input, va_list * args)
2268 {
2269   vnet_classify_main_t * cm = &vnet_classify_main;
2270   u32 * next_indexp = va_arg (*args, u32 *);
2271   u32 node_index;
2272   u32 next_index;
2273
2274   if (unformat (input, "ip6-node %U", unformat_vlib_node,
2275                 cm->vlib_main, &node_index))
2276     {
2277       next_index = vlib_node_add_next (cm->vlib_main,
2278                                        ip6_inacl_node.index, node_index);
2279     }
2280   else if (unformat (input, "ip4-node %U", unformat_vlib_node,
2281                      cm->vlib_main, &node_index))
2282     {
2283       next_index = vlib_node_add_next (cm->vlib_main,
2284                                        ip4_inacl_node.index, node_index);
2285     }
2286   else
2287     return 0;
2288
2289   *next_indexp = next_index;
2290   return 1;
2291 }
2292
2293 static uword 
2294 unformat_l2_input_next_node (unformat_input_t * input, va_list * args)
2295 {
2296   vnet_classify_main_t * cm = &vnet_classify_main;
2297   u32 * next_indexp = va_arg (*args, u32 *);
2298   u32 node_index;
2299   u32 next_index;
2300
2301   if (unformat (input, "input-node %U", unformat_vlib_node,
2302                 cm->vlib_main, &node_index))
2303     {
2304       next_index = vlib_node_add_next 
2305         (cm->vlib_main, l2_input_classify_node.index, node_index);
2306
2307       *next_indexp = next_index;
2308       return 1;
2309     }
2310   return 0;
2311 }
2312
2313 static uword 
2314 unformat_l2_output_next_node (unformat_input_t * input, va_list * args)
2315 {
2316   vnet_classify_main_t * cm = &vnet_classify_main;
2317   u32 * next_indexp = va_arg (*args, u32 *);
2318   u32 node_index;
2319   u32 next_index;
2320
2321   if (unformat (input, "output-node %U", unformat_vlib_node,
2322                 cm->vlib_main, &node_index))
2323     {
2324       next_index = vlib_node_add_next 
2325         (cm->vlib_main, l2_output_classify_node.index, node_index);
2326
2327       *next_indexp = next_index;
2328       return 1;
2329     }
2330   return 0;
2331 }
2332
2333 static clib_error_t * 
2334 vnet_classify_init (vlib_main_t * vm)
2335 {
2336   vnet_classify_main_t * cm = &vnet_classify_main;
2337
2338   cm->vlib_main = vm;
2339   cm->vnet_main = vnet_get_main();
2340
2341   vnet_classify_register_unformat_opaque_index_fn 
2342     (unformat_opaque_sw_if_index);
2343
2344   vnet_classify_register_unformat_ip_next_index_fn
2345     (unformat_ip_next_node);
2346
2347   vnet_classify_register_unformat_l2_next_index_fn
2348     (unformat_l2_input_next_node);
2349
2350   vnet_classify_register_unformat_l2_next_index_fn
2351     (unformat_l2_output_next_node);
2352
2353   vnet_classify_register_unformat_acl_next_index_fn
2354     (unformat_acl_next_node);
2355
2356   return 0;
2357 }
2358
2359 VLIB_INIT_FUNCTION (vnet_classify_init);
2360
2361 #define TEST_CODE 1
2362
2363 #if TEST_CODE > 0
2364
2365 typedef struct 
2366 {
2367   ip4_address_t addr;
2368   int in_table;
2369 } test_entry_t;
2370
2371 typedef struct
2372 {
2373   test_entry_t *entries;
2374
2375   /* test parameters */
2376   u32 buckets;
2377   u32 sessions;
2378   u32 iterations;
2379   u32 memory_size;
2380   ip4_address_t src;
2381   vnet_classify_table_t *table;
2382   u32 table_index;
2383   int verbose;
2384
2385   /* Random seed */
2386   u32 seed;
2387
2388   /* Test data */
2389   classify_data_or_mask_t * mask;
2390   classify_data_or_mask_t * data;
2391
2392   /* convenience */
2393   vnet_classify_main_t *classify_main;
2394   vlib_main_t *vlib_main;
2395
2396 } test_classify_main_t;
2397
2398 static test_classify_main_t test_classify_main;
2399
2400 static clib_error_t *
2401 test_classify_churn (test_classify_main_t *tm)
2402 {
2403   classify_data_or_mask_t *mask, *data;
2404   vlib_main_t *vm = tm->vlib_main;
2405   test_entry_t *ep;
2406   u8 *mp = 0, *dp = 0;
2407   u32 tmp;
2408   int i, rv;
2409
2410   vec_validate_aligned (mp, 3 * sizeof(u32x4), sizeof(u32x4));
2411   vec_validate_aligned (dp, 3 * sizeof(u32x4), sizeof(u32x4));
2412
2413   mask = (classify_data_or_mask_t *) mp;
2414   data = (classify_data_or_mask_t *) dp;
2415
2416   /* Mask on src address */
2417   memset (&mask->ip.src_address, 0xff, 4);
2418
2419   tmp = clib_host_to_net_u32 (tm->src.as_u32);
2420
2421   for (i = 0; i < tm->sessions; i++)
2422     {
2423       vec_add2 (tm->entries, ep, 1);
2424       ep->addr.as_u32 = clib_host_to_net_u32 (tmp);
2425       ep->in_table = 0;
2426       tmp++;
2427     }
2428
2429   tm->table = vnet_classify_new_table (tm->classify_main, 
2430                                        (u8 *)mask, 
2431                                        tm->buckets, 
2432                                        tm->memory_size,
2433                                        0 /* skip */,
2434                                        3 /* vectors to match */);
2435   tm->table->miss_next_index = IP_LOOKUP_NEXT_DROP;
2436   tm->table_index = tm->table - tm->classify_main->tables;
2437   vlib_cli_output (vm, "Created table %d, buckets %d", 
2438                    tm->table_index, tm->buckets);
2439
2440   vlib_cli_output (vm, "Initialize: add %d (approx. half of %d sessions)...", 
2441                    tm->sessions/2, tm->sessions);
2442       
2443   for (i = 0; i < tm->sessions/2; i++)
2444     {
2445       ep = vec_elt_at_index (tm->entries, i);
2446
2447       data->ip.src_address.as_u32 = ep->addr.as_u32;
2448       ep->in_table = 1;
2449
2450       rv = vnet_classify_add_del_session (tm->classify_main, 
2451                                           tm->table_index, 
2452                                           (u8 *) data,
2453                                           IP_LOOKUP_NEXT_DROP,
2454                                           i /* opaque_index */, 
2455                                           0 /* advance */, 
2456                                           0 /* action*/, 
2457                                           0 /* metadata */,
2458                                           1 /* is_add */);
2459       
2460       if (rv != 0)
2461         clib_warning ("add: returned %d", rv);
2462
2463       if (tm->verbose)
2464         vlib_cli_output (vm, "add: %U", format_ip4_address, 
2465                          &ep->addr.as_u32);
2466     }
2467
2468   vlib_cli_output (vm, "Execute %d random add/delete operations",
2469                    tm->iterations);
2470
2471   for (i = 0; i < tm->iterations; i++)
2472     {
2473       int index, is_add;
2474
2475       /* Pick a random entry */
2476       index = random_u32 (&tm->seed) % tm->sessions;
2477       
2478       ep = vec_elt_at_index (tm->entries, index);
2479
2480       data->ip.src_address.as_u32 = ep->addr.as_u32;
2481
2482       /* If it's in the table, remove it. Else, add it */
2483       is_add = !ep->in_table;
2484
2485       if (tm->verbose)
2486         vlib_cli_output (vm, "%s: %U", 
2487                          is_add ? "add" : "del",
2488                          format_ip4_address,
2489                          &ep->addr.as_u32);
2490
2491       rv = vnet_classify_add_del_session (tm->classify_main, 
2492                                           tm->table_index, 
2493                                           (u8 *) data,
2494                                           IP_LOOKUP_NEXT_DROP,
2495                                           i /* opaque_index */, 
2496                                           0 /* advance */, 
2497                                           0 /* action*/, 
2498                                           0 /* metadata */,
2499                                           is_add);
2500       if (rv != 0)
2501         vlib_cli_output (vm, 
2502                          "%s[%d]: %U returned %d", is_add ? "add" : "del", 
2503                          index,
2504                          format_ip4_address, 
2505                          &ep->addr.as_u32, rv);
2506       else
2507         ep->in_table = is_add;
2508     }
2509
2510   vlib_cli_output (vm, "Remove remaining %d entries from the table",
2511                    tm->table->active_elements);
2512
2513   for (i = 0; i < tm->sessions; i++)
2514     {
2515       u8 * key_minus_skip;
2516       u64 hash;
2517       vnet_classify_entry_t * e;
2518       
2519       ep = tm->entries + i;
2520       if (ep->in_table == 0)
2521         continue;
2522
2523       data->ip.src_address.as_u32 = ep->addr.as_u32;
2524
2525       hash = vnet_classify_hash_packet (tm->table, (u8 *) data);
2526
2527       e = vnet_classify_find_entry (tm->table, 
2528                                     (u8 *) data, hash, 0 /* time_now */);
2529       if (e == 0)
2530         {
2531           clib_warning ("Couldn't find %U index %d which should be present",
2532                         format_ip4_address, ep->addr, i);
2533           continue;
2534         }
2535
2536       key_minus_skip = (u8 *)e->key;
2537       key_minus_skip -= tm->table->skip_n_vectors * sizeof (u32x4);
2538
2539       rv = vnet_classify_add_del_session 
2540         (tm->classify_main, 
2541          tm->table_index, 
2542          key_minus_skip,
2543          IP_LOOKUP_NEXT_DROP,
2544          i /* opaque_index */, 
2545          0 /* advance */, 0, 0,
2546          0 /* is_add */);
2547
2548       if (rv != 0)
2549         clib_warning ("del: returned %d", rv);
2550
2551       if (tm->verbose)
2552         vlib_cli_output (vm, "del: %U", format_ip4_address,
2553                          &ep->addr.as_u32);
2554     }
2555
2556   vlib_cli_output (vm, "%d entries remain, MUST be zero",
2557                    tm->table->active_elements);
2558
2559   vlib_cli_output (vm, "Table after cleanup: \n%U\n",
2560                    format_classify_table, tm->table, 0 /* verbose */);
2561
2562   vec_free (mp);
2563   vec_free (dp);
2564
2565   vnet_classify_delete_table_index (tm->classify_main,
2566                                     tm->table_index, 1 /* del_chain */);
2567   tm->table = 0;
2568   tm->table_index = ~0;
2569   vec_free(tm->entries);
2570
2571   return 0;
2572 }
2573
2574 static clib_error_t *
2575 test_classify_command_fn (vlib_main_t * vm,
2576                  unformat_input_t * input,
2577                  vlib_cli_command_t * cmd)
2578 {
2579   test_classify_main_t *tm = &test_classify_main;
2580   vnet_classify_main_t * cm = &vnet_classify_main;
2581   u32 tmp;
2582   int which = 0;
2583   clib_error_t * error = 0;
2584   
2585   tm->buckets = 1024;
2586   tm->sessions = 8192;
2587   tm->iterations = 8192;
2588   tm->memory_size = 64<<20;
2589   tm->src.as_u32 = clib_net_to_host_u32 (0x0100000A);
2590   tm->table = 0;
2591   tm->seed = 0xDEADDABE;
2592   tm->classify_main = cm;
2593   tm->vlib_main = vm;
2594   tm->verbose = 0;
2595
2596   /* Default starting address 1.0.0.10 */
2597
2598   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
2599     if (unformat (input, "sessions %d", &tmp))
2600       tm->sessions = tmp;
2601     else if (unformat (input, "src %U", unformat_ip4_address, &tm->src.as_u32))
2602       ;
2603     else if (unformat (input, "buckets %d", &tm->buckets))
2604       ;
2605     else if (unformat (input, "memory-size %uM", &tmp))
2606       tm->memory_size = tmp<<20;
2607     else if (unformat (input, "memory-size %uG", &tmp))
2608       tm->memory_size = tmp<<30;
2609     else if (unformat (input, "seed %d", &tm->seed))
2610       ;
2611     else if (unformat (input, "verbose"))
2612       tm->verbose = 1;
2613
2614     else if (unformat (input, "iterations %d", &tm->iterations))
2615       ;
2616     else if (unformat (input, "churn-test"))
2617       which = 0;
2618     else
2619       break;
2620     }
2621
2622   switch (which)
2623     {
2624     case 0:
2625       error = test_classify_churn (tm);
2626       break;
2627     default:
2628       error = clib_error_return (0, "No such test");
2629       break;
2630     }
2631
2632   return error;
2633 }
2634
2635 VLIB_CLI_COMMAND (test_classify_command, static) = {
2636     .path = "test classify",
2637     .short_help = 
2638     "test classify [src <ip>] [sessions <nn>] [buckets <nn>] [seed <nnn>]\n"
2639     "              [memory-size <nn>[M|G]]\n"
2640     "              [churn-test]",
2641     .function = test_classify_command_fn,
2642 };
2643 #endif /* TEST_CODE */