gwnavruntime/kernel/HeapMH/HeapMH_Root.h Source File

HeapMH_Root.h
Go to the documentation of this file.
1 /*
2 * Copyright 2015 Autodesk, Inc. All rights reserved.
3 * Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
4 * or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
5 */
6 
7 /**************************************************************************
8 
9 Filename : HeapMH_Root.h
10 Content : Heap root used for bootstrapping and bookkeeping.
11  :
12 Created : 2009
13 Authors : Maxim Shemanarev
14 
15 **************************************************************************/
16 
17 #ifndef INC_KY_Kernel_HeapMH_Root_H
18 #define INC_KY_Kernel_HeapMH_Root_H
19 
24 
25 namespace Kaim { namespace HeapMH {
26 
27 //------------------------------------------------------------------------
28 struct PageMH : public ListNode<PageMH>
29 {
30  enum
31  {
32  PageSize = 4096,
33  PageMask = PageSize-1,
34  UnitShift = 4,
35  UnitSize = 1 << UnitShift,
36  UnitMask = UnitSize - 1,
37  BitSetBytes = PageSize/UnitSize/4,
38  MaxBytes = 512
39  };
40 
41  MemoryHeapMH *pHeap; // Heap this page belongs to.
42  UByte* Start;
43 };
44 
45 
46 //------------------------------------------------------------------------
47 struct PageTableMH
48 {
49  enum
50  {
51  Index1Shift = 7,
52  TableSize = 1 << Index1Shift,
53  Index0Mask = TableSize - 1
54  };
55 
56  struct Level0Entry
57  {
58  PageMH* FirstPage;
59  UPInt SizeMask;
60  };
61 
62  Level0Entry Entries[TableSize];
63 };
64 
65 struct DebugDataMH;
66 
67 //------------------------------------------------------------------------
68 struct MagicHeader
69 {
70  enum { MagicValue = 0x5FC0 }; // "SFCO" - Scaleform Corporation
71 
72  UInt16 Magic; // Magic marker
73  UInt16 UseCount; // Existing allocation count
74  UInt32 Index; // 2-component index in page tables
75  DebugDataMH* DebugHeader;
76 #ifndef KY_64BIT_POINTERS
77  UInt32 Filler;
78 #endif
79 
80  UInt32 GetIndex0() const { return Index & PageTableMH::Index0Mask; }
81  UInt32 GetIndex1() const { return Index >> PageTableMH::Index1Shift; }
82 };
83 
84 //------------------------------------------------------------------------
85 struct NodeMH
86 {
87  enum { Align4 = 0, Align8 = 1, Align16 = 2, MoreInfo = 3 };
88 
89  NodeMH* Parent;
90  NodeMH* Child[2];
91  UPInt pHeap;
92 #ifdef KY_MEMORY_ENABLE_DEBUG_INFO
93  DebugDataMH* DebugHeader;
94 #endif
95  //------------------ Optional data
96  UPInt Align;
97 
98  static UPInt GetNodeSize(UPInt align)
99  {
100  UPInt size = 4*sizeof(void*);
101 #ifdef KY_MEMORY_ENABLE_DEBUG_INFO
102  size += sizeof(void*);
103 #endif
104  return (align <= 16) ? size : size + sizeof(UPInt);
105  }
106 
107  MemoryHeapMH* GetHeap() const
108  {
109  return (MemoryHeapMH*)(pHeap & ~UPInt(3));
110  }
111 
112  UPInt GetAlign() const
113  {
114  return ((pHeap & 3) < 3) ? (UPInt(1) << ((pHeap & 3) + 2)) : Align;
115  }
116 
117  void SetHeap(MemoryHeapMH* heap, UPInt align)
118  {
119  switch(align)
120  {
121  case 1: case 2: case 4:
122  pHeap = UPInt(heap);
123  break;
124 
125  case 8:
126  pHeap = UPInt(heap) | Align8;
127  break;
128 
129  case 16:
130  pHeap = UPInt(heap) | Align16;
131  break;
132 
133  default:
134  pHeap = UPInt(heap) | MoreInfo;
135  Align = align;
136  break;
137  }
138  }
139 };
140 
141 
142 //--------------------------------------------------------------------
143 struct TreeNodeAccessor
144 {
145  static UPInt GetKey (const NodeMH* n) { return UPInt(n); }
146  static NodeMH* GetChild ( NodeMH* n, UPInt i) { return n->Child[i]; }
147  static const NodeMH* GetChild (const NodeMH* n, UPInt i) { return n->Child[i]; }
148  static NodeMH** GetChildPtr( NodeMH* n, UPInt i) { return &n->Child[i]; }
149 
150  static NodeMH* GetParent ( NodeMH* n) { return n->Parent; }
151  static const NodeMH* GetParent (const NodeMH* n) { return n->Parent; }
152 
153  static void SetParent (NodeMH* n, NodeMH* p) { n->Parent = p; }
154  static void SetChild (NodeMH* n, UPInt i, NodeMH* c) { n->Child[i] = c; }
155  static void ClearLinks(NodeMH* n) { n->Parent = n->Child[0] = n->Child[1] = 0; }
156 };
157 
158 
159 //------------------------------------------------------------------------
160 struct MagicHeadersInfo
161 {
162  MagicHeader* Header1; // Header on the left ptr or 0
163  MagicHeader* Header2; // Header on the right ptr or 0
164  UInt32* BitSet; // Pointer to the bitset
165  UByte* AlignedStart; // Pointer to the beginning of the page, aligned
166  UByte* AlignedEnd; // Pointer to the end of the page, aligned
167  UByte* Bound; // The bound between physical pages
168  PageMH* Page; // Page, null after GetMagicHeaders()
169 };
170 
171 
172 //------------------------------------------------------------------------
173 struct PageInfoMH
174 {
175 #ifdef KY_MEMORY_ENABLE_DEBUG_INFO
176  DebugDataMH** DebugHeaders[3];
177 #endif
178  PageMH* Page;
179  NodeMH* Node;
180  UPInt UsableSize;
181 };
182 
183 //------------------------------------------------------------------------
184 void GetMagicHeaders(UPInt pageStart, MagicHeadersInfo* headers);
185 
186 
187 //------------------------------------------------------------------------
188 class RootMH
189 {
190  typedef RadixTree<NodeMH, TreeNodeAccessor> HeapTreeType;
191 public:
192  RootMH(SysAlloc* sysAlloc);
193  ~RootMH();
194 
195  void FreeTables();
196 
197  SysAlloc* GetSysAlloc() { return pSysAlloc; }
198 
199  MemoryHeapMH* CreateHeap(const char* name,
200  MemoryHeapMH* parent,
201  const MemoryHeap::HeapDesc& desc);
202 
203  void DestroyHeap(MemoryHeapMH* heap);
204 
205  LockSafe* GetLock() { return &RootLock; }
206 
207  PageMH* AllocPage(MemoryHeapMH* heap);
208  void FreePage(PageMH* page);
209  UInt32 GetPageIndex(const PageMH* page) const;
210 
211  PageMH* ResolveAddress(UPInt addr) const;
212 
213  NodeMH* AddToGlobalTree(UByte* ptr, UPInt size, UPInt align, MemoryHeapMH* heap)
214  {
215  NodeMH* node = (NodeMH*)(ptr + size);
216  node->SetHeap(heap, align);
217 #ifdef KY_MEMORY_ENABLE_DEBUG_INFO
218  node->DebugHeader = 0;
219 #endif
220  HeapTree.Insert(node);
221  return node;
222  }
223 
224  NodeMH* FindNodeInGlobalTree(UByte* ptr)
225  {
226  return (NodeMH*)HeapTree.FindGrEq(UPInt(ptr));
227  }
228 
229  void RemoveFromGlobalTree(NodeMH* node)
230  {
231  HeapTree.Remove(node);
232  }
233 
234 #ifdef KY_MEMORY_ENABLE_DEBUG_INFO
235  void OnAlloc(const MemoryHeapMH* heap, UPInt size, UPInt align, unsigned sid, const void* ptr);
236  void OnRealloc(const MemoryHeapMH* heap, const void* oldPtr, UPInt newSize, const void* newPtr);
237  void OnFree(const MemoryHeapMH* heap, const void* ptr);
238 #endif
239 
240 
241 private:
242  bool allocPagePool();
243  static void setMagic(UByte* pageStart, unsigned magicValue);
244 
245  SysAlloc* pSysAlloc;
246  mutable LockSafe RootLock;
247  List<PageMH> FreePages;
248  unsigned TableCount;
249  HeapTreeType HeapTree;
250 
251  static MemoryHeap::HeapTracer* pTracer;
252 };
253 
254 extern RootMH* GlobalRootMH;
255 extern PageTableMH GlobalPageTableMH;
256 extern PageMH GlobalEmptyPage;
257 
258 }} // Kaim::HeapMH
259 
260 #endif
Definition: gamekitcrowddispersion.h:20