Intial Thumb2 Sandbox (naclrev 6680)

src/trusted/validator_arm/address_set.cc

 /*
  * Copyright 2009 The Native Client Authors.  All rights reserved.
  * Use of this source code is governed by a BSD-style license that can
  * be found in the LICENSE file.
  * Copyright 2009, Google Inc.
  */
 
 #include "native_client/src/trusted/validator_arm/address_set.h"
 #include <stdio.h>
 #include <string.h>
 
+#define ADDRFACTOR sizeof(uint16_t)
+#define BITSINADDRF (ADDRFACTOR * 8)
+#define RUPADDR    (ADDRFACTOR - 1)
+
 namespace nacl_arm_val {
 
 AddressSet::AddressSet(uint32_t base, uint32_t size)
-    : base_(base), size_(size), bits_(new uint32_t[(size + 3) / 4]) {
-  memset(bits_, 0, sizeof(uint32_t) * ((size + 3) / 4));
+    : base_(base), size_(size),
+      bits_(new uint32_t[(size + RUPADDR) / ADDRFACTOR]) {

[bsy, 2011/09/28 00:31:13]

as discussed, this is a bit vector the max size of which depends on the sandbox
model: the |size| parameter is the address space size but on arm we only care
about |address| div 4 (in add, contains, etc), and on thumb2 we care about
|address| div 2.

i think this should be templated or otherwise parameterized according to the
sandbox model.  in particular, this CL would have the same AddressSet be used
for both arm and thumb2, and when used for arm the sequence

AddressSet as;
as.add(n);  // n is 0 mod 4, within size, etc.
CHECK(as.contains(n+2));

would pass on the original code but fail with the CL applied.

+  memset(bits_, 0, sizeof(uint32_t) * ((size + RUPADDR) / ADDRFACTOR));
 }
 
 AddressSet::~AddressSet() {
   delete[] bits_;
 }
 
 void AddressSet::add(uint32_t address) {
   if ((address - base_) < size_) {
-    uint32_t word_address = (address - base_) / sizeof(uint32_t);
+    uint32_t word_address = (address - base_) / ADDRFACTOR;
 
     bits_[word_address / 32] |= 1 << (word_address % 32);

[bsy, 2011/09/27 23:27:28]

this should be BITSINADDRF instead of 32 in both of these.

[bsy, 2011/09/28 00:31:13]

this code was correct.  my apologies.

it would be nice if the code were more obviously correct....

   }
 }
 
 bool AddressSet::contains(uint32_t address) const {
   if ((address - base_) < size_) {
-    uint32_t word_address = (address - base_) / sizeof(uint32_t);
+    uint32_t word_address = (address - base_) / ADDRFACTOR;
 
     return bits_[word_address / 32] & (1 << (word_address % 32));

[bsy, 2011/09/27 23:27:28]

ditto

[bsy, 2011/09/28 00:31:13]

ditto

   } else {
     return false;
   }
 }
 
 AddressSet::Iterator AddressSet::begin() const {
   return Iterator(*this, 0, 0);
 }
 
 AddressSet::Iterator AddressSet::end() const {
-  return Iterator(*this, (size_ + 3) / 4, 0);
+  return Iterator(*this, (size_ + RUPADDR) / ADDRFACTOR, 0);
 }
 
 AddressSet::Iterator::Iterator(const AddressSet &parent,
                                uint32_t index,
                                uint32_t shift)
     : parent_(parent), index_(index), shift_(shift) {
   advance();
 }
 
 AddressSet::Iterator &AddressSet::Iterator::operator++() {
   shift_++;   // Skip the current bit, if any, and
   advance();  // seek to the next 1 bit.
   return *this;
 }
 
 bool AddressSet::Iterator::operator!=(const AddressSet::Iterator &other) const {
   return index_ != other.index_ || shift_ != other.shift_;
 }
 
 uint32_t AddressSet::Iterator::operator*() const {
-  return parent_.base_ + 4 * ((index_ * 32) + shift_);
+  return parent_.base_ + ADDRFACTOR * ((index_ * 32) + shift_);

[bsy, 2011/09/27 23:27:28]

should this be 32?

 }
 
 void AddressSet::Iterator::advance() {
-  uint32_t max_index = (parent_.size_ + 3) / 4;
+  uint32_t max_index = (parent_.size_ + RUPADDR) / ADDRFACTOR;
 
   for (; index_ < max_index; index_++) {
     uint32_t word = (shift_ > 31)? 0 : parent_.bits_[index_] >> shift_;
     while (word) {
       if (word & 1) return;
 
       // A meager optimization for sparse words
       if (!(word & 0xFFFF)) {
         word >>= 16;
         shift_ += 16;
       } else if (!(word & 0xFF)) {
         word >>= 8;
         shift_ += 8;
       } else {
         word >>= 1;
         shift_++;
       }
     }
     shift_ = 0;
   }
 }
 
 }  // namespace