1 /****************************************************************************
2  *
3  * Copyright (C) 2014-2021 Cisco and/or its affiliates. All rights reserved.
4  * Copyright (C) 2006-2013 Sourcefire, Inc.
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License Version 2 as
8  * published by the Free Software Foundation.  You may not use, modify or
9  * distribute this program under any other version of the GNU General
10  * Public License.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
20  *
21  ****************************************************************************/
22 
23 /*
24  * @file    sfrt.h
25  * @author  Adam Keeton <akeeton@sourcefire.com>
26  * @date    Thu July 20 10:16:26 EDT 2006
27  *
28  * SFRT implements two different routing table lookup methods that have been
29  * adapted to return a void pointers. Any generic information may be
30  * associated with a given IP or CIDR block.
31  *
32  * As of this writing, the two methods used are Stefan Nilsson and Gunnar
33  * Karlsson's LC-trie, and a multibit-trie method similar to Gupta et-al.'s
34  * DIR-n-m.  Presently, the LC-trie is used for testing purposes as the
35  * current implementation does not allow for fast, dynamic inserts.
36  *
37  * The intended use is to associate large IP blocks with specific information;
38  * such as what may be written into the table by RNA.
39  *
40  * NOTE: information should only move from less specific to more specific, ie:
41  *
42  *      First insert:  1.1.0.0/16  ->  some data
43  *      Second insert: 1.1.2.3     ->  some other data
44  *
45  * As opposed to:
46  *
47  *      First insert:  1.1.2.3     ->  some other data
48  *      Second insert: 1.1.0.0/16  ->  some data
49  *
50  * If more general information is to overwrite existing entries, the table
51  * should be free'ed and rebuilt.  This is due to the difficulty of cleaning
52  * out stale entries with the current implementation.  At runtime, this won't
53  * be a significant issue since inserts should apply to specific IP addresses
54  * and not entire blocks of IPs.
55  *
56  *
57  * Implementation:
58  *
59  * The routing tables associate an index into a "data" table with each CIDR.
60  * Each entry in the data table stores a pointer to actual data.  This
61  * implementation was chosen so each routing entry only needs one word to
62  * either index the data array, or point to another table.
63  *
64  * Inserts are performed by specifying a CIDR and a pointer to its associated
65  * data.  Since a new routing table entry may overwrite previous entries,
66  * a flag selects whether the insert favors the most recent or favors the most
67  * specific.  Favoring most specific should be the default behvior.  If
68  * the user wishes to overwrite routing entries with more general data, the
69  * table should be flushed, rather than using favor-most-recent.
70  *
71  * Before modifying the routing or data tables, the insert function performs a
72  * lookup on the CIDR-to-be-insertted.  If no entry or an entry *of differing
73  * bit length* is found, the data is insertted into the data table, and its
74  * index is used for the new routing table entry.  If an entry is found that
75  * is as specific as the new CIDR, the index stored points to where the new
76  * data is written into the data table.
77  *
78  * If more specific CIDR blocks overwrote the data table, then the more
79  * general routing table entries that were not overwritten will be referencing
80  * the wrong data.  Alternatively, less specific entries can only overwrite
81  * existing routing table entries if favor-most-recent inserts are used.
82  *
83  * Because there is no quick way to clean the data-table if a user wishes to
84  * use a favor-most-recent insert for more general data, the user should flush
85  * the table with sfrt_free and create one anew.  Alternatively, a small
86  * memory leak occurs with the data table, as it will be storing pointers that
87  * no routing table entry cares about.
88  *
89  *
90  * The API calls that should be used are:
91  *  sfrt_new    - create new table
92  *  sfrt_insert - insert entry
93  *  sfrt_lookup - lookup entry
94  *  sfrt_free   - free table
95 */
96 
97 #ifndef _SFRT_H_
98 #define _SFRT_H_
99 
100 #include <stdlib.h>
101 #include <sys/types.h>
102 #include "sfrt_trie.h"
103 #include "snort_debug.h"
104 #include "ipv6_port.h"
105 
106 typedef sfcidr_t *IP;
107 typedef void* GENERIC;   /* To be replaced with a pointer to a policy */
108 typedef struct
109 {
110     word index;
111     word length;
112 } tuple_t;
113 
114 
115 #include "sfrt_dir.h"
116 /*#define SUPPORT_LCTRIE */
117 #ifdef SUPPORT_LCTRIE
118 #include "sfrt_lctrie.h"
119 #endif
120 
121 enum types
122 {
123 #ifdef SUPPORT_LCTRIE
124    LCT,
125 #endif
126    DIR_24_8,
127    DIR_16x2,
128    DIR_16_8x2,
129    DIR_16_4x4,
130    DIR_8x4,
131    DIR_4x8,
132    DIR_2x16,
133    DIR_16_4x4_16x5_4x4,
134    DIR_16x7_4x4,
135    DIR_16x8,
136    DIR_8x16,
137    IPv4,
138    IPv6
139 };
140 
141 enum return_codes
142 {
143    RT_SUCCESS=0,
144    RT_INSERT_FAILURE,
145    RT_POLICY_TABLE_EXCEEDED,
146    DIR_INSERT_FAILURE,
147    DIR_LOOKUP_FAILURE,
148    MEM_ALLOC_FAILURE,
149 #ifdef SUPPORT_LCTRIE
150    LCT_COMPILE_FAILURE,
151    LCT_INSERT_FAILURE,
152    LCT_LOOKUP_FAILURE,
153 #endif
154    RT_REMOVE_FAILURE
155 };
156 
157 /* Defined in sfrt.c */
158 extern char *rt_error_messages[];
159 
160 enum
161 {
162    RT_FAVOR_TIME,
163    RT_FAVOR_SPECIFIC,
164    RT_FAVOR_ALL
165 };
166 
167 /*******************************************************************/
168 /* Master table struct.  Abstracts DIR and LC-trie methods         */
169 typedef struct
170 {
171     GENERIC *data;      /* data table. Each IP points to an entry here */
172     uint32_t num_ent;  /* Number of entries in the policy table */
173     uint32_t max_size; /* Max size of policies array */
174     uint32_t lastAllocatedIndex; /* Index allocated last. Search for unused index
175                                     starts from this value and then wraps around at max_size.*/
176     char ip_type;       /* Only IPs of this family will be used */
177     char table_type;
178     uint32_t allocated;
179 
180     void *rt;            /* Actual "routing" table */
181     void *rt6;            /* Actual "routing" table */
182 
183     tuple_t (*lookup)(uint32_t* adr, int numAdrDwords, GENERIC tbl);
184     int (*insert)(uint32_t* adr, int numAdrDwords, int len, word index, int behavior, GENERIC tbl);
185     void (*free)(GENERIC tbl);
186     uint32_t (*usage)(GENERIC tbl);
187     void     (*print)(GENERIC tbl);
188     word (*remove)(uint32_t* adr, int numAdrDwords, int len, int behavior, GENERIC tbl);
189 } table_t;
190 /*******************************************************************/
191 
192 /* Abstracted routing table API */
193 table_t * sfrt_new(char type, char ip_type, long data_size, uint32_t mem_cap);
194 void      sfrt_free(table_t *table);
195 GENERIC sfrt_lookup(sfaddr_t* ip, table_t* table);
196 GENERIC sfrt_search(sfaddr_t* ip, table_t *table);
197 typedef void (*sfrt_iterator_callback)(void *);
198 struct _SnortConfig;
199 typedef void (*sfrt_sc_iterator_callback)(struct _SnortConfig *, void *);
200 typedef int (*sfrt_sc_iterator_callback3)(struct _SnortConfig *, void *);
201 typedef void (*sfrt_iterator_callback2)(void *, void *);
202 typedef int  (*sfrt_iterator_callback3)(void *);
203 void    sfrt_iterate(table_t* table, sfrt_iterator_callback userfunc);
204 void    sfrt_iterate_with_snort_config(struct _SnortConfig *sc, table_t* table, sfrt_sc_iterator_callback userfunc);
205 int     sfrt_iterate2(table_t* table, sfrt_iterator_callback3 userfunc);
206 int     sfrt_iterate2_with_snort_config(struct _SnortConfig *sc, table_t* table, sfrt_sc_iterator_callback3 userfunc);
207 void    sfrt_cleanup(table_t* table, sfrt_iterator_callback userfunc);
208 void    sfrt_cleanup2(table_t*, sfrt_iterator_callback2, void *);
209 int     sfrt_insert(sfcidr_t* ip, unsigned char len, GENERIC ptr,
210                         int behavior, table_t *table);
211 int     sfrt_remove(sfcidr_t* ip, unsigned char len, GENERIC *ptr,
212                         int behavior, table_t *table);
213 uint32_t     sfrt_usage(table_t *table);
214 void    sfrt_print(table_t *table);
215 uint32_t     sfrt_num_entries(table_t *table);
216 
217 /* Perform a lookup on value contained in "ip"
218  * For performance reason, we use this simplified version instead of sfrt_lookup
219  * Note: this only applied to table setting: DIR_8x16 (DIR_16_8_4x2 for IPV4), DIR_8x4*/
sfrt_dir8x_lookup(sfaddr_t * ip,table_t * table)220 static inline GENERIC sfrt_dir8x_lookup(sfaddr_t *ip, table_t* table)
221 {
222     dir_sub_table_t *subtable;
223     int i;
224     void *rt = NULL;
225     int index;
226 
227     if (sfaddr_family(ip) == AF_INET)
228     {
229         rt =  table->rt;
230         subtable = ((dir_table_t *)rt)->sub_table;
231          /* 16 bits*/
232         index = ntohs(ip->ia16[6]);
233         if( !subtable->entries[index] || subtable->lengths[index] )
234         {
235             return table->data[subtable->entries[index]];
236         }
237         subtable = (dir_sub_table_t *) subtable->entries[index];
238 
239         /* 8 bits*/
240         index = ip->ia8[14];
241         if( !subtable->entries[index] || subtable->lengths[index] )
242         {
243             return table->data[subtable->entries[index]];
244         }
245         subtable = (dir_sub_table_t *) subtable->entries[index];
246 
247         /* 4 bits */
248         index = ip->ia8[15] >> 4;
249         if( !subtable->entries[index] || subtable->lengths[index] )
250         {
251             return table->data[subtable->entries[index]];
252         }
253         subtable = (dir_sub_table_t *) subtable->entries[index];
254 
255         /* 4 bits */
256         index = ip->ia8[15] & 0xF;
257         if( !subtable->entries[index] || subtable->lengths[index] )
258         {
259             return table->data[subtable->entries[index]];
260         }
261     }
262     else
263     {
264 
265         rt =  table->rt6;
266         subtable = ((dir_table_t *)rt)->sub_table;
267         for (i = 0; i < 16; i++)
268         {
269             index = ip->ia8[i];
270             if( !subtable->entries[index] || subtable->lengths[index] )
271             {
272                 return table->data[subtable->entries[index]];
273             }
274             subtable = (dir_sub_table_t *) subtable->entries[index];
275         }
276     }
277     return NULL;
278 
279 }
280 
281 #endif
282 
283