1 /*
2 ===========================================================================
3 Copyright (C) 1999-2005 Id Software, Inc.
4 Copyright (C) 2000-2006 Tim Angus
5
6 This file is part of Tremulous.
7
8 Tremulous is free software; you can redistribute it
9 and/or modify it under the terms of the GNU General Public License as
10 published by the Free Software Foundation; either version 2 of the License,
11 or (at your option) any later version.
12
13 Tremulous is distributed in the hope that it will be
14 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with Tremulous; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 ===========================================================================
22 */
23
24 #include "cg_local.h"
25
26 #define POOLSIZE (256 * 1024)
27 #define FREEMEMCOOKIE ((int)0xDEADBE3F) // Any unlikely to be used value
28 #define ROUNDBITS 31 // Round to 32 bytes
29
30 struct freememnode
31 {
32 // Size of ROUNDBITS
33 int cookie, size; // Size includes node (obviously)
34 struct freememnode *prev, *next;
35 };
36
37 static char memoryPool[ POOLSIZE ];
38 static struct freememnode *freehead;
39 static int freemem;
40
CG_Alloc(int size)41 void *CG_Alloc( int size )
42 {
43 // Find a free block and allocate.
44 // Does two passes, attempts to fill same-sized free slot first.
45
46 struct freememnode *fmn, *prev, *next, *smallest;
47 int allocsize, smallestsize;
48 char *endptr;
49 int *ptr;
50
51 allocsize = ( size + sizeof(int) + ROUNDBITS ) & ~ROUNDBITS; // Round to 32-byte boundary
52 ptr = NULL;
53
54 smallest = NULL;
55 smallestsize = POOLSIZE + 1; // Guaranteed not to miss any slots :)
56 for( fmn = freehead; fmn; fmn = fmn->next )
57 {
58 if( fmn->cookie != FREEMEMCOOKIE )
59 CG_Error( "CG_Alloc: Memory corruption detected!\n" );
60
61 if( fmn->size >= allocsize )
62 {
63 // We've got a block
64 if( fmn->size == allocsize )
65 {
66 // Same size, just remove
67
68 prev = fmn->prev;
69 next = fmn->next;
70 if( prev )
71 prev->next = next; // Point previous node to next
72 if( next )
73 next->prev = prev; // Point next node to previous
74 if( fmn == freehead )
75 freehead = next; // Set head pointer to next
76 ptr = (int *) fmn;
77 break; // Stop the loop, this is fine
78 }
79 else
80 {
81 // Keep track of the smallest free slot
82 if( fmn->size < smallestsize )
83 {
84 smallest = fmn;
85 smallestsize = fmn->size;
86 }
87 }
88 }
89 }
90
91 if( !ptr && smallest )
92 {
93 // We found a slot big enough
94 smallest->size -= allocsize;
95 endptr = (char *) smallest + smallest->size;
96 ptr = (int *) endptr;
97 }
98
99 if( ptr )
100 {
101 freemem -= allocsize;
102 if( cg_debugAlloc.integer )
103 CG_Printf( "CG_Alloc of %i bytes (%i left)\n", allocsize, freemem );
104 memset( ptr, 0, allocsize );
105 *ptr++ = allocsize; // Store a copy of size for deallocation
106 return( (void *) ptr );
107 }
108
109 CG_Error( "CG_Alloc: failed on allocation of %i bytes\n", size );
110 return( NULL );
111 }
112
CG_Free(void * ptr)113 void CG_Free( void *ptr )
114 {
115 // Release allocated memory, add it to the free list.
116
117 struct freememnode *fmn;
118 char *freeend;
119 int *freeptr;
120
121 freeptr = ptr;
122 freeptr--;
123
124 freemem += *freeptr;
125 if( cg_debugAlloc.integer )
126 CG_Printf( "CG_Free of %i bytes (%i left)\n", *freeptr, freemem );
127
128 for( fmn = freehead; fmn; fmn = fmn->next )
129 {
130 freeend = ((char *) fmn) + fmn->size;
131 if( freeend == (char *) freeptr )
132 {
133 // Released block can be merged to an existing node
134
135 fmn->size += *freeptr; // Add size of node.
136 return;
137 }
138 }
139 // No merging, add to head of list
140
141 fmn = (struct freememnode *) freeptr;
142 fmn->size = *freeptr; // Set this first to avoid corrupting *freeptr
143 fmn->cookie = FREEMEMCOOKIE;
144 fmn->prev = NULL;
145 fmn->next = freehead;
146 freehead->prev = fmn;
147 freehead = fmn;
148 }
149
CG_InitMemory(void)150 void CG_InitMemory( void )
151 {
152 // Set up the initial node
153
154 freehead = (struct freememnode *) memoryPool;
155 freehead->cookie = FREEMEMCOOKIE;
156 freehead->size = POOLSIZE;
157 freehead->next = NULL;
158 freehead->prev = NULL;
159 freemem = sizeof(memoryPool);
160 }
161
CG_DefragmentMemory(void)162 void CG_DefragmentMemory( void )
163 {
164 // If there's a frenzy of deallocation and we want to
165 // allocate something big, this is useful. Otherwise...
166 // not much use.
167
168 struct freememnode *startfmn, *endfmn, *fmn;
169
170 for( startfmn = freehead; startfmn; )
171 {
172 endfmn = (struct freememnode *)(((char *) startfmn) + startfmn->size);
173 for( fmn = freehead; fmn; )
174 {
175 if( fmn->cookie != FREEMEMCOOKIE )
176 CG_Error( "CG_DefragmentMemory: Memory corruption detected!\n" );
177
178 if( fmn == endfmn )
179 {
180 // We can add fmn onto startfmn.
181
182 if( fmn->prev )
183 fmn->prev->next = fmn->next;
184 if( fmn->next )
185 {
186 if( !(fmn->next->prev = fmn->prev) )
187 freehead = fmn->next; // We're removing the head node
188 }
189 startfmn->size += fmn->size;
190 memset( fmn, 0, sizeof(struct freememnode) ); // A redundant call, really.
191
192 startfmn = freehead;
193 endfmn = fmn = NULL; // Break out of current loop
194 }
195 else
196 fmn = fmn->next;
197 }
198
199 if( endfmn )
200 startfmn = startfmn->next; // endfmn acts as a 'restart' flag here
201 }
202 }
203