gwnavruntime/kernel/HeapPT/HeapPT_Granulator.h Source File

HeapPT_Granulator.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 : HeapPT_Granulator.h
10 Content : Allocation granulator
11 Created : 2009
12 Authors : Maxim Shemanarev
13 
14 Notes : The granulator requests the system allocator for
15  large memory blocks and granulates them as necessary,
16  providing smaller granularity to the consumer.
17 
18 **************************************************************************/
19 
20 #ifndef INC_KY_Kernel_HeapPT_Granulator_H
21 #define INC_KY_Kernel_HeapPT_Granulator_H
22 
23 #include "gwnavruntime/kernel/SF_SysAlloc.h"
24 #include "gwnavruntime/kernel/HeapPT/HeapPT_AllocLite.h"
25 
26 namespace Kaim { namespace HeapPT {
27 
28 // ***** Granulator
29 //
30 // The granulator requests the system allocator for large memory blocks
31 // and granulates them as necessary, providing smaller granularity to
32 // the consumer.
33 //
34 // Internally the granulator allocates a page of "headerPageSize" for
35 // the headers, and pages of "granularity" size (or bigger) for the payload.
36 // There can be many header pages linked in a circular list. When allocating
37 // it sometimes (very rarely) has to iterate through all header pages
38 // and all headers. Most of the time requests will be served successfully
39 // by using the last successful page and header.
40 //
41 // When freeing the granulator has to find the page that corresponds to
42 // the pointer. The granulator uses a binary search within every header
43 // page and iterates through all header pages in the linked list.
44 //
45 // Don't worry if it sounds scary in terms of the performance.
46 // The request are rare, and besides, there's no large variety of
47 // sizes.
48 //
49 // The only restriction is: HeaderPageSize and Granularity cannot be
50 // less than Heap_PageSize.
51 //------------------------------------------------------------------------
52 
53 
54 //------------------------------------------------------------------------
55 struct HdrPage : ListNode<HdrPage>
56 {
57  UPInt UseCount;
58  UPInt Filler[5]; // Just for better alignment to sizeof(TreeSeg)
59 // TreeSeg Segments[PageCapacity];
60 };
61 
62 
63 //------------------------------------------------------------------------
64 class Granulator
65 {
66  typedef TreeSeg Segment;
67 
68 public:
69  //--------------------------------------------------------------------
70  struct SegListAccessor
71  {
72  static void SetPrev(Segment* self, Segment* what) { self->AddrChild[0] = what; }
73  static void SetNext(Segment* self, Segment* what) { self->AddrChild[1] = what; }
74  static const Segment* GetPrev(const Segment* self) { return self->AddrChild[0]; }
75  static const Segment* GetNext(const Segment* self) { return self->AddrChild[1]; }
76  static Segment* GetPrev(Segment* self) { return self->AddrChild[0]; }
77  static Segment* GetNext(Segment* self) { return self->AddrChild[1]; }
78  };
79 
80  //--------------------------------------------------------------------
81  struct SegTreeAccessor
82  {
83  static UPInt GetKey (const Segment* n) { return UPInt(n->Buffer); }
84  static Segment* GetChild ( Segment* n, UPInt i) { return n->AddrChild[i]; }
85  static const Segment* GetChild (const Segment* n, UPInt i) { return n->AddrChild[i]; }
86  static Segment** GetChildPtr( Segment* n, UPInt i) { return &n->AddrChild[i]; }
87 
88  static Segment* GetParent ( Segment* n) { return n->AddrParent; }
89  static const Segment* GetParent (const Segment* n) { return n->AddrParent; }
90 
91  static void SetParent (Segment* n, Segment* p) { n->AddrParent = p; }
92  static void SetChild (Segment* n, UPInt i, Segment* c) { n->AddrChild[i] = c; }
93  static void ClearLinks(Segment* n) { n->AddrParent = n->AddrChild[0] = n->AddrChild[1] = 0; }
94  };
95 
96 
97  //--------------------------------------------------------------------
98  typedef List<HdrPage> HdrListType;
99  typedef List2<Segment, SegListAccessor> SegListType;
100  typedef RadixTree<Segment, SegTreeAccessor> SegTreeType;
101 
102 
103 public:
104  // Public interface functions
105  //--------------------------------------------------------------------
106  Granulator(SysAllocPaged* sysAlloc,
107  UPInt minSize = 256,
108  UPInt granularity = 64*1024,
109  UPInt hdrPageSize = Heap_PageSize);
110 
111  SysAllocPaged* GetSysAlloc() { return pSysAlloc; }
112 
113  UPInt GetGranularity() { return Granularity; }
114 
115  void* Alloc(UPInt size, UPInt alignSize);
116  bool ReallocInPlace(void* oldPtr, UPInt oldSize,
117  UPInt newSize, UPInt alignSize);
118 
119  bool Free(void* ptr, UPInt size, UPInt alignSize); // Size is required!
120 
121  UPInt GetFootprint() const { return Footprint; }
122  UPInt GetUsedSpace() const { return Footprint - Allocator.GetFreeBytes(); }
123 
124  UPInt GetBase() const { return pSysAlloc->GetBase(); } // DBG
125  UPInt GetSize() const { return pSysAlloc->GetSize(); } // DBG
126 
127  const TreeSeg* GetAllocSegment(const void* ptr) const;
128 
129  void VisitMem(MemVisitor* visitor,
130  MemVisitor::Category catSegm,
131  MemVisitor::Category catFree) const;
132 
133  void VisitSegments(SegVisitor* visitor, unsigned catSeg, unsigned catUnused) const;
134 
135  UPInt GetMinBase() const; // DBG
136 
137 private:
138  //--------------------------------------------------------------------
139  bool allocSegment(UPInt size, UPInt alignSize);
140  bool freeSegment(Segment* seg);
141  void* alloc(UPInt size, UPInt alignSize);
142  bool hasHeaders(const Segment* seg) const
143  {
144  return (UByte*)seg->Headers + HdrPageSize == seg->Buffer;
145  }
146  UByte* getSegBase(Segment* seg)
147  {
148  UPInt hdrSize = hasHeaders(seg) ? HdrPageSize : 0;
149  return seg->Buffer - hdrSize - seg->HeadBytes;
150  }
151  UPInt getSegSize(const Segment* seg) const
152  {
153  UPInt hdrSize = hasHeaders(seg) ? HdrPageSize : 0;
154  UPInt tailBytes = seg->HeadBytes ? Allocator.GetMinSize() - seg->HeadBytes : 0;
155  return seg->Size + hdrSize + seg->HeadBytes + tailBytes;
156  }
157  void visitSegments(const Segment* node, SegVisitor* visitor, unsigned cat) const;
158 
159  //--------------------------------------------------------------------
160  SysAllocPaged* pSysAlloc;
161  UPInt Granularity;
162  UPInt HdrPageSize;
163  UPInt HdrCapacity;
164  UPInt MinAlign;
165  UPInt MaxAlign;
166  bool HasRealloc;
167  HdrListType HdrList;
168  SegListType FreeSeg;
169  SegTreeType UsedSeg;
170  UPInt Footprint;
171  AllocLite Allocator;
172 };
173 
174 }} // Kaim::Heap
175 
176 #endif
SF_SysAlloc.h
HeapPT_AllocLite.h
Kaim
Definition: gamekitcrowddispersion.h:20
Please send us your comment about this page