1 //--------------------------------------------------------------------------
2 // Copyright (C) 2019-2021 Cisco and/or its affiliates. All rights reserved.
3 //
4 // This program is free software; you can redistribute it and/or modify it
5 // under the terms of the GNU General Public License Version 2 as published
6 // by the Free Software Foundation. You may not use, modify or distribute
7 // this program under any other version of the GNU General Public License.
8 //
9 // This program is distributed in the hope that it will be useful, but
10 // WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 // General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License along
15 // with this program; if not, write to the Free Software Foundation, Inc.,
16 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 //--------------------------------------------------------------------------
18 // http2_hpack_dynamic_table.cc author Katura Harvey <katharve@cisco.com>
19
20 #ifdef HAVE_CONFIG_H
21 #include "config.h"
22 #endif
23
24 #include "http2_hpack_dynamic_table.h"
25 #include "http2_module.h"
26
27 #include <cstring>
28
29 #include "http2_hpack_table.h"
30
31 using namespace Http2Enums;
32
~HpackDynamicTable()33 HpackDynamicTable::~HpackDynamicTable()
34 {
35 for (std::vector<HpackTableEntry*>::iterator it = circular_buf.begin();
36 it != circular_buf.end(); ++it)
37 {
38 delete *it;
39 }
40 }
41
add_entry(const Field & name,const Field & value)42 bool HpackDynamicTable::add_entry(const Field& name, const Field& value)
43 {
44 // The add only fails if the underlying circular array is out of space
45 if (num_entries >= ARRAY_CAPACITY)
46 return false;
47
48 const uint32_t new_entry_size = name.length() + value.length() + RFC_ENTRY_OVERHEAD;
49
50 // As per the RFC, attempting to add an entry that is larger than the max size of the table is
51 // not an error, it causes the table to be cleared
52 if (new_entry_size > max_size)
53 {
54 prune_to_size(0);
55 return true;
56 }
57
58 // Create new entry. This is done before pruning because the entry referenced by the new name
59 // may be pruned.
60 HpackTableEntry* new_entry = new HpackTableEntry(name, value);
61
62 // If add entry would exceed max table size, evict old entries
63 prune_to_size(max_size - new_entry_size);
64
65 // Add new entry to the front of the table (newest entry = lowest index)
66 start = (start + ARRAY_CAPACITY - 1) % ARRAY_CAPACITY;
67 circular_buf[start] = new_entry;
68
69 num_entries++;
70 if (num_entries > Http2Module::get_peg_counts(PEG_MAX_TABLE_ENTRIES))
71 Http2Module::increment_peg_counts(PEG_MAX_TABLE_ENTRIES);
72
73 rfc_table_size += new_entry_size;
74 return true;
75 }
76
get_entry(uint32_t virtual_index) const77 const HpackTableEntry* HpackDynamicTable::get_entry(uint32_t virtual_index) const
78 {
79 const uint32_t dyn_index = virtual_index - HpackIndexTable::STATIC_MAX_INDEX - 1;
80
81 if (dyn_index + 1 > num_entries)
82 return nullptr;
83
84 const uint32_t arr_index = (start + dyn_index) % ARRAY_CAPACITY;
85 return circular_buf[arr_index];
86 }
87
88 /* This is called when adding a new entry and when receiving a dynamic table size update.
89 * If adding the new entry would make the table size exceed the max size, entries are pruned
90 * until the new entry fits. If the dynamic size update is smaller than the current table size,
91 * entries are pruned until the table is no larger than the max size. Entries are pruned least
92 * recently added first.
93 */
prune_to_size(uint32_t new_max_size)94 void HpackDynamicTable::prune_to_size(uint32_t new_max_size)
95 {
96 while (rfc_table_size > new_max_size)
97 {
98 const uint32_t last_index = (start + num_entries - 1 + ARRAY_CAPACITY) % ARRAY_CAPACITY;
99 num_entries--;
100 rfc_table_size -= circular_buf[last_index]->name.length() +
101 circular_buf[last_index]->value.length() + RFC_ENTRY_OVERHEAD;
102 delete circular_buf[last_index];
103 circular_buf[last_index] = nullptr;
104 }
105 }
106
update_size(uint32_t new_size)107 void HpackDynamicTable::update_size(uint32_t new_size)
108 {
109 if (new_size < rfc_table_size)
110 {
111 prune_to_size(new_size);
112 }
113 max_size = new_size;
114 }
115