1/*
2 Copyright (c) 2000, 2010, Oracle and/or its affiliates
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
16
17/* Routines to handle mallocing of results which will be freed the same time */
18
19#include <my_global.h>
20#include <my_sys.h>
21#include <m_string.h>
22#undef EXTRA_DEBUG
23#define EXTRA_DEBUG
24
25/* data packed in MEM_ROOT -> min_malloc */
26
27#define MALLOC_FLAG(A) ((A & 1) ? MY_THREAD_SPECIFIC : 0)
28
29#define TRASH_MEM(X) TRASH_FREE(((char*)(X) + ((X)->size-(X)->left)), (X)->left)
30
31/*
32 Initialize memory root
33
34 SYNOPSIS
35 init_alloc_root()
36 mem_root - memory root to initialize
37 name - name of memroot (for debugging)
38 block_size - size of chunks (blocks) used for memory allocation
39 (It is external size of chunk i.e. it should include
40 memory required for internal structures, thus it
41 should be no less than ALLOC_ROOT_MIN_BLOCK_SIZE)
42 pre_alloc_size - if non-0, then size of block that should be
43 pre-allocated during memory root initialization.
44 my_flags MY_THREAD_SPECIFIC flag for my_malloc
45
46 DESCRIPTION
47 This function prepares memory root for further use, sets initial size of
48 chunk for memory allocation and pre-allocates first block if specified.
49 Although error can happen during execution of this function if
50 pre_alloc_size is non-0 it won't be reported. Instead it will be
51 reported as error in first alloc_root() on this memory root.
52
53 We don't want to change the structure size for MEM_ROOT.
54 Because of this, we store in MY_THREAD_SPECIFIC as bit 1 in block_size
55*/
56
57void init_alloc_root(MEM_ROOT *mem_root, const char *name, size_t block_size,
58 size_t pre_alloc_size __attribute__((unused)),
59 myf my_flags)
60{
61 DBUG_ENTER("init_alloc_root");
62 DBUG_PRINT("enter",("root: %p name: %s prealloc: %zu", mem_root,
63 name, pre_alloc_size));
64
65 mem_root->free= mem_root->used= mem_root->pre_alloc= 0;
66 mem_root->min_malloc= 32;
67 mem_root->block_size= (block_size - ALLOC_ROOT_MIN_BLOCK_SIZE) & ~1;
68 if (MY_TEST(my_flags & MY_THREAD_SPECIFIC))
69 mem_root->block_size|= 1;
70
71 mem_root->error_handler= 0;
72 mem_root->block_num= 4; /* We shift this with >>2 */
73 mem_root->first_block_usage= 0;
74 mem_root->total_alloc= 0;
75 mem_root->name= name;
76
77#if !(defined(HAVE_valgrind) && defined(EXTRA_DEBUG))
78 if (pre_alloc_size)
79 {
80 if ((mem_root->free= mem_root->pre_alloc=
81 (USED_MEM*) my_malloc(pre_alloc_size + ALIGN_SIZE(sizeof(USED_MEM)),
82 MYF(my_flags))))
83 {
84 mem_root->free->size= pre_alloc_size+ALIGN_SIZE(sizeof(USED_MEM));
85 mem_root->total_alloc= pre_alloc_size+ALIGN_SIZE(sizeof(USED_MEM));
86 mem_root->free->left= pre_alloc_size;
87 mem_root->free->next= 0;
88 TRASH_MEM(mem_root->free);
89 }
90 }
91#endif
92 DBUG_VOID_RETURN;
93}
94
95/*
96 SYNOPSIS
97 reset_root_defaults()
98 mem_root memory root to change defaults of
99 block_size new value of block size. Must be greater or equal
100 than ALLOC_ROOT_MIN_BLOCK_SIZE (this value is about
101 68 bytes and depends on platform and compilation flags)
102 pre_alloc_size new size of preallocated block. If not zero,
103 must be equal to or greater than block size,
104 otherwise means 'no prealloc'.
105 DESCRIPTION
106 Function aligns and assigns new value to block size; then it tries to
107 reuse one of existing blocks as prealloc block, or malloc new one of
108 requested size. If no blocks can be reused, all unused blocks are freed
109 before allocation.
110*/
111
112void reset_root_defaults(MEM_ROOT *mem_root, size_t block_size,
113 size_t pre_alloc_size __attribute__((unused)))
114{
115 DBUG_ENTER("reset_root_defaults");
116 DBUG_ASSERT(alloc_root_inited(mem_root));
117
118 mem_root->block_size= (((block_size - ALLOC_ROOT_MIN_BLOCK_SIZE) & ~1) |
119 (mem_root->block_size & 1));
120#if !(defined(HAVE_valgrind) && defined(EXTRA_DEBUG))
121 if (pre_alloc_size)
122 {
123 size_t size= pre_alloc_size + ALIGN_SIZE(sizeof(USED_MEM));
124 if (!mem_root->pre_alloc || mem_root->pre_alloc->size != size)
125 {
126 USED_MEM *mem, **prev= &mem_root->free;
127 /*
128 Free unused blocks, so that consequent calls
129 to reset_root_defaults won't eat away memory.
130 */
131 while (*prev)
132 {
133 mem= *prev;
134 if (mem->size == size)
135 {
136 /* We found a suitable block, no need to do anything else */
137 mem_root->pre_alloc= mem;
138 DBUG_VOID_RETURN;
139 }
140 if (mem->left + ALIGN_SIZE(sizeof(USED_MEM)) == mem->size)
141 {
142 /* remove block from the list and free it */
143 *prev= mem->next;
144 mem_root->total_alloc-= mem->size;
145 my_free(mem);
146 }
147 else
148 prev= &mem->next;
149 }
150 /* Allocate new prealloc block and add it to the end of free list */
151 if ((mem= (USED_MEM *) my_malloc(size,
152 MYF(MALLOC_FLAG(mem_root->
153 block_size)))))
154 {
155 mem->size= size;
156 mem_root->total_alloc+= size;
157 mem->left= pre_alloc_size;
158 mem->next= *prev;
159 *prev= mem_root->pre_alloc= mem;
160 TRASH_MEM(mem);
161 }
162 else
163 {
164 mem_root->pre_alloc= 0;
165 }
166 }
167 }
168 else
169#endif
170 mem_root->pre_alloc= 0;
171
172 DBUG_VOID_RETURN;
173}
174
175
176void *alloc_root(MEM_ROOT *mem_root, size_t length)
177{
178#if defined(HAVE_valgrind) && defined(EXTRA_DEBUG)
179 reg1 USED_MEM *next;
180 DBUG_ENTER("alloc_root");
181 DBUG_PRINT("enter",("root: %p name: %s", mem_root, mem_root->name));
182
183 DBUG_ASSERT(alloc_root_inited(mem_root));
184
185 DBUG_EXECUTE_IF("simulate_out_of_memory",
186 {
187 if (mem_root->error_handler)
188 (*mem_root->error_handler)();
189 DBUG_SET("-d,simulate_out_of_memory");
190 DBUG_RETURN((void*) 0); /* purecov: inspected */
191 });
192
193 length+=ALIGN_SIZE(sizeof(USED_MEM));
194 if (!(next = (USED_MEM*) my_malloc(length,
195 MYF(MY_WME | ME_FATALERROR |
196 MALLOC_FLAG(mem_root->block_size)))))
197 {
198 if (mem_root->error_handler)
199 (*mem_root->error_handler)();
200 DBUG_RETURN((uchar*) 0); /* purecov: inspected */
201 }
202 next->next= mem_root->used;
203 next->left= 0;
204 next->size= length;
205 mem_root->used= next;
206 mem_root->total_alloc+= length;
207 DBUG_PRINT("exit",("ptr: %p", (((char*) next)+
208 ALIGN_SIZE(sizeof(USED_MEM)))));
209 DBUG_RETURN((uchar*) (((char*) next)+ALIGN_SIZE(sizeof(USED_MEM))));
210#else
211 size_t get_size, block_size;
212 uchar* point;
213 reg1 USED_MEM *next= 0;
214 reg2 USED_MEM **prev;
215 DBUG_ENTER("alloc_root");
216 DBUG_PRINT("enter",("root: %p name: %s", mem_root, mem_root->name));
217 DBUG_ASSERT(alloc_root_inited(mem_root));
218
219 DBUG_EXECUTE_IF("simulate_out_of_memory",
220 {
221 /* Avoid reusing an already allocated block */
222 if (mem_root->error_handler)
223 (*mem_root->error_handler)();
224 DBUG_SET("-d,simulate_out_of_memory");
225 DBUG_RETURN((void*) 0); /* purecov: inspected */
226 });
227 length= ALIGN_SIZE(length);
228 if ((*(prev= &mem_root->free)) != NULL)
229 {
230 if ((*prev)->left < length &&
231 mem_root->first_block_usage++ >= ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP &&
232 (*prev)->left < ALLOC_MAX_BLOCK_TO_DROP)
233 {
234 next= *prev;
235 *prev= next->next; /* Remove block from list */
236 next->next= mem_root->used;
237 mem_root->used= next;
238 mem_root->first_block_usage= 0;
239 }
240 for (next= *prev ; next && next->left < length ; next= next->next)
241 prev= &next->next;
242 }
243 if (! next)
244 { /* Time to alloc new block */
245 block_size= (mem_root->block_size & ~1) * (mem_root->block_num >> 2);
246 get_size= length+ALIGN_SIZE(sizeof(USED_MEM));
247 get_size= MY_MAX(get_size, block_size);
248
249 if (!(next = (USED_MEM*) my_malloc(get_size,
250 MYF(MY_WME | ME_FATALERROR |
251 MALLOC_FLAG(mem_root->
252 block_size)))))
253 {
254 if (mem_root->error_handler)
255 (*mem_root->error_handler)();
256 DBUG_RETURN((void*) 0); /* purecov: inspected */
257 }
258 mem_root->block_num++;
259 mem_root->total_alloc+= get_size;
260 next->next= *prev;
261 next->size= get_size;
262 next->left= get_size-ALIGN_SIZE(sizeof(USED_MEM));
263 *prev=next;
264 TRASH_MEM(next);
265 }
266
267 point= (uchar*) ((char*) next+ (next->size-next->left));
268 /*TODO: next part may be unneded due to mem_root->first_block_usage counter*/
269 if ((next->left-= length) < mem_root->min_malloc)
270 { /* Full block */
271 *prev= next->next; /* Remove block from list */
272 next->next= mem_root->used;
273 mem_root->used= next;
274 mem_root->first_block_usage= 0;
275 }
276 TRASH_ALLOC(point, length);
277 DBUG_PRINT("exit",("ptr: %p", point));
278 DBUG_RETURN((void*) point);
279#endif
280}
281
282
283/*
284 Allocate many pointers at the same time.
285
286 DESCRIPTION
287 ptr1, ptr2, etc all point into big allocated memory area.
288
289 SYNOPSIS
290 multi_alloc_root()
291 root Memory root
292 ptr1, length1 Multiple arguments terminated by a NULL pointer
293 ptr2, length2 ...
294 ...
295 NULL
296
297 RETURN VALUE
298 A pointer to the beginning of the allocated memory block
299 in case of success or NULL if out of memory.
300*/
301
302void *multi_alloc_root(MEM_ROOT *root, ...)
303{
304 va_list args;
305 char **ptr, *start, *res;
306 size_t tot_length, length;
307 DBUG_ENTER("multi_alloc_root");
308 /*
309 We don't need to do DBUG_PRINT here as it will be done when alloc_root
310 is called
311 */
312
313 va_start(args, root);
314 tot_length= 0;
315 while ((ptr= va_arg(args, char **)))
316 {
317 length= va_arg(args, uint);
318 tot_length+= ALIGN_SIZE(length);
319 }
320 va_end(args);
321
322 if (!(start= (char*) alloc_root(root, tot_length)))
323 DBUG_RETURN(0); /* purecov: inspected */
324
325 va_start(args, root);
326 res= start;
327 while ((ptr= va_arg(args, char **)))
328 {
329 *ptr= res;
330 length= va_arg(args, uint);
331 res+= ALIGN_SIZE(length);
332 }
333 va_end(args);
334 DBUG_RETURN((void*) start);
335}
336
337
338#if !(defined(HAVE_valgrind) && defined(EXTRA_DEBUG))
339/** Mark all data in blocks free for reusage */
340
341static inline void mark_blocks_free(MEM_ROOT* root)
342{
343 reg1 USED_MEM *next;
344 reg2 USED_MEM **last;
345
346 /* iterate through (partially) free blocks, mark them free */
347 last= &root->free;
348 for (next= root->free; next; next= *(last= &next->next))
349 {
350 next->left= next->size - ALIGN_SIZE(sizeof(USED_MEM));
351 TRASH_MEM(next);
352 }
353
354 /* Combine the free and the used list */
355 *last= next=root->used;
356
357 /* now go through the used blocks and mark them free */
358 for (; next; next= next->next)
359 {
360 next->left= next->size - ALIGN_SIZE(sizeof(USED_MEM));
361 TRASH_MEM(next);
362 }
363
364 /* Now everything is set; Indicate that nothing is used anymore */
365 root->used= 0;
366 root->first_block_usage= 0;
367 root->block_num= 4;
368}
369#endif
370
371
372/*
373 Deallocate everything used by alloc_root or just move
374 used blocks to free list if called with MY_USED_TO_FREE
375
376 SYNOPSIS
377 free_root()
378 root Memory root
379 MyFlags Flags for what should be freed:
380
381 MY_MARK_BLOCKS_FREED Don't free blocks, just mark them free
382 MY_KEEP_PREALLOC If this is not set, then free also the
383 preallocated block
384
385 NOTES
386 One can call this function either with root block initialised with
387 init_alloc_root() or with a bzero()-ed block.
388 It's also safe to call this multiple times with the same mem_root.
389*/
390
391void free_root(MEM_ROOT *root, myf MyFlags)
392{
393 reg1 USED_MEM *next,*old;
394 DBUG_ENTER("free_root");
395 DBUG_PRINT("enter",("root: %p name: %s flags: %u", root, root->name,
396 (uint) MyFlags));
397
398#if !(defined(HAVE_valgrind) && defined(EXTRA_DEBUG))
399 /*
400 There is no point in using mark_blocks_free when using valgrind as
401 it will not reclaim any memory
402 */
403 if (MyFlags & MY_MARK_BLOCKS_FREE)
404 {
405 mark_blocks_free(root);
406 DBUG_VOID_RETURN;
407 }
408#endif
409 if (!(MyFlags & MY_KEEP_PREALLOC))
410 root->pre_alloc=0;
411
412 for (next=root->used; next ;)
413 {
414 old=next; next= next->next ;
415 if (old != root->pre_alloc)
416 {
417 root->total_alloc-= old->size;
418 my_free(old);
419 }
420 }
421 for (next=root->free ; next ;)
422 {
423 old=next; next= next->next;
424 if (old != root->pre_alloc)
425 {
426 root->total_alloc-= old->size;
427 my_free(old);
428 }
429 }
430 root->used=root->free=0;
431 if (root->pre_alloc)
432 {
433 root->free=root->pre_alloc;
434 root->free->left=root->pre_alloc->size-ALIGN_SIZE(sizeof(USED_MEM));
435 TRASH_MEM(root->pre_alloc);
436 root->free->next=0;
437 }
438 root->block_num= 4;
439 root->first_block_usage= 0;
440 DBUG_VOID_RETURN;
441}
442
443/*
444 Find block that contains an object and set the pre_alloc to it
445*/
446
447void set_prealloc_root(MEM_ROOT *root, char *ptr)
448{
449 USED_MEM *next;
450 for (next=root->used; next ; next=next->next)
451 {
452 if ((char*) next <= ptr && (char*) next + next->size > ptr)
453 {
454 root->pre_alloc=next;
455 return;
456 }
457 }
458 for (next=root->free ; next ; next=next->next)
459 {
460 if ((char*) next <= ptr && (char*) next + next->size > ptr)
461 {
462 root->pre_alloc=next;
463 return;
464 }
465 }
466}
467
468
469char *strdup_root(MEM_ROOT *root, const char *str)
470{
471 return strmake_root(root, str, strlen(str));
472}
473
474
475char *strmake_root(MEM_ROOT *root, const char *str, size_t len)
476{
477 char *pos;
478 if ((pos=alloc_root(root,len+1)))
479 {
480 memcpy(pos,str,len);
481 pos[len]=0;
482 }
483 return pos;
484}
485
486
487void *memdup_root(MEM_ROOT *root, const void *str, size_t len)
488{
489 char *pos;
490 if ((pos=alloc_root(root,len)))
491 memcpy(pos,str,len);
492 return pos;
493}
494