1/*
2 * rdbx.h
3 *
4 * replay database with extended packet indices, using a rollover counter
5 *
6 * David A. McGrew
7 * Cisco Systems, Inc.
8 *
9 */
10/*
11 *
12 * Copyright (c) 2001-2006, Cisco Systems, Inc.
13 * All rights reserved.
14 *
15 * Redistribution and use in source and binary forms, with or without
16 * modification, are permitted provided that the following conditions
17 * are met:
18 *
19 *   Redistributions of source code must retain the above copyright
20 *   notice, this list of conditions and the following disclaimer.
21 *
22 *   Redistributions in binary form must reproduce the above
23 *   copyright notice, this list of conditions and the following
24 *   disclaimer in the documentation and/or other materials provided
25 *   with the distribution.
26 *
27 *   Neither the name of the Cisco Systems, Inc. nor the names of its
28 *   contributors may be used to endorse or promote products derived
29 *   from this software without specific prior written permission.
30 *
31 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
32 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
33 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
34 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
35 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
36 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
37 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
38 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
39 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
40 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
41 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
42 * OF THE POSSIBILITY OF SUCH DAMAGE.
43 *
44 */
45
46#ifndef RDBX_H
47#define RDBX_H
48
49#include "datatypes.h"
50#include "err.h"
51
52/* #define ROC_TEST */
53
54#ifndef ROC_TEST
55
56typedef uint16_t sequence_number_t;   /* 16 bit sequence number  */
57typedef uint32_t rollover_counter_t;   /* 32 bit rollover counter */
58
59#else  /* use small seq_num and roc datatypes for testing purposes */
60
61typedef unsigned char sequence_number_t;         /* 8 bit sequence number   */
62typedef uint16_t rollover_counter_t;   /* 16 bit rollover counter */
63
64#endif
65
66#define seq_num_median (1 << (8*sizeof(sequence_number_t) - 1))
67#define seq_num_max    (1 << (8*sizeof(sequence_number_t)))
68
69/*
70 * An xtd_seq_num_t is a 64-bit unsigned integer used as an 'extended'
71 * sequence number.
72 */
73
74typedef uint64_t xtd_seq_num_t;
75
76
77/*
78 * An rdbx_t is a replay database with extended range; it uses an
79 * xtd_seq_num_t and a bitmask of recently received indices.
80 */
81
82typedef struct {
83  xtd_seq_num_t index;
84  bitvector_t bitmask;
85} rdbx_t;
86
87
88/*
89 * rdbx_init(rdbx_ptr, ws)
90 *
91 * initializes the rdbx pointed to by its argument with the window size ws,
92 * setting the rollover counter and sequence number to zero
93 */
94
95err_status_t
96rdbx_init(rdbx_t *rdbx, unsigned long ws);
97
98
99/*
100 * rdbx_dealloc(rdbx_ptr)
101 *
102 * frees memory associated with the rdbx
103 */
104
105err_status_t
106rdbx_dealloc(rdbx_t *rdbx);
107
108
109/*
110 * rdbx_estimate_index(rdbx, guess, s)
111 *
112 * given an rdbx and a sequence number s (from a newly arrived packet),
113 * sets the contents of *guess to contain the best guess of the packet
114 * index to which s corresponds, and returns the difference between
115 * *guess and the locally stored synch info
116 */
117
118int
119rdbx_estimate_index(const rdbx_t *rdbx,
120		    xtd_seq_num_t *guess,
121		    sequence_number_t s);
122
123/*
124 * rdbx_check(rdbx, delta);
125 *
126 * rdbx_check(&r, delta) checks to see if the xtd_seq_num_t
127 * which is at rdbx->window_start + delta is in the rdb
128 *
129 */
130
131err_status_t
132rdbx_check(const rdbx_t *rdbx, int difference);
133
134/*
135 * replay_add_index(rdbx, delta)
136 *
137 * adds the xtd_seq_num_t at rdbx->window_start + delta to replay_db
138 * (and does *not* check if that xtd_seq_num_t appears in db)
139 *
140 * this function should be called *only* after replay_check has
141 * indicated that the index does not appear in the rdbx, and a mutex
142 * should protect the rdbx between these calls if necessary.
143 */
144
145err_status_t
146rdbx_add_index(rdbx_t *rdbx, int delta);
147
148
149/*
150 * rdbx_set_roc(rdbx, roc) initalizes the rdbx_t at the location rdbx
151 * to have the rollover counter value roc.  If that value is less than
152 * the current rollover counter value, then the function returns
153 * err_status_replay_old; otherwise, err_status_ok is returned.
154 *
155 */
156
157err_status_t
158rdbx_set_roc(rdbx_t *rdbx, uint32_t roc);
159
160/*
161 * rdbx_get_roc(rdbx) returns the value of the rollover counter for
162 * the rdbx_t pointed to by rdbx
163 *
164 */
165
166xtd_seq_num_t
167rdbx_get_packet_index(const rdbx_t *rdbx);
168
169/*
170 * xtd_seq_num_t functions - these are *internal* functions of rdbx, and
171 * shouldn't be used to manipulate rdbx internal values.  use the rdbx
172 * api instead!
173 */
174
175/*
176 * rdbx_get_ws(rdbx_ptr)
177 *
178 * gets the window size which was used to initialize the rdbx
179 */
180
181unsigned long
182rdbx_get_window_size(const rdbx_t *rdbx);
183
184
185/* index_init(&pi) initializes a packet index pi (sets it to zero) */
186
187void
188index_init(xtd_seq_num_t *pi);
189
190/* index_advance(&pi, s) advances a xtd_seq_num_t forward by s */
191
192void
193index_advance(xtd_seq_num_t *pi, sequence_number_t s);
194
195
196/*
197 * index_guess(local, guess, s)
198 *
199 * given a xtd_seq_num_t local (which represents the highest
200 * known-to-be-good index) and a sequence number s (from a newly
201 * arrived packet), sets the contents of *guess to contain the best
202 * guess of the packet index to which s corresponds, and returns the
203 * difference between *guess and *local
204 */
205
206int
207index_guess(const xtd_seq_num_t *local,
208		   xtd_seq_num_t *guess,
209		   sequence_number_t s);
210
211
212#endif /* RDBX_H */
213
214
215
216
217
218
219
220
221
222