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
35using namespace BPrivate;
36
37
38processHeap::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.
90void
91processHeap::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
128void
129processHeap::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
145void
146processHeap::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
162void
163processHeap::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