1 // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
8 #include "sandbox/win/src/policy_low_level.h"
9 #include "base/basictypes.h"
13 // A single rule can use at most this amount of memory.
14 const size_t kRuleBufferSize
= 1024*4;
16 // The possible states of the string matching opcode generator.
19 PENDING_ASTERISK
, // Have seen an '*' but have not generated an opcode.
20 PENDING_QMARK
, // Have seen an '?' but have not generated an opcode.
23 // The category of the last character seen by the string matching opcode
25 const uint32 kLastCharIsNone
= 0;
26 const uint32 kLastCharIsAlpha
= 1;
27 const uint32 kLastCharIsWild
= 2;
28 const uint32 kLastCharIsAsterisk
= kLastCharIsWild
+ 4;
29 const uint32 kLastCharIsQuestionM
= kLastCharIsWild
+ 8;
34 // Adding a rule is nothing more than pushing it into an stl container. Done()
35 // is called for the rule in case the code that made the rule in the first
36 // place has not done it.
37 bool LowLevelPolicy::AddRule(int service
, PolicyRule
* rule
) {
42 PolicyRule
* local_rule
= new PolicyRule(*rule
);
43 RuleNode node
= {local_rule
, service
};
44 rules_
.push_back(node
);
48 LowLevelPolicy::~LowLevelPolicy() {
49 // Delete all the rules.
50 typedef std::list
<RuleNode
> RuleNodes
;
51 for (RuleNodes::iterator it
= rules_
.begin(); it
!= rules_
.end(); ++it
) {
56 // Here is where the heavy byte shuffling is done. We take all the rules and
57 // 'compile' them into a single memory region. Now, the rules are in random
58 // order so the first step is to reorganize them into a stl map that is keyed
59 // by the service id and as a value contains a list with all the rules that
60 // belong to that service. Then we enter the big for-loop where we carve a
61 // memory zone for the opcodes and the data and call RebindCopy on each rule
62 // so they all end up nicely packed in the policy_store_.
63 bool LowLevelPolicy::Done() {
64 typedef std::list
<RuleNode
> RuleNodes
;
65 typedef std::list
<const PolicyRule
*> RuleList
;
66 typedef std::map
<uint32
, RuleList
> Mmap
;
69 for (RuleNodes::iterator it
= rules_
.begin(); it
!= rules_
.end(); ++it
) {
70 mmap
[it
->service
].push_back(it
->rule
);
73 PolicyBuffer
* current_buffer
= &policy_store_
->data
[0];
74 char* buffer_end
= reinterpret_cast<char*>(current_buffer
) +
75 policy_store_
->data_size
;
76 size_t avail_size
= policy_store_
->data_size
;
78 for (Mmap::iterator it
= mmap
.begin(); it
!= mmap
.end(); ++it
) {
79 uint32 service
= (*it
).first
;
80 if (service
>= kMaxServiceCount
) {
83 policy_store_
->entry
[service
] = current_buffer
;
85 RuleList::iterator rules_it
= (*it
).second
.begin();
86 RuleList::iterator rules_it_end
= (*it
).second
.end();
88 size_t svc_opcode_count
= 0;
90 for (; rules_it
!= rules_it_end
; ++rules_it
) {
91 const PolicyRule
* rule
= (*rules_it
);
92 size_t op_count
= rule
->GetOpcodeCount();
94 size_t opcodes_size
= op_count
* sizeof(PolicyOpcode
);
95 if (avail_size
< opcodes_size
) {
98 size_t data_size
= avail_size
- opcodes_size
;
99 PolicyOpcode
* opcodes_start
= ¤t_buffer
->opcodes
[svc_opcode_count
];
100 if (!rule
->RebindCopy(opcodes_start
, opcodes_size
,
101 buffer_end
, &data_size
)) {
104 size_t used
= avail_size
- data_size
;
107 svc_opcode_count
+= op_count
;
110 current_buffer
->opcode_count
+= svc_opcode_count
;
111 size_t policy_byte_count
= (svc_opcode_count
* sizeof(PolicyOpcode
))
112 / sizeof(current_buffer
[0]);
113 current_buffer
= ¤t_buffer
[policy_byte_count
+ 1];
119 PolicyRule::PolicyRule(EvalResult action
)
120 : action_(action
), done_(false) {
121 char* memory
= new char[sizeof(PolicyBuffer
) + kRuleBufferSize
];
122 buffer_
= reinterpret_cast<PolicyBuffer
*>(memory
);
123 buffer_
->opcode_count
= 0;
124 opcode_factory_
= new OpcodeFactory(buffer_
,
125 kRuleBufferSize
+ sizeof(PolicyOpcode
));
128 PolicyRule::PolicyRule(const PolicyRule
& other
) {
131 action_
= other
.action_
;
133 size_t buffer_size
= sizeof(PolicyBuffer
) + kRuleBufferSize
;
134 char* memory
= new char[buffer_size
];
135 buffer_
= reinterpret_cast<PolicyBuffer
*>(memory
);
136 memcpy(buffer_
, other
.buffer_
, buffer_size
);
138 char* opcode_buffer
= reinterpret_cast<char*>(&buffer_
->opcodes
[0]);
139 char* next_opcode
= &opcode_buffer
[GetOpcodeCount() * sizeof(PolicyOpcode
)];
141 new OpcodeFactory(next_opcode
, other
.opcode_factory_
->memory_size());
144 // This function get called from a simple state machine implemented in
145 // AddStringMatch() which passes the current state (in state) and it passes
146 // true in last_call if AddStringMatch() has finished processing the input
147 // pattern string and this would be the last call to generate any pending
148 // opcode. The skip_count is the currently accumulated number of '?' seen so
149 // far and once the associated opcode is generated this function sets it back
151 bool PolicyRule::GenStringOpcode(RuleType rule_type
,
152 StringMatchOptions match_opts
,
153 uint16 parameter
, int state
, bool last_call
,
154 int* skip_count
, base::string16
* fragment
) {
156 // The last opcode must:
157 // 1) Always clear the context.
158 // 2) Preserve the negation.
159 // 3) Remove the 'OR' mode flag.
160 uint32 options
= kPolNone
;
162 if (IF_NOT
== rule_type
) {
163 options
= kPolClearContext
| kPolNegateEval
;
165 options
= kPolClearContext
;
167 } else if (IF_NOT
== rule_type
) {
168 options
= kPolUseOREval
| kPolNegateEval
;
171 PolicyOpcode
* op
= NULL
;
173 // The fragment string contains the accumulated characters to match with, it
174 // never contains wildcards (unless they have been escaped) and while there
175 // is no fragment there is no new string match opcode to generate.
176 if (fragment
->empty()) {
177 // There is no new opcode to generate but in the last call we have to fix
178 // the previous opcode because it was really the last but we did not know
180 if (last_call
&& (buffer_
->opcode_count
> 0)) {
181 op
= &buffer_
->opcodes
[buffer_
->opcode_count
- 1];
182 op
->SetOptions(options
);
187 if (PENDING_ASTERISK
== state
) {
189 op
= opcode_factory_
->MakeOpWStringMatch(parameter
, fragment
->c_str(),
190 kSeekToEnd
, match_opts
,
193 op
= opcode_factory_
->MakeOpWStringMatch(parameter
, fragment
->c_str(),
194 kSeekForward
, match_opts
,
198 } else if (PENDING_QMARK
== state
) {
199 op
= opcode_factory_
->MakeOpWStringMatch(parameter
, fragment
->c_str(),
200 *skip_count
, match_opts
, options
);
204 match_opts
= static_cast<StringMatchOptions
>(EXACT_LENGHT
| match_opts
);
206 op
= opcode_factory_
->MakeOpWStringMatch(parameter
, fragment
->c_str(), 0,
207 match_opts
, options
);
212 ++buffer_
->opcode_count
;
217 bool PolicyRule::AddStringMatch(RuleType rule_type
, int16 parameter
,
218 const wchar_t* string
,
219 StringMatchOptions match_opts
) {
221 // Do not allow to add more rules after generating the action opcode.
225 const wchar_t* current_char
= string
;
226 uint32 last_char
= kLastCharIsNone
;
227 int state
= PENDING_NONE
;
228 int skip_count
= 0; // counts how many '?' we have seen in a row.
229 base::string16 fragment
; // accumulates the non-wildcard part.
231 while (L
'\0' != *current_char
) {
232 switch (*current_char
) {
234 if (kLastCharIsWild
& last_char
) {
235 // '**' and '&*' is an error.
238 if (!GenStringOpcode(rule_type
, match_opts
, parameter
,
239 state
, false, &skip_count
, &fragment
)) {
242 last_char
= kLastCharIsAsterisk
;
243 state
= PENDING_ASTERISK
;
246 if (kLastCharIsAsterisk
== last_char
) {
250 if (!GenStringOpcode(rule_type
, match_opts
, parameter
,
251 state
, false, &skip_count
, &fragment
)) {
255 last_char
= kLastCharIsQuestionM
;
256 state
= PENDING_QMARK
;
259 // Note: "/?" is an escaped '?'. Eat the slash and fall through.
260 if (L
'?' == current_char
[1]) {
264 fragment
+= *current_char
;
265 last_char
= kLastCharIsAlpha
;
270 if (!GenStringOpcode(rule_type
, match_opts
, parameter
,
271 state
, true, &skip_count
, &fragment
)) {
277 bool PolicyRule::AddNumberMatch(RuleType rule_type
,
280 RuleOp comparison_op
) {
282 // Do not allow to add more rules after generating the action opcode.
285 uint32 opts
= (rule_type
== IF_NOT
)? kPolNegateEval
: kPolNone
;
287 if (EQUAL
== comparison_op
) {
288 if (NULL
== opcode_factory_
->MakeOpNumberMatch(parameter
, number
, opts
)) {
291 } else if (AND
== comparison_op
) {
292 if (NULL
== opcode_factory_
->MakeOpNumberAndMatch(parameter
, number
,
297 ++buffer_
->opcode_count
;
301 bool PolicyRule::Done() {
305 if (NULL
== opcode_factory_
->MakeOpAction(action_
, kPolNone
)) {
308 ++buffer_
->opcode_count
;
313 bool PolicyRule::RebindCopy(PolicyOpcode
* opcode_start
, size_t opcode_size
,
314 char* data_start
, size_t* data_size
) const {
315 size_t count
= buffer_
->opcode_count
;
316 for (size_t ix
= 0; ix
!= count
; ++ix
) {
317 if (opcode_size
< sizeof(PolicyOpcode
)) {
320 PolicyOpcode
& opcode
= buffer_
->opcodes
[ix
];
321 *opcode_start
= opcode
;
322 if (OP_WSTRING_MATCH
== opcode
.GetID()) {
323 // For this opcode argument 0 is a delta to the string and argument 1
324 // is the length (in chars) of the string.
325 const wchar_t* str
= opcode
.GetRelativeString(0);
327 opcode
.GetArgument(1, &str_len
);
328 str_len
= str_len
* sizeof(wchar_t);
329 if ((*data_size
) < str_len
) {
332 *data_size
-= str_len
;
333 data_start
-= str_len
;
334 memcpy(data_start
, str
, str_len
);
335 // Recompute the string displacement
336 ptrdiff_t delta
= data_start
- reinterpret_cast<char*>(opcode_start
);
337 opcode_start
->SetArgument(0, delta
);
340 opcode_size
-= sizeof(PolicyOpcode
);
346 PolicyRule::~PolicyRule() {
347 delete [] reinterpret_cast<char*>(buffer_
);
348 delete opcode_factory_
;
351 } // namespace sandbox