js/src/ds/Bitmap.h
author Nika Layzell <nika@thelayzells.com>
Wed, 16 Sep 2020 20:47:55 +0000
changeset 549331 ab7d302fd3186b10ada9264528c80f6840e44571
parent 548864 85cff42af3a321f95791fb66cde1aff70107693c
permissions -rw-r--r--
Bug 1659696 - Check PendingInitialization before targeting in window.open, r=kmag This requires adding the flag as a synced field on the BrowsingContext, and checking it in a few more places. Attempts to open a new window in this racy manner will now raise an exception. This should avoid the issue from bug 1658854 by blocking the buggy attempts to load before the nested event loop has been exited. Differential Revision: https://phabricator.services.mozilla.com/D87927

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * vim: set ts=8 sts=2 et sw=2 tw=80:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef ds_Bitmap_h
#define ds_Bitmap_h

#include "mozilla/Array.h"
#include "mozilla/Assertions.h"
#include "mozilla/Attributes.h"
#include "mozilla/MemoryChecking.h"

#include <algorithm>
#include <stddef.h>
#include <stdint.h>

#include "js/AllocPolicy.h"
#include "js/HashTable.h"
#include "js/HeapAPI.h"
#include "js/Vector.h"

// This file provides two classes for representing bitmaps.
//
// DenseBitmap is an array of words of bits, with size linear in the maximum
// bit which has been set on it.
//
// SparseBitmap provides a reasonably simple, reasonably efficient (in time and
// space) implementation of a sparse bitmap. The basic representation is a hash
// table whose entries are fixed length malloc'ed blocks of bits.

namespace js {

class DenseBitmap {
  using Data = Vector<uintptr_t, 0, SystemAllocPolicy>;

  Data data;

 public:
  size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) {
    return data.sizeOfExcludingThis(mallocSizeOf);
  }

  bool ensureSpace(size_t numWords) {
    MOZ_ASSERT(data.empty());
    return data.appendN(0, numWords);
  }

  size_t numWords() const { return data.length(); }
  uintptr_t word(size_t i) const { return data[i]; }
  uintptr_t& word(size_t i) { return data[i]; }

  template <typename T>
  typename std::enable_if_t<std::is_convertible_v<T, uintptr_t>, void>
  copyBitsFrom(size_t wordStart, size_t numWords, T* source) {
    MOZ_ASSERT(wordStart + numWords <= data.length());
    for (size_t i = 0; i < numWords; i++) {
      data[wordStart + i] = source[i];
    }
  }

  template <typename T>
  typename std::enable_if_t<std::is_convertible_v<T, uintptr_t>, void>
  bitwiseOrRangeInto(size_t wordStart, size_t numWords, T* target) const {
    for (size_t i = 0; i < numWords; i++) {
      target[i] |= data[wordStart + i];
    }
  }
};

class SparseBitmap {
  // The number of words of bits to use for each block mainly affects the
  // memory usage of the bitmap. To minimize overhead, bitmaps which are
  // expected to be fairly dense should have a large block size, and bitmaps
  // which are expected to be very sparse should have a small block size.
  static const size_t WordsInBlock = 4096 / sizeof(uintptr_t);

  using BitBlock = mozilla::Array<uintptr_t, WordsInBlock>;
  using Data =
      HashMap<size_t, BitBlock*, DefaultHasher<size_t>, SystemAllocPolicy>;

  Data data;

  static size_t blockStartWord(size_t word) {
    return word & ~(WordsInBlock - 1);
  }

  // Return the number of words in a BitBlock starting at |blockWord| which
  // are in |other|.
  static size_t wordIntersectCount(size_t blockWord, const DenseBitmap& other) {
    long count = other.numWords() - blockWord;
    return std::min<size_t>((size_t)WordsInBlock, std::max<long>(count, 0));
  }

  BitBlock& createBlock(Data::AddPtr p, size_t blockId,
                        AutoEnterOOMUnsafeRegion& oomUnsafe);

  BitBlock* createBlock(Data::AddPtr p, size_t blockId);

  MOZ_ALWAYS_INLINE BitBlock* getBlock(size_t blockId) const {
    Data::Ptr p = data.lookup(blockId);
    return p ? p->value() : nullptr;
  }

  MOZ_ALWAYS_INLINE BitBlock& getOrCreateBlock(size_t blockId) {
    // The lookupForAdd() needs protection against injected OOMs, as does
    // the add() within createBlock().
    AutoEnterOOMUnsafeRegion oomUnsafe;
    Data::AddPtr p = data.lookupForAdd(blockId);
    if (p) {
      return *p->value();
    }
    return createBlock(p, blockId, oomUnsafe);
  }

  MOZ_ALWAYS_INLINE BitBlock* getOrCreateBlockFallible(size_t blockId) {
    Data::AddPtr p = data.lookupForAdd(blockId);
    if (p) {
      return p->value();
    }
    return createBlock(p, blockId);
  }

 public:
  ~SparseBitmap();

  size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf);

  MOZ_ALWAYS_INLINE void setBit(size_t bit) {
    size_t word = bit / JS_BITS_PER_WORD;
    size_t blockWord = blockStartWord(word);
    BitBlock& block = getOrCreateBlock(blockWord / WordsInBlock);
    block[word - blockWord] |= uintptr_t(1) << (bit % JS_BITS_PER_WORD);
  }

  MOZ_ALWAYS_INLINE bool setBitFallible(size_t bit) {
    size_t word = bit / JS_BITS_PER_WORD;
    size_t blockWord = blockStartWord(word);
    BitBlock* block = getOrCreateBlockFallible(blockWord / WordsInBlock);
    if (!block) {
      return false;
    }
    (*block)[word - blockWord] |= uintptr_t(1) << (bit % JS_BITS_PER_WORD);
    return true;
  }

  bool getBit(size_t bit) const;

  void bitwiseAndWith(const DenseBitmap& other);
  void bitwiseOrWith(const SparseBitmap& other);
  void bitwiseOrInto(DenseBitmap& other) const;

  // Currently, this API only supports a range of words that is in a single bit
  // block.
  template <typename T>
  typename std::enable_if_t<std::is_convertible_v<T, uintptr_t>, void>
  bitwiseOrRangeInto(size_t wordStart, size_t numWords, T* target) const {
    size_t blockWord = blockStartWord(wordStart);

    // We only support using a single bit block in this API.
    MOZ_ASSERT(numWords &&
               (blockWord == blockStartWord(wordStart + numWords - 1)));

    BitBlock* block = getBlock(blockWord / WordsInBlock);
    if (block) {
      for (size_t i = 0; i < numWords; i++) {
        target[i] |= (*block)[wordStart - blockWord + i];
      }
    }
  }
};

}  // namespace js

#endif  // ds_Bitmap_h