libgo/runtime/mheapmap64.h

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // Free(v) must be able to determine the MSpan containing v.
   6 // The MHeapMap is a 3-level radix tree mapping page numbers to MSpans.
   7 //
   8 // NOTE(rsc): On a 32-bit platform (= 20-bit page numbers),
   9 // we can swap in a 2-level radix tree.
  10 //
  11 // NOTE(rsc): We use a 3-level tree because tcmalloc does, but
  12 // having only three levels requires approximately 1 MB per node
  13 // in the tree, making the minimum map footprint 3 MB.
  14 // Using a 4-level tree would cut the minimum footprint to 256 kB.
  15 // On the other hand, it's just virtual address space: most of
  16 // the memory is never going to be touched, thus never paged in.
  17
  18 typedef struct MHeapMapNode2 MHeapMapNode2;
  19 typedef struct MHeapMapNode3 MHeapMapNode3;
  20
  21 enum
  22 {
  23         // 64 bit address - 12 bit page size = 52 bits to map
  24         MHeapMap_Level1Bits = 18,
  25         MHeapMap_Level2Bits = 18,
  26         MHeapMap_Level3Bits = 16,
  27
  28         MHeapMap_TotalBits =
  29                 MHeapMap_Level1Bits +
  30                 MHeapMap_Level2Bits +
  31                 MHeapMap_Level3Bits,
  32
  33         MHeapMap_Level1Mask = (1<<MHeapMap_Level1Bits) - 1,
  34         MHeapMap_Level2Mask = (1<<MHeapMap_Level2Bits) - 1,
  35         MHeapMap_Level3Mask = (1<<MHeapMap_Level3Bits) - 1,
  36 };
  37
  38 struct MHeapMap
  39 {
  40         void *(*allocator)(uintptr);
  41         MHeapMapNode2 *p[1<<MHeapMap_Level1Bits];
  42 };
  43
  44 struct MHeapMapNode2
  45 {
  46         MHeapMapNode3 *p[1<<MHeapMap_Level2Bits];
  47 };
  48
  49 struct MHeapMapNode3
  50 {
  51         MSpan *s[1<<MHeapMap_Level3Bits];
  52 };
  53
  54 void    runtime_MHeapMap_Init(MHeapMap *m, void *(*allocator)(uintptr));
  55 bool    runtime_MHeapMap_Preallocate(MHeapMap *m, PageID k, uintptr npages);
  56 MSpan*  runtime_MHeapMap_Get(MHeapMap *m, PageID k);
  57 MSpan*  runtime_MHeapMap_GetMaybe(MHeapMap *m, PageID k);
  58 void    runtime_MHeapMap_Set(MHeapMap *m, PageID k, MSpan *v);
  59
  60