pagemap.h 9.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324
  1. // -*- Mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*-
  2. // Copyright (c) 2005, Google Inc.
  3. // All rights reserved.
  4. //
  5. // Redistribution and use in source and binary forms, with or without
  6. // modification, are permitted provided that the following conditions are
  7. // met:
  8. //
  9. // * Redistributions of source code must retain the above copyright
  10. // notice, this list of conditions and the following disclaimer.
  11. // * Redistributions in binary form must reproduce the above
  12. // copyright notice, this list of conditions and the following disclaimer
  13. // in the documentation and/or other materials provided with the
  14. // distribution.
  15. // * Neither the name of Google Inc. nor the names of its
  16. // contributors may be used to endorse or promote products derived from
  17. // this software without specific prior written permission.
  18. //
  19. // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20. // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21. // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22. // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  23. // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24. // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25. // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26. // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27. // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28. // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  29. // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30. // ---
  31. // Author: Sanjay Ghemawat <opensource@google.com>
  32. //
  33. // A data structure used by the caching malloc. It maps from page# to
  34. // a pointer that contains info about that page. We use two
  35. // representations: one for 32-bit addresses, and another for 64 bit
  36. // addresses. Both representations provide the same interface. The
  37. // first representation is implemented as a flat array, the seconds as
  38. // a three-level radix tree that strips away approximately 1/3rd of
  39. // the bits every time.
  40. //
  41. // The BITS parameter should be the number of bits required to hold
  42. // a page number. E.g., with 32 bit pointers and 4K pages (i.e.,
  43. // page offset fits in lower 12 bits), BITS == 20.
  44. #ifndef TCMALLOC_PAGEMAP_H_
  45. #define TCMALLOC_PAGEMAP_H_
  46. #include "config.h"
  47. #include <stddef.h> // for NULL, size_t
  48. #include <string.h> // for memset
  49. #if defined HAVE_STDINT_H
  50. #include <stdint.h>
  51. #elif defined HAVE_INTTYPES_H
  52. #include <inttypes.h>
  53. #else
  54. #include <sys/types.h>
  55. #endif
  56. #include "internal_logging.h" // for ASSERT
  57. // Single-level array
  58. template <int BITS>
  59. class TCMalloc_PageMap1 {
  60. private:
  61. static const int LENGTH = 1 << BITS;
  62. void** array_;
  63. public:
  64. typedef uintptr_t Number;
  65. explicit TCMalloc_PageMap1(void* (*allocator)(size_t)) {
  66. array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS));
  67. memset(array_, 0, sizeof(void*) << BITS);
  68. }
  69. // Ensure that the map contains initialized entries "x .. x+n-1".
  70. // Returns true if successful, false if we could not allocate memory.
  71. bool Ensure(Number x, size_t n) {
  72. // Nothing to do since flat array was allocated at start. All
  73. // that's left is to check for overflow (that is, we don't want to
  74. // ensure a number y where array_[y] would be an out-of-bounds
  75. // access).
  76. return n <= LENGTH - x; // an overflow-free way to do "x + n <= LENGTH"
  77. }
  78. void PreallocateMoreMemory() {}
  79. // Return the current value for KEY. Returns NULL if not yet set,
  80. // or if k is out of range.
  81. void* get(Number k) const {
  82. if ((k >> BITS) > 0) {
  83. return NULL;
  84. }
  85. return array_[k];
  86. }
  87. // REQUIRES "k" is in range "[0,2^BITS-1]".
  88. // REQUIRES "k" has been ensured before.
  89. //
  90. // Sets the value 'v' for key 'k'.
  91. void set(Number k, void* v) {
  92. array_[k] = v;
  93. }
  94. // Return the first non-NULL pointer found in this map for
  95. // a page number >= k. Returns NULL if no such number is found.
  96. void* Next(Number k) const {
  97. while (k < (1 << BITS)) {
  98. if (array_[k] != NULL) return array_[k];
  99. k++;
  100. }
  101. return NULL;
  102. }
  103. };
  104. // Two-level radix tree
  105. template <int BITS>
  106. class TCMalloc_PageMap2 {
  107. private:
  108. // Put 32 entries in the root and (2^BITS)/32 entries in each leaf.
  109. static const int ROOT_BITS = 5;
  110. static const int ROOT_LENGTH = 1 << ROOT_BITS;
  111. static const int LEAF_BITS = BITS - ROOT_BITS;
  112. static const int LEAF_LENGTH = 1 << LEAF_BITS;
  113. // Leaf node
  114. struct Leaf {
  115. void* values[LEAF_LENGTH];
  116. };
  117. Leaf* root_[ROOT_LENGTH]; // Pointers to 32 child nodes
  118. void* (*allocator_)(size_t); // Memory allocator
  119. public:
  120. typedef uintptr_t Number;
  121. explicit TCMalloc_PageMap2(void* (*allocator)(size_t)) {
  122. allocator_ = allocator;
  123. memset(root_, 0, sizeof(root_));
  124. }
  125. void* get(Number k) const {
  126. const Number i1 = k >> LEAF_BITS;
  127. const Number i2 = k & (LEAF_LENGTH-1);
  128. if ((k >> BITS) > 0 || root_[i1] == NULL) {
  129. return NULL;
  130. }
  131. return root_[i1]->values[i2];
  132. }
  133. void set(Number k, void* v) {
  134. const Number i1 = k >> LEAF_BITS;
  135. const Number i2 = k & (LEAF_LENGTH-1);
  136. ASSERT(i1 < ROOT_LENGTH);
  137. root_[i1]->values[i2] = v;
  138. }
  139. bool Ensure(Number start, size_t n) {
  140. for (Number key = start; key <= start + n - 1; ) {
  141. const Number i1 = key >> LEAF_BITS;
  142. // Check for overflow
  143. if (i1 >= ROOT_LENGTH)
  144. return false;
  145. // Make 2nd level node if necessary
  146. if (root_[i1] == NULL) {
  147. Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));
  148. if (leaf == NULL) return false;
  149. memset(leaf, 0, sizeof(*leaf));
  150. root_[i1] = leaf;
  151. }
  152. // Advance key past whatever is covered by this leaf node
  153. key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
  154. }
  155. return true;
  156. }
  157. void PreallocateMoreMemory() {
  158. // Allocate enough to keep track of all possible pages
  159. Ensure(0, 1 << BITS);
  160. }
  161. void* Next(Number k) const {
  162. while (k < (1 << BITS)) {
  163. const Number i1 = k >> LEAF_BITS;
  164. Leaf* leaf = root_[i1];
  165. if (leaf != NULL) {
  166. // Scan forward in leaf
  167. for (Number i2 = k & (LEAF_LENGTH - 1); i2 < LEAF_LENGTH; i2++) {
  168. if (leaf->values[i2] != NULL) {
  169. return leaf->values[i2];
  170. }
  171. }
  172. }
  173. // Skip to next top-level entry
  174. k = (i1 + 1) << LEAF_BITS;
  175. }
  176. return NULL;
  177. }
  178. };
  179. // Three-level radix tree
  180. template <int BITS>
  181. class TCMalloc_PageMap3 {
  182. private:
  183. // How many bits should we consume at each interior level
  184. static const int INTERIOR_BITS = (BITS + 2) / 3; // Round-up
  185. static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS;
  186. // How many bits should we consume at leaf level
  187. static const int LEAF_BITS = BITS - 2*INTERIOR_BITS;
  188. static const int LEAF_LENGTH = 1 << LEAF_BITS;
  189. // Interior node
  190. struct Node {
  191. Node* ptrs[INTERIOR_LENGTH];
  192. };
  193. // Leaf node
  194. struct Leaf {
  195. void* values[LEAF_LENGTH];
  196. };
  197. Node* root_; // Root of radix tree
  198. void* (*allocator_)(size_t); // Memory allocator
  199. Node* NewNode() {
  200. Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node)));
  201. if (result != NULL) {
  202. memset(result, 0, sizeof(*result));
  203. }
  204. return result;
  205. }
  206. public:
  207. typedef uintptr_t Number;
  208. explicit TCMalloc_PageMap3(void* (*allocator)(size_t)) {
  209. allocator_ = allocator;
  210. root_ = NewNode();
  211. }
  212. void* get(Number k) const {
  213. const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
  214. const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);
  215. const Number i3 = k & (LEAF_LENGTH-1);
  216. if ((k >> BITS) > 0 ||
  217. root_->ptrs[i1] == NULL || root_->ptrs[i1]->ptrs[i2] == NULL) {
  218. return NULL;
  219. }
  220. return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];
  221. }
  222. void set(Number k, void* v) {
  223. ASSERT(k >> BITS == 0);
  224. const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
  225. const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);
  226. const Number i3 = k & (LEAF_LENGTH-1);
  227. reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v;
  228. }
  229. bool Ensure(Number start, size_t n) {
  230. for (Number key = start; key <= start + n - 1; ) {
  231. const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);
  232. const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH-1);
  233. // Check for overflow
  234. if (i1 >= INTERIOR_LENGTH || i2 >= INTERIOR_LENGTH)
  235. return false;
  236. // Make 2nd level node if necessary
  237. if (root_->ptrs[i1] == NULL) {
  238. Node* n = NewNode();
  239. if (n == NULL) return false;
  240. root_->ptrs[i1] = n;
  241. }
  242. // Make leaf node if necessary
  243. if (root_->ptrs[i1]->ptrs[i2] == NULL) {
  244. Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));
  245. if (leaf == NULL) return false;
  246. memset(leaf, 0, sizeof(*leaf));
  247. root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);
  248. }
  249. // Advance key past whatever is covered by this leaf node
  250. key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
  251. }
  252. return true;
  253. }
  254. void PreallocateMoreMemory() {
  255. }
  256. void* Next(Number k) const {
  257. while (k < (Number(1) << BITS)) {
  258. const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
  259. const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);
  260. if (root_->ptrs[i1] == NULL) {
  261. // Advance to next top-level entry
  262. k = (i1 + 1) << (LEAF_BITS + INTERIOR_BITS);
  263. } else {
  264. Leaf* leaf = reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2]);
  265. if (leaf != NULL) {
  266. for (Number i3 = (k & (LEAF_LENGTH-1)); i3 < LEAF_LENGTH; i3++) {
  267. if (leaf->values[i3] != NULL) {
  268. return leaf->values[i3];
  269. }
  270. }
  271. }
  272. // Advance to next interior entry
  273. k = ((k >> LEAF_BITS) + 1) << LEAF_BITS;
  274. }
  275. }
  276. return NULL;
  277. }
  278. };
  279. #endif // TCMALLOC_PAGEMAP_H_