2
* (C) 2006, 2007 Andreas Gruenbacher <agruen@suse.de>
3
* Copyright (c) 2003-2008 Novell, Inc. (All rights reserved)
4
* Copyright 2009-2012 Canonical Ltd.
6
* The libapparmor library is licensed under the terms of the GNU
7
* Lesser General Public License, version 2.1. Please see the file
10
* This library is distributed in the hope that it will be useful,
11
* but WITHOUT ANY WARRANTY; without even the implied warranty of
12
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13
* GNU Lesser General Public License for more details.
15
* You should have received a copy of the GNU Lesser General Public License
16
* along with this program. If not, see <http://www.gnu.org/licenses/>.
19
* Create a compressed hfa from and hfa
28
#include <arpa/inet.h>
34
#include "../immunix.h"
35
#include "flex-tables.h"
37
void CHFA::init_free_list(vector<pair<size_t, size_t> > &free_list,
38
size_t prev, size_t start)
40
for (size_t i = start; i < free_list.size(); i++) {
42
free_list[prev].second = i;
43
free_list[i].first = prev;
46
free_list[free_list.size() - 1].second = 0;
50
* new Construct the transition table.
52
CHFA::CHFA(DFA &dfa, map<uchar, uchar> &eq, dfaflags_t flags): eq(eq)
54
if (flags & DFA_DUMP_TRANS_PROGRESS)
55
fprintf(stderr, "Compressing HFA:\r");
58
chfaflags = YYTH_FLAG_DIFF_ENCODE;
66
for (map<uchar, uchar>::iterator i = eq.begin();
68
if (i->second > max_eq)
73
/* Do initial setup adding up all the transitions and sorting by
77
multimap<size_t, State *> order;
78
vector<pair<size_t, size_t> > free_list;
80
for (Partition::iterator i = dfa.states.begin(); i != dfa.states.end(); i++) {
81
if (*i == dfa.start || *i == dfa.nonmatching)
83
optimal += (*i)->trans.size();
84
if (flags & DFA_CONTROL_TRANS_HIGH) {
86
if ((*i)->trans.size())
88
(*i)->trans.rbegin()->first -
89
(*i)->trans.begin()->first;
90
size_t ord = ((256 - (*i)->trans.size()) << 8) | (256 - range);
91
/* reverse sort by entry count, most entries first */
92
order.insert(make_pair(ord, *i));
96
/* Insert the dummy nonmatching transition by hand */
97
next_check.push_back(make_pair(dfa.nonmatching, dfa.nonmatching));
98
default_base.push_back(make_pair(dfa.nonmatching, 0));
99
num.insert(make_pair(dfa.nonmatching, num.size()));
101
accept.resize(max(dfa.states.size(), (size_t) 2));
102
accept2.resize(max(dfa.states.size(), (size_t) 2));
103
next_check.resize(max(optimal, (size_t) 256));
104
free_list.resize(next_check.size());
109
init_free_list(free_list, 0, 1);
111
insert_state(free_list, dfa.start, dfa);
114
num.insert(make_pair(dfa.start, num.size()));
118
if (!(flags & DFA_CONTROL_TRANS_HIGH)) {
119
for (Partition::iterator i = dfa.states.begin(); i != dfa.states.end(); i++) {
120
if (*i != dfa.nonmatching && *i != dfa.start) {
121
insert_state(free_list, *i, dfa);
122
accept[num.size()] = (*i)->perms.allow;
123
accept2[num.size()] = PACK_AUDIT_CTL((*i)->perms.audit, (*i)->perms.quiet & (*i)->perms.deny);
124
num.insert(make_pair(*i, num.size()));
126
if (flags & (DFA_DUMP_TRANS_PROGRESS)) {
128
if (count % 100 == 0)
129
fprintf(stderr, "\033[2KCompressing trans table: insert state: %d/%zd\r",
130
count, dfa.states.size());
134
for (multimap<size_t, State *>::iterator i = order.begin();
135
i != order.end(); i++) {
136
if (i->second != dfa.nonmatching &&
137
i->second != dfa.start) {
138
insert_state(free_list, i->second, dfa);
139
accept[num.size()] = i->second->perms.allow;
140
accept2[num.size()] = PACK_AUDIT_CTL(i->second->perms.audit, i->second->perms.quiet & i->second->perms.deny);
141
num.insert(make_pair(i->second, num.size()));
143
if (flags & (DFA_DUMP_TRANS_PROGRESS)) {
145
if (count % 100 == 0)
146
fprintf(stderr, "\033[2KCompressing trans table: insert state: %d/%zd\r",
147
count, dfa.states.size());
152
if (flags & (DFA_DUMP_TRANS_STATS | DFA_DUMP_TRANS_PROGRESS)) {
153
ssize_t size = 4 * next_check.size() + 6 * dfa.states.size();
154
fprintf(stderr, "\033[2KCompressed trans table: states %zd, next/check %zd, optimal next/check %zd avg/state %.2f, compression %zd/%zd = %.2f %%\n",
155
dfa.states.size(), next_check.size(), optimal,
156
(float)next_check.size() / (float)dfa.states.size(),
157
size, 512 * dfa.states.size(),
158
100.0 - ((float)size * 100.0 /(float)(512 * dfa.states.size())));
163
* Does <trans> fit into position <base> of the transition table?
165
bool CHFA::fits_in(vector<pair<size_t, size_t> > &free_list
166
__attribute__ ((unused)), size_t pos,
169
size_t c, base = pos - trans.begin()->first;
170
for (StateTrans::iterator i = trans.begin(); i != trans.end(); i++) {
172
/* if it overflows the next_check array it fits in as we will
174
if (c >= next_check.size())
176
if (next_check[c].second)
184
* Insert <state> of <dfa> into the transition table.
186
void CHFA::insert_state(vector<pair<size_t, size_t> > &free_list,
187
State *from, DFA &dfa)
189
State *default_state = dfa.nonmatching;
193
StateTrans &trans = from->trans;
194
size_t c = trans.begin()->first;
196
size_t x = first_free;
199
default_state = from->otherwise;
205
/* get the first free entry that won't underflow */
206
while (x && (x < c)) {
208
x = free_list[x].second;
211
/* try inserting until we succeed. */
212
while (x && !fits_in(free_list, x, trans)) {
214
x = free_list[x].second;
217
resize = 256 - trans.begin()->first;
218
x = free_list.size();
219
/* set prev to last free */
220
} else if (x + 255 - trans.begin()->first >= next_check.size()) {
221
resize = (255 - trans.begin()->first - (next_check.size() - 1 - x));
222
for (size_t y = x; y; y = free_list[y].second)
226
/* expand next_check and free_list */
227
size_t old_size = free_list.size();
228
next_check.resize(next_check.size() + resize);
229
free_list.resize(free_list.size() + resize);
230
init_free_list(free_list, prev, old_size);
232
first_free = old_size;;
238
for (StateTrans::iterator j = trans.begin(); j != trans.end(); j++) {
239
next_check[base + j->first] = make_pair(j->second, from);
240
size_t prev = free_list[base + j->first].first;
241
size_t next = free_list[base + j->first].second;
243
free_list[prev].second = next;
245
free_list[next].first = prev;
246
if (base + j->first == first_free)
251
if (from->flags & DiffEncodeFlag)
252
base |= DiffEncodeBit32;
253
default_base.push_back(make_pair(default_state, base));
257
* Text-dump the transition table (for debugging).
259
void CHFA::dump(ostream &os)
261
map<size_t, const State *> st;
262
for (map<const State *, size_t>::iterator i = num.begin(); i != num.end(); i++) {
263
st.insert(make_pair(i->second, i->first));
266
os << "size=" << default_base.size() << " (accept, default, base): {state} -> {default state}" << "\n";
267
for (size_t i = 0; i < default_base.size(); i++) {
269
os << "(" << accept[i] << ", " << num[default_base[i].first]
270
<< ", " << default_base[i].second << ")";
273
if (default_base[i].first)
274
os << " -> " << *default_base[i].first;
278
os << "size=" << next_check.size() << " (next, check): {check state} -> {next state} : offset from base\n";
279
for (size_t i = 0; i < next_check.size(); i++) {
280
if (!next_check[i].second)
284
if (next_check[i].second) {
285
os << "(" << num[next_check[i].first] << ", "
286
<< num[next_check[i].second] << ")" << " "
287
<< *next_check[i].second << " -> "
288
<< *next_check[i].first << ": ";
290
size_t offs = i - base_mask_size(default_base[num[next_check[i].second]].second);
301
* Create a flex-style binary dump of the DFA tables. The table format
302
* was partly reverse engineered from the flex sources and from
303
* examining the tables that flex creates with its --tables-file option.
304
* (Only the -Cf and -Ce formats are currently supported.)
307
#define YYTH_REGEX_MAGIC 0x1B5E783D
309
static inline size_t pad64(size_t i)
311
return (i + (size_t) 7) & ~(size_t) 7;
314
string fill64(size_t i)
316
const char zeroes[8] = { };
317
string fill(zeroes, (i & 7) ? 8 - (i & 7) : 0);
321
template<class Iter> size_t flex_table_size(Iter pos, Iter end)
323
return pad64(sizeof(struct table_header) + sizeof(*pos) * (end - pos));
327
void write_flex_table(ostream &os, int id, Iter pos, Iter end)
329
struct table_header td = { 0, 0, 0, 0 };
330
size_t size = end - pos;
332
td.td_id = htons(id);
333
td.td_flags = htons(sizeof(*pos));
334
td.td_lolen = htonl(size);
335
os.write((char *)&td, sizeof(td));
337
for (; pos != end; ++pos) {
338
switch (sizeof(*pos)) {
340
os.put((char)(*pos >> 24));
341
os.put((char)(*pos >> 16));
343
os.put((char)(*pos >> 8));
349
os << fill64(sizeof(td) + sizeof(*pos) * size);
352
void CHFA::flex_table(ostream &os, const char *name)
354
const char th_version[] = "notflex";
355
struct table_set_header th = { 0, 0, 0, 0 };
358
* Change the following two data types to adjust the maximum flex
361
typedef uint16_t state_t;
362
typedef uint32_t trans_t;
364
if (default_base.size() >= (state_t) - 1) {
365
cerr << "Too many states (" << default_base.size() << ") for "
369
if (next_check.size() >= (trans_t) - 1) {
370
cerr << "Too many transitions (" << next_check.size()
371
<< ") for " "type trans_t\n";
376
* Create copies of the data structures so that we can dump the tables
377
* using the generic write_flex_table() routine.
379
vector<uint8_t> equiv_vec;
381
equiv_vec.resize(256);
382
for (map<uchar, uchar>::iterator i = eq.begin(); i != eq.end(); i++) {
383
equiv_vec[i->first] = i->second;
387
vector<state_t> default_vec;
388
vector<trans_t> base_vec;
389
for (DefaultBase::iterator i = default_base.begin(); i != default_base.end(); i++) {
390
default_vec.push_back(num[i->first]);
391
base_vec.push_back(i->second);
394
vector<state_t> next_vec;
395
vector<state_t> check_vec;
396
for (NextCheck::iterator i = next_check.begin(); i != next_check.end(); i++) {
397
next_vec.push_back(num[i->first]);
398
check_vec.push_back(num[i->second]);
401
/* Write the actual flex parser table. */
403
size_t hsize = pad64(sizeof(th) + sizeof(th_version) + strlen(name) + 1);
404
th.th_magic = htonl(YYTH_REGEX_MAGIC);
405
th.th_flags = htonl(chfaflags);
406
th.th_hsize = htonl(hsize);
407
th.th_ssize = htonl(hsize +
408
flex_table_size(accept.begin(), accept.end()) +
409
flex_table_size(accept2.begin(), accept2.end()) +
410
(eq.size() ? flex_table_size(equiv_vec.begin(), equiv_vec.end()) : 0) +
411
flex_table_size(base_vec.begin(), base_vec.end()) +
412
flex_table_size(default_vec.begin(), default_vec.end()) +
413
flex_table_size(next_vec.begin(), next_vec.end()) +
414
flex_table_size(check_vec.begin(), check_vec.end()));
415
os.write((char *)&th, sizeof(th));
416
os << th_version << (char)0 << name << (char)0;
417
os << fill64(sizeof(th) + sizeof(th_version) + strlen(name) + 1);
419
write_flex_table(os, YYTD_ID_ACCEPT, accept.begin(), accept.end());
420
write_flex_table(os, YYTD_ID_ACCEPT2, accept2.begin(), accept2.end());
422
write_flex_table(os, YYTD_ID_EC, equiv_vec.begin(),
424
write_flex_table(os, YYTD_ID_BASE, base_vec.begin(), base_vec.end());
425
write_flex_table(os, YYTD_ID_DEF, default_vec.begin(), default_vec.end());
426
write_flex_table(os, YYTD_ID_NXT, next_vec.begin(), next_vec.end());
427
write_flex_table(os, YYTD_ID_CHK, check_vec.begin(), check_vec.end());
added
removed
parser/libapparmor_re/chfa.cc
