Branch data Line data Source code
1 : : /**
2 : : * \file This holds all stufff related our memory managent.
3 : : * I try the best as far as I can to reduce memory fragmentation
4 : : * and unneccessary calls to alloc and free.
5 : : *
6 : : * To achive this I try an approach described here as "Quick Fit".
7 : : * http://www.flounder.com/memory_allocation.htm
8 : : *
9 : : * The basic idea is to keep allocated memory segments and don't free
10 : : * them again. Instead I will put them in a tree indexed by their size.
11 : : * To get new memory I first have a look in the tree if there is
12 : : * a fitting memory segment. Fitting mean, larger or exactly the size
13 : : * I need. If there is one, use it. If not create a new one using
14 : : * usual malloc approach.
15 : : * I won't split the reagions at all because most likely they will be
16 : : * free soon again. This way I might waste some memory, so I have to
17 : : * keep an eye on this.
18 : : *
19 : : * Right now I don't build an upper limit for allocation. The limit
20 : : * still is the system memory itself.
21 : : *
22 : : * This is not implemented as a class because it will be used in the
23 : : * process of object creation.
24 : : *
25 : : * The data structure is a balanced tree with size as key.
26 : : * Under the size key is a list of elements of the same size.
27 : : *
28 : : * \author Georg Hopp
29 : : *
30 : : * \copyright
31 : : * Copyright © 2014 Georg Hopp
32 : : *
33 : : * This program is free software: you can redistribute it and/or modify
34 : : * it under the terms of the GNU General Public License as published by
35 : : * the Free Software Foundation, either version 3 of the License, or
36 : : * (at your option) any later version.
37 : : *
38 : : * This program is distributed in the hope that it will be useful,
39 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
40 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
41 : : * GNU General Public License for more details.
42 : : *
43 : : * You should have received a copy of the GNU General Public License
44 : : * along with this program. If not, see <http://www.gnu.org/licenses/>.
45 : : */
46 : :
47 : : #define _GNU_SOURCE
48 : :
49 : : #include <stdio.h>
50 : :
51 : : #include <stdlib.h>
52 : : #include <string.h>
53 : : #include <search.h>
54 : : #include <unistd.h>
55 : : #include <stdint.h>
56 : :
57 : : #include "tr/memory.h"
58 : :
59 : : #ifdef _WIN32
60 : : #define _SC_PAGESIZE 2048L
61 : :
62 : : long
63 : : sysconf(int name)
64 : : {
65 : : switch (name) {
66 : : case _SC_PAGESIZE: return 2048L;
67 : : }
68 : :
69 : : return -1;
70 : : }
71 : : #endif
72 : :
73 : : extern inline int TR_bitwidth(size_t);
74 : : extern inline size_t TR_getSize(void *);
75 : : extern inline size_t TR_getUsableSize(void *);
76 : : extern inline int TR_getIdx(void *);
77 : :
78 : : static
79 : : struct memSegment *
80 : 2 : newElement(size_t size, int idx)
81 : : {
82 : 2 : struct memSegment * element = malloc(size);
83 : :
84 : 2 : element->ref_count = 1;
85 : 2 : element->size = size;
86 : 2 : element->idx = idx;
87 : 2 : element->ptr = (void*)element + sizeof(struct memSegment);
88 : :
89 : 2 : element->next = NULL;
90 : :
91 : 2 : return element;
92 : : }
93 : :
94 : : #ifdef MEM_OPT
95 : : /**
96 : : * insert element in tree
97 : : */
98 : : static
99 : : inline
100 : : struct memSegment *
101 : 5 : insertElement(struct memSegment ** stack, struct memSegment * element)
102 : : {
103 : 5 : element->next = *stack;
104 : 5 : *stack = element;
105 : :
106 : 5 : return element;
107 : : }
108 : :
109 : : static
110 : : inline
111 : : struct memSegment *
112 : 5 : deleteElement(struct memSegment ** stack)
113 : : {
114 : 5 : struct memSegment * del_node = *stack;
115 : :
116 : 5 : if (*stack) {
117 : 3 : *stack = (*stack)->next;
118 : : }
119 : :
120 : 5 : return del_node;
121 : : }
122 : :
123 : : #define TR_MAX_MEM_IDX 1024
124 : :
125 : : struct memSegment * segments[TR_MAX_MEM_IDX] = {};
126 : :
127 : : static
128 : : inline
129 : : void
130 : : segmentFree(struct memSegment * segment, int depth)
131 : : {
132 : : while (NULL != segment) {
133 : : struct memSegment * next = segment->next;
134 : : free(segment);
135 : : segment = next;
136 : : }
137 : : }
138 : : #endif
139 : :
140 : : void *
141 : 0 : TR_reference(void * mem)
142 : : {
143 : 0 : struct memSegment * seg = (mem - sizeof(struct memSegment));
144 : :
145 : 0 : seg->ref_count++;
146 : :
147 : 0 : return mem;
148 : : }
149 : :
150 : : /*
151 : : * This tries to reflect the memory management behaviour of the
152 : : * GNU version of malloc. For other versions this might need
153 : : * to be changed to be optimal.
154 : : *
155 : : * However, GNU malloc keeps separate pools for each power of
156 : : * 2 memory size up to page size. So one page consists all of
157 : : * memory blocks of the same sizei (a power of 2).
158 : : *
159 : : * Also as far as I understand the smallest allocatable block is
160 : : * 8 bytes. At least the adresses are alwayse a multiple of 8.
161 : : *
162 : : * So lets say page size is 4096. There is nothing allocated
163 : : * right now. We allocate a block of 8 bytes. This will request
164 : : * a memory page from the OS. Then define it as a page containing
165 : : * 8 byte blocks and return the address of the first one of these.
166 : : * Any subsequent call to malloc for 8 bytes will return one of the
167 : : * blocks within this page as long as there are some left.
168 : : *
169 : : * So what we do here is up to page size round the request size up
170 : : * to the next power of 2 >= 8.
171 : : * Sizes greater then pagesize will be round up to the next
172 : : * multiple of pagesize. As far as I understand these are not
173 : : * pooled anyway.
174 : : *
175 : : * For now this assumes we are on a little endian machine.
176 : : */
177 : : void *
178 : 5 : TR_malloc(size_t size)
179 : : {
180 : 5 : struct memSegment * seg = NULL;
181 : 5 : long psize = sysconf(_SC_PAGESIZE);
182 : : static int psize_width = 0;
183 : : int idx;
184 : :
185 : 5 : psize_width = psize_width ? psize_width : TR_bitwidth(psize);
186 : :
187 : 5 : size += sizeof(struct memSegment);
188 : :
189 : : #define MIN_BITS 8
190 : :
191 : 5 : if (size >= psize) {
192 : : // get a multiple of pagesize
193 : 0 : idx = size / psize;
194 : :
195 : 0 : if (0 != (size % psize)) {
196 : : // size if not a multiple of pagesize so bring it to one.
197 : 0 : idx++;
198 : 0 : size = idx * psize;
199 : : }
200 : :
201 : 0 : idx += psize_width - MIN_BITS;
202 : : } else {
203 : 5 : if (size <= 1 << (MIN_BITS - 1)) {
204 : 5 : size = 1 << (MIN_BITS - 1);
205 : 5 : idx = 0;
206 : : } else {
207 : : // size-1 to ensure that powers of two will not be
208 : : // changed to the next power of two
209 : 0 : idx = TR_bitwidth(size-1) + 1;
210 : 0 : size = 1 << idx;
211 : 0 : idx -= (MIN_BITS - 1);
212 : : }
213 : : }
214 : :
215 : : #undef MIN_BITS
216 : :
217 : : #ifdef MEM_OPT
218 : 5 : if (idx < TR_MAX_MEM_IDX) {
219 : 5 : seg = deleteElement(&(segments[idx]));
220 : : } else
221 : : #endif
222 : : {
223 : 0 : idx = -1;
224 : : }
225 : :
226 : 5 : if (NULL == seg) {
227 : 2 : seg = newElement(size, idx);
228 : : }
229 : :
230 : 5 : return seg->ptr;
231 : : }
232 : :
233 : : /**
234 : : * this is a really memory wasting solution....just to be able to
235 : : * use calloc, which might be faster then malloc/memset solution.
236 : : *
237 : : * Maybe this is a bad idea, as we need to memset the buffer anyway
238 : : * if it comes from our tree, which hopefully should be the majority
239 : : * of cases.
240 : : */
241 : : void *
242 : 5 : TR_calloc(size_t nmemb, size_t size)
243 : : {
244 : 5 : size_t _size = nmemb * size;
245 : 5 : void * mem = TR_malloc(_size);
246 : :
247 : 5 : memset(mem, 0, TR_getUsableSize(mem));
248 : :
249 : 5 : return mem;
250 : : }
251 : :
252 : : void
253 : 5 : TR_free(void ** mem)
254 : : {
255 : 5 : if (NULL != *mem) {
256 : 5 : struct memSegment * seg = (*mem - sizeof(struct memSegment));
257 : :
258 : 5 : if (1 < seg->ref_count) {
259 : 0 : seg->ref_count--;
260 : : } else {
261 : : #ifdef MEM_OPT
262 : 5 : if (-1 != seg->idx) {
263 : 5 : insertElement(&(segments[seg->idx]), seg);
264 : : } else
265 : : #endif
266 : : {
267 : 0 : free(seg);
268 : : }
269 : : }
270 : :
271 : 5 : *mem = NULL;
272 : : }
273 : 5 : }
274 : :
275 : : void
276 : 0 : TR_cleanup()
277 : : {
278 : : #ifdef MEM_OPT
279 : : int i;
280 : :
281 : 0 : for (i=0; i<TR_MAX_MEM_IDX; i++) {
282 : 0 : while(segments[i]) {
283 : 0 : struct memSegment * next = segments[i]->next;
284 : 0 : free(segments[i]);
285 : 0 : segments[i] = next;
286 : : }
287 : : }
288 : : #endif
289 : 0 : }
290 : :
291 : : char *
292 : 0 : TR_strdup(const char * src)
293 : : {
294 : : char * dup;
295 : :
296 : 0 : if (NULL == src) {
297 : 0 : return NULL;
298 : : }
299 : :
300 : 0 : dup = TR_malloc(strlen(src)+1);
301 : 0 : strcpy(dup, src);
302 : :
303 : 0 : return dup;
304 : : }
305 : :
306 : : // vim: set ts=4 sw=4:
|
