16ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org/* 26ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * rdb.c 36ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 46ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * Implements a replay database for packet security 56ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 66ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * David A. McGrew 76ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * Cisco Systems, Inc. 86ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org */ 96ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 106ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org/* 116ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 126ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * Copyright (c) 2001-2006, Cisco Systems, Inc. 136ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * All rights reserved. 146ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 156ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * Redistribution and use in source and binary forms, with or without 166ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * modification, are permitted provided that the following conditions 176ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * are met: 186ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 196ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * Redistributions of source code must retain the above copyright 206ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * notice, this list of conditions and the following disclaimer. 216ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 226ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * Redistributions in binary form must reproduce the above 236ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * copyright notice, this list of conditions and the following 246ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * disclaimer in the documentation and/or other materials provided 256ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * with the distribution. 266ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 276ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * Neither the name of the Cisco Systems, Inc. nor the names of its 286ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * contributors may be used to endorse or promote products derived 296ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * from this software without specific prior written permission. 306ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 316ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 326ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 336ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 346ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 356ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 366ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 376ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 386ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 396ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 406ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 416ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 426ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * OF THE POSSIBILITY OF SUCH DAMAGE. 436ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 446ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org */ 456ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 466ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 476ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org#include "rdb.h" 486ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 496ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 506ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org/* 516ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * this implementation of a replay database works as follows: 526ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 536ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * window_start is the index of the first packet in the window 546ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * bitmask a bit-buffer, containing the most recently entered 556ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * index as the leftmost bit 566ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 576ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org */ 586ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 596ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org/* rdb_init initalizes rdb */ 606ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 616ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.orgerr_status_t 626ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.orgrdb_init(rdb_t *rdb) { 636ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org v128_set_to_zero(&rdb->bitmask); 646ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org rdb->window_start = 0; 656ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org return err_status_ok; 666ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org} 676ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 686ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org/* 696ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * rdb_check checks to see if index appears in rdb 706ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org */ 716ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 726ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.orgerr_status_t 736ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.orgrdb_check(const rdb_t *rdb, uint32_t p_index) { 746ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 756ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org /* if the index appears after (or at very end of) the window, its good */ 766ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org if (p_index >= rdb->window_start + rdb_bits_in_bitmask) 776ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org return err_status_ok; 786ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 796ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org /* if the index appears before the window, its bad */ 806ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org if (p_index < rdb->window_start) 816ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org return err_status_replay_old; 826ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 836ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org /* otherwise, the index appears within the window, so check the bitmask */ 846ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org if (v128_get_bit(&rdb->bitmask, (p_index - rdb->window_start)) == 1) 856ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org return err_status_replay_fail; 866ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 876ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org /* otherwise, the index is okay */ 886ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org return err_status_ok; 896ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org} 906ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 916ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org/* 926ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * rdb_add_index adds index to rdb_t (and does *not* check if 936ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * index appears in db) 946ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 956ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * this function should be called only after rdb_check has 966ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * indicated that the index does not appear in the rdb, e.g., a mutex 976ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * should protect the rdb between these calls 986ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org */ 996ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 1006ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.orgerr_status_t 1016ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.orgrdb_add_index(rdb_t *rdb, uint32_t p_index) { 1026ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org int delta; 1036ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 1046ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org /* here we *assume* that p_index > rdb->window_start */ 1056ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 1066ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org delta = (p_index - rdb->window_start); 1076ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org if (delta < rdb_bits_in_bitmask) { 1086ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 1096ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org /* if the p_index is within the window, set the appropriate bit */ 1106ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org v128_set_bit(&rdb->bitmask, delta); 1116ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 1126ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org } else { 1136ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 1146ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org delta -= rdb_bits_in_bitmask - 1; 1156ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 1166ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org /* shift the window forward by delta bits*/ 1176ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org v128_left_shift(&rdb->bitmask, delta); 1186ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org v128_set_bit(&rdb->bitmask, rdb_bits_in_bitmask-1); 1196ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org rdb->window_start += delta; 1206ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 1216ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org } 1226ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 1236ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org return err_status_ok; 1246ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org} 1256ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 1266ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.orgerr_status_t 1276ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.orgrdb_increment(rdb_t *rdb) { 1286ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 1296ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org if (rdb->window_start++ > 0x7fffffff) 1306ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org return err_status_key_expired; 1316ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org return err_status_ok; 1326ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org} 1336ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 1346ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.orguint32_t 1356ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.orgrdb_get_value(const rdb_t *rdb) { 1366ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org return rdb->window_start; 1376ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org} 138