1/*
2  Ido Barnea
3  Cisco Systems, Inc.
4*/
5
6/*
7  Copyright (c) 2016-2016 Cisco Systems, Inc.
8
9  Licensed under the Apache License, Version 2.0 (the "License");
10  you may not use this file except in compliance with the License.
11  You may obtain a copy of the License at
12
13  http://www.apache.org/licenses/LICENSE-2.0
14
15  Unless required by applicable law or agreed to in writing, software
16  distributed under the License is distributed on an "AS IS" BASIS,
17  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18  See the License for the specific language governing permissions and
19  limitations under the License.
20*/
21
22#include <assert.h>
23#include <stdint.h>
24#include <string>
25#include <iostream>
26#include <new>
27#include "nat_check_flow_table.h"
28/*
29  classes in this file:
30  CNatCheckFlowTableList - List implementation
31  CNatCheckFlowTableMap - Map implementation
32  CNatData - element of data that exists in the map and the list.
33  CNatCheckFlowTable - Wrapper class which is the interface to outside.
34  New element is always inserted to the list and map.
35  If element is removed, it is always removed from list and map together.
36  Map is used to lookup elemnt by key.
37  List is used to clean up old elements by timestamp. We guarantee the list is always sorted by timestamp,
38  since we always insert at the end, with increasing timestamp.
39*/
40
41std::ostream& operator<<(std::ostream& os, const CNatData &cn) {
42    os << "(" << &cn << ")" << "data:" << cn.m_data << " time:" << cn.m_timestamp;
43    os << " prev:" << cn.m_prev << " next:" << cn.m_next;
44    return os;
45}
46
47// map implementation
48CNatData *CNatCheckFlowTableMap::erase(uint64_t key) {
49    nat_check_flow_map_iter_no_const_t it = m_map.find(key);
50
51    if (it != m_map.end()) {
52        CNatData *val = it->second;
53        m_map.erase(it);
54        return val;
55    }
56
57    return NULL;
58}
59
60bool CNatCheckFlowTableMap::find(uint64_t key, uint32_t &val) {
61    nat_check_flow_map_iter_t it = m_map.find(key);
62
63    if (it != m_map.end()) {
64        CNatData *data = it->second;
65        val = data->get_data();
66        return true;
67    }
68
69    return false;
70}
71
72// for testing
73bool CNatCheckFlowTableMap::verify(uint32_t *arr, int size) {
74    uint32_t val = -1;
75    int real_size = 0;
76
77    for (int i = 0; i < size; i++) {
78        if (arr[i] == -1)
79            continue;
80        real_size++;
81        find(i, val);
82        if (val != arr[i])
83            return false;
84    }
85
86    if (m_map.size() != real_size) {
87        std::cout << "Error: Wrong map size " << m_map.size() << ". Should be " << real_size << std::endl;
88        return false;
89    }
90
91    return true;
92}
93
94CNatData * CNatCheckFlowTableMap::insert(uint64_t key, uint32_t val, double time) {
95    CNatData *elem = new CNatData;
96    assert(elem);
97    elem->set_data(val);
98    elem->set_key(key);
99    elem->set_timestamp(time);
100    std::pair<uint64_t, CNatData *> pair = std::pair<uint64_t, CNatData *>(key, elem);
101
102    if (m_map.insert(pair).second == false) {
103        delete elem;
104        return NULL;
105    } else {
106        return elem;
107    }
108}
109
110std::ostream& operator<<(std::ostream& os, const CNatCheckFlowTableMap& cf) {
111    nat_check_flow_map_iter_t it;
112
113    os << "NAT check flow table map:\n";
114    for (it = cf.m_map.begin(); it != cf.m_map.end(); it++) {
115        CNatData *data = it->second;
116        uint32_t key = it->first;
117        os << "  " << key << ":" << *data << std::endl;
118    }
119    return os;
120}
121
122void CNatCheckFlowTableList::dump_short(FILE *fd) {
123    fprintf(fd, "list:\n");
124    // this is not fully safe, since we call it from CP core, and rx core changes the list.
125    // It is usefull as a debug function
126    if (m_head) {
127        fprintf(fd, "  head: time:%f key:%x data:%x\n", m_head->get_timestamp(), m_head->get_key(), m_head->get_data());
128        fprintf(fd, "  tail: time:%f key:%x data:%x\n", m_tail->get_timestamp(), m_tail->get_key(), m_tail->get_data());
129    }
130}
131
132// list implementation
133// The list is always sorted by timestamp, since we always insert at the end, with increasing timestamp
134void CNatCheckFlowTableList::erase(CNatData *data) {
135    if (m_head == data) {
136        m_head = data->m_next;
137    }
138    if (m_tail == data) {
139        m_tail = data->m_prev;
140    }
141    if (data->m_prev) {
142        data->m_prev->m_next = data->m_next;
143    }
144    if (data->m_next) {
145        data->m_next->m_prev = data->m_prev;
146    }
147}
148
149// insert as last element in list
150void CNatCheckFlowTableList::insert(CNatData *data) {
151    data->m_prev = m_tail;
152    data->m_next = NULL;
153
154    if (m_tail != NULL) {
155        m_tail->m_next = data;
156    } else {
157        // if m_tail is NULL m_head is also NULL
158        m_head = data;
159    }
160    m_tail = data;
161}
162
163bool CNatCheckFlowTableList::verify(uint32_t *arr, int size) {
164    int index = -1;
165    CNatData *elem = m_head;
166    int count = 0;
167
168    while (index < size - 1) {
169        index++;
170        if (arr[index] == -1) {
171            continue;
172        }
173        count++;
174
175        if (elem->get_data() != arr[index]) {
176            return false;
177        }
178
179        if (elem == NULL) {
180            std::cout << "Too few items in list. Only " << count << std::endl;
181            return false;
182        }
183        elem = elem->m_next;
184    }
185
186    // We expect number of items in list to be like num of val!=-1 in arr
187    if (elem != NULL) {
188        std::cout << "Too many items in list" << std::endl;
189        return false;
190    }
191
192    return true;
193}
194
195std::ostream& operator<<(std::ostream& os, const CNatCheckFlowTableList& cf) {
196    CNatData *it = cf.m_head;
197
198    os << "NAT check flow table list:\n";
199    os << "  head:" << cf.m_head << " tail:" << cf.m_tail << std::endl;
200    while (it != NULL) {
201        os << "  " << *it  << std::endl;
202        it = it->m_next;
203    }
204
205    return os;
206}
207
208// flow table
209std::ostream& operator<<(std::ostream& os, const CNatCheckFlowTable& cf) {
210    os << "========= Flow table start =========" << std::endl;
211    os << cf.m_map;
212    os << cf.m_list;
213    os << "========= Flow table end =========" << std::endl;
214
215    return os;
216}
217
218void CNatCheckFlowTable::clear_old(double time) {
219    CNatData *data = m_list.get_head();
220    uint32_t val;
221
222    while (data) {
223        if (data->get_timestamp() < time) {
224            erase(data->get_key(), val);
225            data = m_list.get_head();
226        } else {
227            break;
228        }
229    }
230}
231
232void CNatCheckFlowTable::dump(FILE *fd) {
233    fprintf(fd, "map size:%lu\n", m_map.size());
234    m_list.dump_short(fd);
235}
236
237bool CNatCheckFlowTable::erase(uint64_t key, uint32_t &val) {
238    CNatData *data = m_map.erase(key);
239
240    if (!data)
241        return false;
242
243    val = data->get_data();
244    m_list.erase(data);
245    delete data;
246
247    return true;
248}
249
250bool CNatCheckFlowTable::insert(uint64_t key, uint32_t val, double time) {
251    CNatData *res;
252
253    res = m_map.insert(key, val, time);
254    if (!res) {
255        return false;
256    } else {
257        m_list.insert(res);
258    }
259    return true;
260}
261
262CNatCheckFlowTable::~CNatCheckFlowTable() {
263    clear_old(UINT64_MAX);
264}
265
266bool CNatCheckFlowTable::test() {
267    uint32_t size = 100;
268    uint32_t arr[size];
269    int i;
270    uint32_t val;
271
272    for (i = 0; i < size; i++) {
273        arr[i] = i+200;
274    }
275
276    // insert some elements
277    for (i = 0; i < size; i++) {
278        val = arr[i];
279        assert(insert(i, val, i) == true);
280    }
281
282    // insert same elements. should fail
283    for (i = 0; i < size; i++) {
284        val = arr[i];
285        assert(insert(i, val, val) == false);
286    }
287
288    // remove element we did not insert
289    assert(erase(size, val) == false);
290
291    assert (m_map.verify(arr, size) == true);
292    assert (m_list.verify(arr, size) == true);
293
294    // remove even keys
295    for (i = 0; i < size; i += 2) {
296        assert(erase(i, val) == true);
297        assert (val == arr[i]);
298        arr[i] = -1;
299    }
300
301    assert (m_map.verify(arr, size) == true);
302    assert (m_list.verify(arr, size) == true);
303
304    // clear half of the old values (We removed the even already, so 1/4 should be left)
305    clear_old(size/2);
306    for (i = 0; i < size/2; i++) {
307        arr [i] = -1;
308    }
309
310    assert (m_map.verify(arr, size) == true);
311    assert (m_list.verify(arr, size) == true);
312
313    return true;
314}
315