1 ///-*-C++-*-//////////////////////////////////////////////////////////////////
2 //
3 // Hoard: A Fast, Scalable, and Memory-Efficient Allocator
4 // for Shared-Memory Multiprocessors
5 // Contact author: Emery Berger, http://www.cs.utexas.edu/users/emery
6 //
7 // Copyright (c) 1998-2000, The University of Texas at Austin.
8 //
9 // This library is free software; you can redistribute it and/or modify
10 // it under the terms of the GNU Library General Public License as
11 // published by the Free Software Foundation, http://www.fsf.org.
12 //
13 // This library is distributed in the hope that it will be useful, but
14 // WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 // Library General Public License for more details.
17 //
18 //////////////////////////////////////////////////////////////////////////////
19
20 #include <string.h>
21 #include <stdio.h>
22
23 #include "config.h"
24
25 #if USE_PRIVATE_HEAPS
26 # include "privateheap.h"
27 # define HEAPTYPE privateHeap
28 #else
29 # define HEAPTYPE threadHeap
30 # include "threadheap.h"
31 #endif
32
33 #include "processheap.h"
34
35 using namespace BPrivate;
36
37
processHeap()38 processHeap::processHeap()
39 :
40 theap((HEAPTYPE*)hoardSbrk(sizeof(HEAPTYPE) * fMaxThreadHeaps)),
41 #if HEAP_FRAG_STATS
42 _currentAllocated(0),
43 _currentRequested(0),
44 _maxAllocated(0),
45 _inUseAtMaxAllocated(0),
46 _maxRequested(0),
47 #endif
48 #if HEAP_LOG
49 _log((Log<MemoryRequest>*)
50 hoardSbrk(sizeof(Log<MemoryRequest>) * (fMaxThreadHeaps + 1))),
51 #endif
52 _buffer(NULL),
53 _bufferCount(0)
54 {
55 if (theap == NULL)
56 return;
57 new(theap) HEAPTYPE[fMaxThreadHeaps];
58
59 #if HEAP_LOG
60 if (_log == NULL)
61 return;
62 new(_log) Log<MemoryRequest>[fMaxThreadHeaps + 1];
63 #endif
64
65 int i;
66 // The process heap is heap 0.
67 setIndex(0);
68 for (i = 0; i < fMaxThreadHeaps; i++) {
69 // Set every thread's process heap to this one.
70 theap[i].setpHeap(this);
71 // Set every thread heap's index.
72 theap[i].setIndex(i + 1);
73 }
74 #if HEAP_LOG
75 for (i = 0; i < fMaxThreadHeaps + 1; i++) {
76 char fname[255];
77 sprintf(fname, "log%d", i);
78 unlink(fname);
79 _log[i].open(fname);
80 }
81 #endif
82 #if HEAP_FRAG_STATS
83 hoardLockInit(_statsLock, "hoard stats");
84 #endif
85 hoardLockInit(_bufferLock, "hoard buffer");
86 }
87
88
89 // Print out statistics information.
90 void
stats(void)91 processHeap::stats(void)
92 {
93 #if HEAP_STATS
94 int umax = 0;
95 int amax = 0;
96 for (int j = 0; j < fMaxThreadHeaps; j++) {
97 for (int i = 0; i < SIZE_CLASSES; i++) {
98 amax += theap[j].maxAllocated(i) * sizeFromClass(i);
99 umax += theap[j].maxInUse(i) * sizeFromClass(i);
100 }
101 }
102 printf("Amax <= %d, Umax <= %d\n", amax, umax);
103
104 #if HEAP_FRAG_STATS
105 amax = getMaxAllocated();
106 umax = getMaxRequested();
107 printf
108 ("Maximum allocated = %d\nMaximum in use = %d\nIn use at max allocated = %d\n",
109 amax, umax, getInUseAtMaxAllocated());
110 printf("Still in use = %d\n", _currentRequested);
111 printf("Fragmentation (3) = %f\n",
112 (float)amax / (float)getInUseAtMaxAllocated());
113 printf("Fragmentation (4) = %f\n", (float)amax / (float)umax);
114 #endif
115 #endif // HEAP_STATS
116
117 #if HEAP_LOG
118 printf("closing logs.\n");
119 fflush(stdout);
120 for (int i = 0; i < fMaxThreadHeaps + 1; i++) {
121 _log[i].close();
122 }
123 #endif
124 }
125
126
127 #if HEAP_FRAG_STATS
128 void
setAllocated(int requestedSize,int actualSize)129 processHeap::setAllocated(int requestedSize, int actualSize)
130 {
131 hoardLock(_statsLock);
132 _currentRequested += requestedSize;
133 _currentAllocated += actualSize;
134 if (_currentRequested > _maxRequested) {
135 _maxRequested = _currentRequested;
136 }
137 if (_currentAllocated > _maxAllocated) {
138 _maxAllocated = _currentAllocated;
139 _inUseAtMaxAllocated = _currentRequested;
140 }
141 hoardUnlock(_statsLock);
142 }
143
144
145 void
setDeallocated(int requestedSize,int actualSize)146 processHeap::setDeallocated(int requestedSize, int actualSize)
147 {
148 hoardLock(_statsLock);
149 _currentRequested -= requestedSize;
150 _currentAllocated -= actualSize;
151 hoardUnlock(_statsLock);
152 }
153 #endif // HEAP_FRAG_STATS
154
155
156 // free (ptr, pheap):
157 // inputs: a pointer to an object allocated by malloc().
158 // side effects: returns the block to the object's superblock;
159 // updates the thread heap's statistics;
160 // may release the superblock to the process heap.
161
162 void
free(void * ptr)163 processHeap::free(void *ptr)
164 {
165 // Return if ptr is 0.
166 // This is the behavior prescribed by the standard.
167 if (ptr == 0)
168 return;
169
170 // Find the block and superblock corresponding to this ptr.
171
172 block *b = (block *) ptr - 1;
173 assert(b->isValid());
174
175 // Check to see if this block came from a memalign() call.
176 if (((unsigned long)b->getNext() & 1) == 1) {
177 // It did. Set the block to the actual block header.
178 b = (block *) ((unsigned long)b->getNext() & ~1);
179 assert(b->isValid());
180 }
181
182 b->markFree();
183
184 superblock *sb = b->getSuperblock();
185 assert(sb);
186 assert(sb->isValid());
187
188 const int sizeclass = sb->getBlockSizeClass();
189
190 //
191 // Return the block to the superblock,
192 // find the heap that owns this superblock
193 // and update its statistics.
194 //
195
196 hoardHeap *owner;
197
198 // By acquiring the up lock on the superblock,
199 // we prevent it from moving to the global heap.
200 // This eventually pins it down in one heap,
201 // so this loop is guaranteed to terminate.
202 // (It should generally take no more than two iterations.)
203 sb->upLock();
204 while (1) {
205 owner = sb->getOwner();
206 owner->lock();
207 if (owner == sb->getOwner()) {
208 break;
209 } else {
210 owner->unlock();
211 }
212 // Suspend to allow ownership to quiesce.
213 hoardYield();
214 }
215
216 #if HEAP_LOG
217 MemoryRequest m;
218 m.free(ptr);
219 getLog(owner->getIndex()).append(m);
220 #endif
221 #if HEAP_FRAG_STATS
222 setDeallocated(b->getRequestedSize(), 0);
223 #endif
224
225 int sbUnmapped = owner->freeBlock(b, sb, sizeclass, this);
226
227 owner->unlock();
228 if (!sbUnmapped)
229 sb->upUnlock();
230 }
231