← Back to branch summary

~ubuntu-branches/ubuntu/trusty/drizzle/trusty

« back to all changes in this revision

Viewing changes to drizzled/memory/root.cc

  • Committer: Bazaar Package Importer
  • Author(s): Monty Taylor
  • Date: 2010-03-18 12:12:31 UTC
  • Revision ID: james.westby@ubuntu.com-20100318121231-k6g1xe6cshbwa0f8
Tags: upstream-2010.03.1347
Import upstream version 2010.03.1347

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/memory/root.cc
 
1
/* Copyright (C) 2000 MySQL AB
 
2
 
 
3
   This program is free software; you can redistribute it and/or modify
 
4
   it under the terms of the GNU General Public License as published by
 
5
   the Free Software Foundation; version 2 of the License.
 
6
 
 
7
   This program is distributed in the hope that it will be useful,
 
8
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
   GNU General Public License for more details.
 
11
 
 
12
   You should have received a copy of the GNU General Public License
 
13
   along with this program; if not, write to the Free Software
 
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
15
 
 
16
/* Routines to handle mallocing of results which will be freed the same time */
 
17
 
 
18
#include "config.h"
 
19
 
 
20
#include "drizzled/internal/my_sys.h"
 
21
#include "drizzled/internal/m_string.h"
 
22
 
 
23
#include <algorithm>
 
24
 
 
25
using namespace std;
 
26
 
 
27
namespace drizzled
 
28
{
 
29
 
 
30
static const unsigned int MAX_BLOCK_TO_DROP= 4096;
 
31
static const unsigned int MAX_BLOCK_USAGE_BEFORE_DROP= 10;
 
32
 
 
33
/*
 
34
  Initialize memory root
 
35
 
 
36
  SYNOPSIS
 
37
    memory::init_alloc_root()
 
38
      mem_root       - memory root to initialize
 
39
      block_size     - size of chunks (blocks) used for memory allocation
 
40
                       (It is external size of chunk i.e. it should include
 
41
                        memory required for internal structures, thus it
 
42
                        should be no less than memory::ROOT_MIN_BLOCK_SIZE)
 
43
 
 
44
  DESCRIPTION
 
45
    This function prepares memory root for further use, sets initial size of
 
46
    chunk for memory allocation and pre-allocates first block if specified.
 
47
    Altough error can happen during execution of this function if
 
48
    pre_alloc_size is non-0 it won't be reported. Instead it will be
 
49
    reported as error in first alloc_root() on this memory root.
 
50
*/
 
51
 
 
52
void memory::init_alloc_root(memory::Root *mem_root, size_t block_size)
 
53
{
 
54
  mem_root->free= mem_root->used= mem_root->pre_alloc= 0;
 
55
  mem_root->min_malloc= 32;
 
56
  mem_root->block_size= block_size - memory::ROOT_MIN_BLOCK_SIZE;
 
57
  mem_root->error_handler= 0;
 
58
  mem_root->block_num= 4;                       /* We shift this with >>2 */
 
59
  mem_root->first_block_usage= 0;
 
60
 
 
61
  return;
 
62
}
 
63
 
 
64
 
 
65
/*
 
66
  SYNOPSIS
 
67
    reset_root_defaults()
 
68
    mem_root        memory root to change defaults of
 
69
    block_size      new value of block size. Must be greater or equal
 
70
                    than ALLOC_ROOT_MIN_BLOCK_SIZE (this value is about
 
71
                    68 bytes and depends on platform and compilation flags)
 
72
    pre_alloc_size  new size of preallocated block. If not zero,
 
73
                    must be equal to or greater than block size,
 
74
                    otherwise means 'no prealloc'.
 
75
  DESCRIPTION
 
76
    Function aligns and assigns new value to block size; then it tries to
 
77
    reuse one of existing blocks as prealloc block, or malloc new one of
 
78
    requested size. If no blocks can be reused, all unused blocks are freed
 
79
    before allocation.
 
80
*/
 
81
 
 
82
void memory::reset_root_defaults(memory::Root *mem_root, size_t block_size,
 
83
                                 size_t pre_alloc_size)
 
84
{
 
85
  assert(alloc_root_inited(mem_root));
 
86
 
 
87
  mem_root->block_size= block_size - memory::ROOT_MIN_BLOCK_SIZE;
 
88
  if (pre_alloc_size)
 
89
  {
 
90
    size_t size= pre_alloc_size + ALIGN_SIZE(sizeof(memory::internal::UsedMemory));
 
91
    if (!mem_root->pre_alloc || mem_root->pre_alloc->size != size)
 
92
    {
 
93
      memory::internal::UsedMemory *mem, **prev= &mem_root->free;
 
94
      /*
 
95
        Free unused blocks, so that consequent calls
 
96
        to reset_root_defaults won't eat away memory.
 
97
      */
 
98
      while (*prev)
 
99
      {
 
100
        mem= *prev;
 
101
        if (mem->size == size)
 
102
        {
 
103
          /* We found a suitable block, no need to do anything else */
 
104
          mem_root->pre_alloc= mem;
 
105
          return;
 
106
        }
 
107
        if (mem->left + ALIGN_SIZE(sizeof(memory::internal::UsedMemory)) == mem->size)
 
108
        {
 
109
          /* remove block from the list and free it */
 
110
          *prev= mem->next;
 
111
          free(mem);
 
112
        }
 
113
        else
 
114
          prev= &mem->next;
 
115
      }
 
116
      /* Allocate new prealloc block and add it to the end of free list */
 
117
      if ((mem= static_cast<memory::internal::UsedMemory *>(malloc(size))))
 
118
      {
 
119
        mem->size= size;
 
120
        mem->left= pre_alloc_size;
 
121
        mem->next= *prev;
 
122
        *prev= mem_root->pre_alloc= mem;
 
123
      }
 
124
      else
 
125
      {
 
126
        mem_root->pre_alloc= 0;
 
127
      }
 
128
    }
 
129
  }
 
130
  else
 
131
  {
 
132
    mem_root->pre_alloc= 0;
 
133
  }
 
134
}
 
135
 
 
136
 
 
137
void *memory::alloc_root(memory::Root *mem_root, size_t length)
 
138
{
 
139
  size_t get_size, block_size;
 
140
  unsigned char* point;
 
141
  memory::internal::UsedMemory *next= NULL;
 
142
  memory::internal::UsedMemory **prev;
 
143
  assert(alloc_root_inited(mem_root));
 
144
 
 
145
  length= ALIGN_SIZE(length);
 
146
  if ((*(prev= &mem_root->free)) != NULL)
 
147
  {
 
148
    if ((*prev)->left < length &&
 
149
        mem_root->first_block_usage++ >= MAX_BLOCK_USAGE_BEFORE_DROP &&
 
150
        (*prev)->left < MAX_BLOCK_TO_DROP)
 
151
    {
 
152
      next= *prev;
 
153
      *prev= next->next;                        /* Remove block from list */
 
154
      next->next= mem_root->used;
 
155
      mem_root->used= next;
 
156
      mem_root->first_block_usage= 0;
 
157
    }
 
158
    for (next= *prev ; next && next->left < length ; next= next->next)
 
159
      prev= &next->next;
 
160
  }
 
161
  if (! next)
 
162
  {                                             /* Time to alloc new block */
 
163
    block_size= mem_root->block_size * (mem_root->block_num >> 2);
 
164
    get_size= length+ALIGN_SIZE(sizeof(memory::internal::UsedMemory));
 
165
    get_size= max(get_size, block_size);
 
166
 
 
167
    if (!(next = static_cast<memory::internal::UsedMemory *>(malloc(get_size))))
 
168
    {
 
169
      if (mem_root->error_handler)
 
170
        (*mem_root->error_handler)();
 
171
      return NULL;
 
172
    }
 
173
    mem_root->block_num++;
 
174
    next->next= *prev;
 
175
    next->size= get_size;
 
176
    next->left= get_size-ALIGN_SIZE(sizeof(memory::internal::UsedMemory));
 
177
    *prev=next;
 
178
  }
 
179
 
 
180
  point= (unsigned char*) ((char*) next+ (next->size-next->left));
 
181
  /*TODO: next part may be unneded due to mem_root->first_block_usage counter*/
 
182
  if ((next->left-= length) < mem_root->min_malloc)
 
183
  {                                             /* Full block */
 
184
    *prev= next->next;                          /* Remove block from list */
 
185
    next->next= mem_root->used;
 
186
    mem_root->used= next;
 
187
    mem_root->first_block_usage= 0;
 
188
  }
 
189
  return((void*) point);
 
190
}
 
191
 
 
192
 
 
193
/*
 
194
  Allocate many pointers at the same time.
 
195
 
 
196
  DESCRIPTION
 
197
    ptr1, ptr2, etc all point into big allocated memory area.
 
198
 
 
199
  SYNOPSIS
 
200
    multi_alloc_root()
 
201
      root               Memory root
 
202
      ptr1, length1      Multiple arguments terminated by a NULL pointer
 
203
      ptr2, length2      ...
 
204
      ...
 
205
      NULL
 
206
 
 
207
  RETURN VALUE
 
208
    A pointer to the beginning of the allocated memory block
 
209
    in case of success or NULL if out of memory.
 
210
*/
 
211
 
 
212
void *memory::multi_alloc_root(memory::Root *root, ...)
 
213
{
 
214
  va_list args;
 
215
  char **ptr, *start, *res;
 
216
  size_t tot_length, length;
 
217
 
 
218
  va_start(args, root);
 
219
  tot_length= 0;
 
220
  while ((ptr= va_arg(args, char **)))
 
221
  {
 
222
    length= va_arg(args, uint);
 
223
    tot_length+= ALIGN_SIZE(length);
 
224
  }
 
225
  va_end(args);
 
226
 
 
227
  if (!(start= (char*) memory::alloc_root(root, tot_length)))
 
228
    return(0);
 
229
 
 
230
  va_start(args, root);
 
231
  res= start;
 
232
  while ((ptr= va_arg(args, char **)))
 
233
  {
 
234
    *ptr= res;
 
235
    length= va_arg(args, uint);
 
236
    res+= ALIGN_SIZE(length);
 
237
  }
 
238
  va_end(args);
 
239
  return((void*) start);
 
240
}
 
241
 
 
242
#define TRASH_MEM(X) TRASH(((char*)(X) + ((X)->size-(X)->left)), (X)->left)
 
243
 
 
244
/* Mark all data in blocks free for reusage */
 
245
 
 
246
static inline void mark_blocks_free(memory::Root* root)
 
247
{
 
248
  memory::internal::UsedMemory *next;
 
249
  memory::internal::UsedMemory **last;
 
250
 
 
251
  /* iterate through (partially) free blocks, mark them free */
 
252
  last= &root->free;
 
253
  for (next= root->free; next; next= *(last= &next->next))
 
254
  {
 
255
    next->left= next->size - ALIGN_SIZE(sizeof(memory::internal::UsedMemory));
 
256
    TRASH_MEM(next);
 
257
  }
 
258
 
 
259
  /* Combine the free and the used list */
 
260
  *last= next=root->used;
 
261
 
 
262
  /* now go through the used blocks and mark them free */
 
263
  for (; next; next= next->next)
 
264
  {
 
265
    next->left= next->size - ALIGN_SIZE(sizeof(memory::internal::UsedMemory));
 
266
    TRASH_MEM(next);
 
267
  }
 
268
 
 
269
  /* Now everything is set; Indicate that nothing is used anymore */
 
270
  root->used= 0;
 
271
  root->first_block_usage= 0;
 
272
}
 
273
 
 
274
 
 
275
/*
 
276
  Deallocate everything used by memory::alloc_root or just move
 
277
  used blocks to free list if called with MY_USED_TO_FREE
 
278
 
 
279
  SYNOPSIS
 
280
    free_root()
 
281
      root              Memory root
 
282
      MyFlags           Flags for what should be freed:
 
283
 
 
284
        MARK_BLOCKS_FREED       Don't free blocks, just mark them free
 
285
        KEEP_PREALLOC           If this is not set, then free also the
 
286
                                preallocated block
 
287
 
 
288
  NOTES
 
289
    One can call this function either with root block initialised with
 
290
    init_alloc_root() or with a zero:ed block.
 
291
    It's also safe to call this multiple times with the same mem_root.
 
292
*/
 
293
 
 
294
void memory::free_root(memory::Root *root, myf MyFlags)
 
295
{
 
296
  memory::internal::UsedMemory *next,*old;
 
297
 
 
298
  if (MyFlags & memory::MARK_BLOCKS_FREE)
 
299
  {
 
300
    mark_blocks_free(root);
 
301
    return;
 
302
  }
 
303
  if (!(MyFlags & memory::KEEP_PREALLOC))
 
304
    root->pre_alloc=0;
 
305
 
 
306
  for (next=root->used; next ;)
 
307
  {
 
308
    old=next; next= next->next ;
 
309
    if (old != root->pre_alloc)
 
310
      free(old);
 
311
  }
 
312
  for (next=root->free ; next ;)
 
313
  {
 
314
    old=next; next= next->next;
 
315
    if (old != root->pre_alloc)
 
316
      free(old);
 
317
  }
 
318
  root->used=root->free=0;
 
319
  if (root->pre_alloc)
 
320
  {
 
321
    root->free=root->pre_alloc;
 
322
    root->free->left=root->pre_alloc->size-ALIGN_SIZE(sizeof(memory::internal::UsedMemory));
 
323
    TRASH_MEM(root->pre_alloc);
 
324
    root->free->next=0;
 
325
  }
 
326
  root->block_num= 4;
 
327
  root->first_block_usage= 0;
 
328
  return;
 
329
}
 
330
 
 
331
/*
 
332
  Find block that contains an object and set the pre_alloc to it
 
333
*/
 
334
 
 
335
void memory::set_prealloc_root(memory::Root *root, char *ptr)
 
336
{
 
337
  memory::internal::UsedMemory *next;
 
338
  for (next=root->used; next ; next=next->next)
 
339
  {
 
340
    if ((char*) next <= ptr && (char*) next + next->size > ptr)
 
341
    {
 
342
      root->pre_alloc=next;
 
343
      return;
 
344
    }
 
345
  }
 
346
  for (next=root->free ; next ; next=next->next)
 
347
  {
 
348
    if ((char*) next <= ptr && (char*) next + next->size > ptr)
 
349
    {
 
350
      root->pre_alloc=next;
 
351
      return;
 
352
    }
 
353
  }
 
354
}
 
355
 
 
356
 
 
357
char *memory::strdup_root(memory::Root *root, const char *str)
 
358
{
 
359
  return strmake_root(root, str, strlen(str));
 
360
}
 
361
 
 
362
 
 
363
char *memory::strmake_root(memory::Root *root, const char *str, size_t len)
 
364
{
 
365
  char *pos;
 
366
  if ((pos=(char *)memory::alloc_root(root,len+1)))
 
367
  {
 
368
    memcpy(pos,str,len);
 
369
    pos[len]=0;
 
370
  }
 
371
  return pos;
 
372
}
 
373
 
 
374
 
 
375
void *memory::memdup_root(memory::Root *root, const void *str, size_t len)
 
376
{
 
377
  void *pos;
 
378
  if ((pos=memory::alloc_root(root,len)))
 
379
    memcpy(pos,str,len);
 
380
  return pos;
 
381
}
 
382
 
 
383
} /* namespace drizzled */