michael@0: // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
michael@0: // Use of this source code is governed by a BSD-style license that can be
michael@0: // found in the LICENSE file.
michael@0: 
michael@0: #include <string>
michael@0: #include <map>
michael@0: 
michael@0: #include "sandbox/win/src/policy_low_level.h"
michael@0: #include "base/basictypes.h"
michael@0: 
michael@0: namespace {
michael@0: 
michael@0:   // A single rule can use at most this amount of memory.
michael@0:   const size_t kRuleBufferSize = 1024*4;
michael@0: 
michael@0:   // The possible states of the string matching opcode generator.
michael@0:   enum {
michael@0:     PENDING_NONE,
michael@0:     PENDING_ASTERISK,    // Have seen an '*' but have not generated an opcode.
michael@0:     PENDING_QMARK,       // Have seen an '?' but have not generated an opcode.
michael@0:   };
michael@0: 
michael@0:   // The category of the last character seen by the string matching opcode
michael@0:   // generator.
michael@0:   const uint32 kLastCharIsNone = 0;
michael@0:   const uint32 kLastCharIsAlpha = 1;
michael@0:   const uint32 kLastCharIsWild = 2;
michael@0:   const uint32 kLastCharIsAsterisk = kLastCharIsWild + 4;
michael@0:   const uint32 kLastCharIsQuestionM = kLastCharIsWild + 8;
michael@0: }
michael@0: 
michael@0: namespace sandbox {
michael@0: 
michael@0: // Adding a rule is nothing more than pushing it into an stl container. Done()
michael@0: // is called for the rule in case the code that made the rule in the first
michael@0: // place has not done it.
michael@0: bool LowLevelPolicy::AddRule(int service, PolicyRule* rule) {
michael@0:   if (!rule->Done()) {
michael@0:     return false;
michael@0:   }
michael@0: 
michael@0:   PolicyRule* local_rule = new PolicyRule(*rule);
michael@0:   RuleNode node = {local_rule, service};
michael@0:   rules_.push_back(node);
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: LowLevelPolicy::~LowLevelPolicy() {
michael@0:   // Delete all the rules.
michael@0:   typedef std::list<RuleNode> RuleNodes;
michael@0:   for (RuleNodes::iterator it = rules_.begin(); it != rules_.end(); ++it) {
michael@0:     delete it->rule;
michael@0:   }
michael@0: }
michael@0: 
michael@0: // Here is where the heavy byte shuffling is done. We take all the rules and
michael@0: // 'compile' them into a single memory region. Now, the rules are in random
michael@0: // order so the first step is to reorganize them into a stl map that is keyed
michael@0: // by the service id and as a value contains a list with all the rules that
michael@0: // belong to that service. Then we enter the big for-loop where we carve a
michael@0: // memory zone for the opcodes and the data and call RebindCopy on each rule
michael@0: // so they all end up nicely packed in the policy_store_.
michael@0: bool LowLevelPolicy::Done() {
michael@0:   typedef std::list<RuleNode> RuleNodes;
michael@0:   typedef std::list<const PolicyRule*> RuleList;
michael@0:   typedef std::map<uint32, RuleList> Mmap;
michael@0:   Mmap mmap;
michael@0: 
michael@0:   for (RuleNodes::iterator it = rules_.begin(); it != rules_.end(); ++it) {
michael@0:     mmap[it->service].push_back(it->rule);
michael@0:   }
michael@0: 
michael@0:   PolicyBuffer* current_buffer = &policy_store_->data[0];
michael@0:   char* buffer_end = reinterpret_cast<char*>(current_buffer) +
michael@0:     policy_store_->data_size;
michael@0:   size_t avail_size =  policy_store_->data_size;
michael@0: 
michael@0:   for (Mmap::iterator it = mmap.begin(); it != mmap.end(); ++it) {
michael@0:     uint32 service = (*it).first;
michael@0:     if (service >= kMaxServiceCount) {
michael@0:       return false;
michael@0:     }
michael@0:     policy_store_->entry[service] = current_buffer;
michael@0: 
michael@0:     RuleList::iterator rules_it = (*it).second.begin();
michael@0:     RuleList::iterator rules_it_end = (*it).second.end();
michael@0: 
michael@0:     size_t svc_opcode_count = 0;
michael@0: 
michael@0:     for (; rules_it != rules_it_end; ++rules_it) {
michael@0:       const PolicyRule* rule = (*rules_it);
michael@0:       size_t op_count = rule->GetOpcodeCount();
michael@0: 
michael@0:       size_t opcodes_size = op_count * sizeof(PolicyOpcode);
michael@0:       if (avail_size < opcodes_size) {
michael@0:         return false;
michael@0:       }
michael@0:       size_t data_size = avail_size - opcodes_size;
michael@0:       PolicyOpcode* opcodes_start = &current_buffer->opcodes[svc_opcode_count];
michael@0:       if (!rule->RebindCopy(opcodes_start, opcodes_size,
michael@0:                             buffer_end, &data_size)) {
michael@0:         return false;
michael@0:       }
michael@0:       size_t used = avail_size - data_size;
michael@0:       buffer_end -= used;
michael@0:       avail_size -= used;
michael@0:       svc_opcode_count += op_count;
michael@0:     }
michael@0: 
michael@0:     current_buffer->opcode_count += svc_opcode_count;
michael@0:     size_t policy_byte_count = (svc_opcode_count * sizeof(PolicyOpcode))
michael@0:                                 / sizeof(current_buffer[0]);
michael@0:     current_buffer = &current_buffer[policy_byte_count + 1];
michael@0:   }
michael@0: 
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: PolicyRule::PolicyRule(EvalResult action)
michael@0:     : action_(action), done_(false) {
michael@0:   char* memory = new char[sizeof(PolicyBuffer) + kRuleBufferSize];
michael@0:   buffer_ = reinterpret_cast<PolicyBuffer*>(memory);
michael@0:   buffer_->opcode_count = 0;
michael@0:   opcode_factory_ = new OpcodeFactory(buffer_,
michael@0:                                       kRuleBufferSize + sizeof(PolicyOpcode));
michael@0: }
michael@0: 
michael@0: PolicyRule::PolicyRule(const PolicyRule& other) {
michael@0:   if (this == &other)
michael@0:     return;
michael@0:   action_ = other.action_;
michael@0:   done_ = other.done_;
michael@0:   size_t buffer_size = sizeof(PolicyBuffer) + kRuleBufferSize;
michael@0:   char* memory = new char[buffer_size];
michael@0:   buffer_ = reinterpret_cast<PolicyBuffer*>(memory);
michael@0:   memcpy(buffer_, other.buffer_, buffer_size);
michael@0: 
michael@0:   char* opcode_buffer = reinterpret_cast<char*>(&buffer_->opcodes[0]);
michael@0:   char* next_opcode = &opcode_buffer[GetOpcodeCount() * sizeof(PolicyOpcode)];
michael@0:   opcode_factory_ =
michael@0:       new OpcodeFactory(next_opcode, other.opcode_factory_->memory_size());
michael@0: }
michael@0: 
michael@0: // This function get called from a simple state machine implemented in
michael@0: // AddStringMatch() which passes the current state (in state) and it passes
michael@0: // true in last_call if AddStringMatch() has finished processing the input
michael@0: // pattern string and this would be the last call to generate any pending
michael@0: // opcode. The skip_count is the currently accumulated number of '?' seen so
michael@0: // far and once the associated opcode is generated this function sets it back
michael@0: // to zero.
michael@0: bool PolicyRule::GenStringOpcode(RuleType rule_type,
michael@0:                                  StringMatchOptions match_opts,
michael@0:                                  uint16 parameter, int state, bool last_call,
michael@0:                                  int* skip_count, std::wstring* fragment) {
michael@0: 
michael@0:   // The last opcode must:
michael@0:   //   1) Always clear the context.
michael@0:   //   2) Preserve the negation.
michael@0:   //   3) Remove the 'OR' mode flag.
michael@0:   uint32 options = kPolNone;
michael@0:   if (last_call) {
michael@0:     if (IF_NOT == rule_type) {
michael@0:       options = kPolClearContext | kPolNegateEval;
michael@0:     } else {
michael@0:       options = kPolClearContext;
michael@0:     }
michael@0:   } else if (IF_NOT == rule_type) {
michael@0:     options = kPolUseOREval | kPolNegateEval;
michael@0:   }
michael@0: 
michael@0:   PolicyOpcode* op = NULL;
michael@0: 
michael@0:   // The fragment string contains the accumulated characters to match with, it
michael@0:   // never contains wildcards (unless they have been escaped) and while there
michael@0:   // is no fragment there is no new string match opcode to generate.
michael@0:   if (fragment->empty()) {
michael@0:     // There is no new opcode to generate but in the last call we have to fix
michael@0:     // the previous opcode because it was really the last but we did not know
michael@0:     // it at that time.
michael@0:     if (last_call && (buffer_->opcode_count > 0)) {
michael@0:       op = &buffer_->opcodes[buffer_->opcode_count - 1];
michael@0:       op->SetOptions(options);
michael@0:     }
michael@0:     return true;
michael@0:   }
michael@0: 
michael@0:   if (PENDING_ASTERISK == state) {
michael@0:     if (last_call) {
michael@0:       op = opcode_factory_->MakeOpWStringMatch(parameter, fragment->c_str(),
michael@0:                                                kSeekToEnd, match_opts,
michael@0:                                                options);
michael@0:     } else {
michael@0:       op = opcode_factory_->MakeOpWStringMatch(parameter, fragment->c_str(),
michael@0:                                                kSeekForward, match_opts,
michael@0:                                                options);
michael@0:     }
michael@0: 
michael@0:   } else if (PENDING_QMARK == state) {
michael@0:     op = opcode_factory_->MakeOpWStringMatch(parameter, fragment->c_str(),
michael@0:                                              *skip_count, match_opts, options);
michael@0:     *skip_count = 0;
michael@0:   } else {
michael@0:     if (last_call) {
michael@0:       match_opts = static_cast<StringMatchOptions>(EXACT_LENGHT | match_opts);
michael@0:     }
michael@0:     op = opcode_factory_->MakeOpWStringMatch(parameter, fragment->c_str(), 0,
michael@0:                                              match_opts, options);
michael@0:   }
michael@0:   if (NULL == op) {
michael@0:     return false;
michael@0:   }
michael@0:   ++buffer_->opcode_count;
michael@0:   fragment->clear();
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: bool PolicyRule::AddStringMatch(RuleType rule_type, int16 parameter,
michael@0:                                 const wchar_t* string,
michael@0:                                 StringMatchOptions match_opts) {
michael@0:   if (done_) {
michael@0:     // Do not allow to add more rules after generating the action opcode.
michael@0:     return false;
michael@0:   }
michael@0: 
michael@0:   const wchar_t* current_char = string;
michael@0:   uint32 last_char = kLastCharIsNone;
michael@0:   int state = PENDING_NONE;
michael@0:   int skip_count = 0;       // counts how many '?' we have seen in a row.
michael@0:   std::wstring fragment;    // accumulates the non-wildcard part of the string.
michael@0: 
michael@0:   while (L'\0' != *current_char) {
michael@0:     switch (*current_char) {
michael@0:       case L'*':
michael@0:         if (kLastCharIsWild & last_char) {
michael@0:           // '**' and '&*' is an error.
michael@0:           return false;
michael@0:         }
michael@0:         if (!GenStringOpcode(rule_type, match_opts, parameter,
michael@0:                              state, false, &skip_count, &fragment)) {
michael@0:           return false;
michael@0:         }
michael@0:         last_char = kLastCharIsAsterisk;
michael@0:         state = PENDING_ASTERISK;
michael@0:         break;
michael@0:       case L'?':
michael@0:         if (kLastCharIsAsterisk == last_char) {
michael@0:           // '*?' is an error.
michael@0:           return false;
michael@0:         }
michael@0:         if (!GenStringOpcode(rule_type, match_opts, parameter,
michael@0:                              state, false, &skip_count, &fragment)) {
michael@0:           return false;
michael@0:         }
michael@0:         ++skip_count;
michael@0:         last_char = kLastCharIsQuestionM;
michael@0:         state = PENDING_QMARK;
michael@0:         break;
michael@0:       case L'/':
michael@0:         // Note: "/?" is an escaped '?'. Eat the slash and fall through.
michael@0:         if (L'?' == current_char[1]) {
michael@0:           ++current_char;
michael@0:         }
michael@0:       default:
michael@0:         fragment += *current_char;
michael@0:         last_char = kLastCharIsAlpha;
michael@0:     }
michael@0:     ++current_char;
michael@0:   }
michael@0: 
michael@0:   if (!GenStringOpcode(rule_type, match_opts, parameter,
michael@0:                        state, true, &skip_count, &fragment)) {
michael@0:     return false;
michael@0:   }
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: bool PolicyRule::AddNumberMatch(RuleType rule_type, int16 parameter,
michael@0:                                 unsigned long number, RuleOp comparison_op) {
michael@0:   if (done_) {
michael@0:     // Do not allow to add more rules after generating the action opcode.
michael@0:     return false;
michael@0:   }
michael@0:   uint32 opts = (rule_type == IF_NOT)? kPolNegateEval : kPolNone;
michael@0: 
michael@0:   if (EQUAL == comparison_op) {
michael@0:     if (NULL == opcode_factory_->MakeOpNumberMatch(parameter, number, opts)) {
michael@0:       return false;
michael@0:     }
michael@0:   } else if (AND == comparison_op) {
michael@0:     if (NULL == opcode_factory_->MakeOpUlongAndMatch(parameter, number, opts)) {
michael@0:       return false;
michael@0:     }
michael@0:   }
michael@0:   ++buffer_->opcode_count;
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: bool PolicyRule::Done() {
michael@0:   if (done_) {
michael@0:     return true;
michael@0:   }
michael@0:   if (NULL == opcode_factory_->MakeOpAction(action_, kPolNone)) {
michael@0:     return false;
michael@0:   }
michael@0:   ++buffer_->opcode_count;
michael@0:   done_ = true;
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: bool PolicyRule::RebindCopy(PolicyOpcode* opcode_start, size_t opcode_size,
michael@0:                             char* data_start, size_t* data_size) const {
michael@0:   size_t count = buffer_->opcode_count;
michael@0:   for (size_t ix = 0; ix != count; ++ix) {
michael@0:     if (opcode_size < sizeof(PolicyOpcode)) {
michael@0:       return false;
michael@0:     }
michael@0:     PolicyOpcode& opcode = buffer_->opcodes[ix];
michael@0:     *opcode_start = opcode;
michael@0:     if (OP_WSTRING_MATCH == opcode.GetID()) {
michael@0:       // For this opcode argument 0 is a delta to the string and argument 1
michael@0:       // is the length (in chars) of the string.
michael@0:       const wchar_t* str = opcode.GetRelativeString(0);
michael@0:       size_t str_len;
michael@0:       opcode.GetArgument(1, &str_len);
michael@0:       str_len = str_len * sizeof(wchar_t);
michael@0:       if ((*data_size) < str_len) {
michael@0:         return false;
michael@0:       }
michael@0:       *data_size -= str_len;
michael@0:       data_start -= str_len;
michael@0:       memcpy(data_start, str, str_len);
michael@0:       // Recompute the string displacement
michael@0:       ptrdiff_t delta = data_start - reinterpret_cast<char*>(opcode_start);
michael@0:       opcode_start->SetArgument(0, delta);
michael@0:     }
michael@0:     ++opcode_start;
michael@0:     opcode_size -= sizeof(PolicyOpcode);
michael@0:   }
michael@0: 
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: PolicyRule::~PolicyRule() {
michael@0:   delete [] reinterpret_cast<char*>(buffer_);
michael@0:   delete opcode_factory_;
michael@0: }
michael@0: 
michael@0: }  // namespace sandbox