tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

Extent.h (2651B)

      1 /* This Source Code Form is subject to the terms of the Mozilla Public
      2 * License, v. 2.0. If a copy of the MPL was not distributed with this
      3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
      4 
      5 #ifndef EXTENT_H
      6 #define EXTENT_H
      7 
      8 #include "mozjemalloc_types.h"
      9 
     10 #include "BaseAlloc.h"
     11 #include "RedBlackTree.h"
     12 
     13 #include "mozilla/UniquePtr.h"
     14 
     15 // ***************************************************************************
     16 // Extent data structures.
     17 
     18 struct arena_t;
     19 
     20 enum ChunkType;
     21 
     22 // Tree of extents.
     23 struct extent_node_t {
     24  union {
     25    // Linkage for the size/address-ordered tree for chunk recycling.
     26    RedBlackTreeNode<extent_node_t> mLinkBySize;
     27    // Arena id for huge allocations. It's meant to match mArena->mId,
     28    // which only holds true when the arena hasn't been disposed of.
     29    arena_id_t mArenaId;
     30  };
     31 
     32  // Linkage for the address-ordered tree.
     33  RedBlackTreeNode<extent_node_t> mLinkByAddr;
     34 
     35  // Pointer to the extent that this tree node is responsible for.
     36  void* mAddr;
     37 
     38  // Total region size.
     39  size_t mSize;
     40 
     41  union {
     42    // What type of chunk is there; used for chunk recycling.
     43    ChunkType mChunkType;
     44 
     45    // A pointer to the associated arena, for huge allocations.
     46    arena_t* mArena;
     47  };
     48 };
     49 
     50 struct ExtentTreeSzTrait {
     51  static RedBlackTreeNode<extent_node_t>& GetTreeNode(extent_node_t* aThis) {
     52    return aThis->mLinkBySize;
     53  }
     54 
     55  static inline Order Compare(extent_node_t* aNode, extent_node_t* aOther) {
     56    Order ret = CompareInt(aNode->mSize, aOther->mSize);
     57    return (ret != Order::eEqual) ? ret
     58                                  : CompareAddr(aNode->mAddr, aOther->mAddr);
     59  }
     60 };
     61 
     62 struct ExtentTreeTrait {
     63  static RedBlackTreeNode<extent_node_t>& GetTreeNode(extent_node_t* aThis) {
     64    return aThis->mLinkByAddr;
     65  }
     66 
     67  static inline Order Compare(extent_node_t* aNode, extent_node_t* aOther) {
     68    return CompareAddr(aNode->mAddr, aOther->mAddr);
     69  }
     70 };
     71 
     72 struct ExtentTreeBoundsTrait : public ExtentTreeTrait {
     73  static inline Order Compare(extent_node_t* aKey, extent_node_t* aNode) {
     74    uintptr_t key_addr = reinterpret_cast<uintptr_t>(aKey->mAddr);
     75    uintptr_t node_addr = reinterpret_cast<uintptr_t>(aNode->mAddr);
     76    size_t node_size = aNode->mSize;
     77 
     78    // Is aKey within aNode?
     79    if (node_addr <= key_addr && key_addr < node_addr + node_size) {
     80      return Order::eEqual;
     81    }
     82 
     83    return CompareAddr(aKey->mAddr, aNode->mAddr);
     84  }
     85 };
     86 
     87 using ExtentAlloc = TypedBaseAlloc<extent_node_t>;
     88 
     89 template <>
     90 extent_node_t* ExtentAlloc::sFirstFree;
     91 
     92 using UniqueBaseNode =
     93    mozilla::UniquePtr<extent_node_t, BaseAllocFreePolicy<extent_node_t>>;
     94 
     95 #endif /* ! EXTENT_H */