← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to plugin/heap/hp_dspace.cc

  • Committer: Padraig O'Sullivan
  • Date: 2009-09-13 00:53:34 UTC
  • mto: (1126.9.2 captain-20090915-01)
  • mto: This revision was merged to the branch mainline in revision 1133.
  • Revision ID: osullivan.padraig@gmail.com-20090913005334-6wio2sbjugskfbm3
Added calls to the connection start/end dtrace probes.

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugin/heap/hp_dspace.cc
1
 
/* Copyright (C) 2000-2002 MySQL AB
2
 
   Copyright (C) 2008 eBay, Inc
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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
16
 
 
17
 
/* Implements various base dataspace-related functions - allocate, free, clear */
18
 
 
19
 
#include "heap_priv.h"
20
 
 
21
 
#include <cassert>
22
 
 
23
 
 
24
 
/*
25
 
  MySQL Heap tables keep data in arrays of fixed-size chunks.
26
 
  These chunks are organized into two groups of HP_BLOCK structures:
27
 
    - group1 contains indexes, with one HP_BLOCK per key
28
 
      (part of HP_KEYDEF)
29
 
    - group2 contains record data, with single HP_BLOCK
30
 
      for all records, referenced by HP_SHARE.recordspace.block
31
 
 
32
 
  While columns used in index are usually small, other columns
33
 
  in the table may need to accomodate larger data. Typically,
34
 
  larger data is placed into VARCHAR or BLOB columns. With actual
35
 
  sizes varying, Heap Engine has to support variable-sized records
36
 
  in memory. Heap Engine implements the concept of dataspace
37
 
  (HP_DATASPACE), which incorporates HP_BLOCK for the record data,
38
 
  and adds more information for managing variable-sized records.
39
 
 
40
 
  Variable-size records are stored in multiple "chunks",
41
 
  which means that a single record of data (database "row") can
42
 
  consist of multiple chunks organized into one "set". HP_BLOCK
43
 
  contains chunks. In variable-size format, one record
44
 
  is represented as one or many chunks, depending on the actual
45
 
  data, while in fixed-size mode, one record is always represented
46
 
  as one chunk. The index structures would always point to the first
47
 
  chunk in the chunkset.
48
 
 
49
 
  At the time of table creation, Heap Engine attempts to find out
50
 
  if variable-size records are desired. A user can request
51
 
  variable-size records by providing either row_type=dynamic or
52
 
  block_size=NNN table create option. Heap Engine will check
53
 
  whether block_size provides enough space in the first chunk
54
 
  to keep all null bits and columns that are used in indexes.
55
 
  If block_size is too small, table creation will be aborted
56
 
  with an error. Heap Engine will revert to fixed-size allocation
57
 
  mode if block_size provides no memory benefits (no VARCHAR
58
 
  fields extending past first chunk).
59
 
 
60
 
  In order to improve index search performance, Heap Engine needs
61
 
  to keep all null flags and all columns used as keys inside
62
 
  the first chunk of a chunkset. In particular, this means that
63
 
  all columns used as keys should be defined first in the table
64
 
  creation SQL. The length of data used by null bits and key columns
65
 
  is stored as fixed_data_length inside HP_SHARE. fixed_data_length
66
 
  will extend past last key column if more fixed-length fields can
67
 
  fit into the first chunk.
68
 
 
69
 
  Variable-size records are necessary only in the presence
70
 
  of variable-size columns. Heap Engine will be looking for VARCHAR
71
 
  columns, which declare length of 32 or more. If no such columns
72
 
  are found, table will be switched to fixed-size format. You should
73
 
  always try to put such columns at the end of the table definition.
74
 
 
75
 
  Whenever data is being inserted or updated in the table
76
 
  Heap Engine will calculate how many chunks are necessary.
77
 
  For insert operations, Heap Engine allocates new chunkset in
78
 
  the recordspace. For update operations it will modify length of
79
 
  the existing chunkset, unlinking unnecessary chunks at the end,
80
 
  or allocating and adding more if larger length is necessary.
81
 
 
82
 
  When writing data to chunks or copying data back to record,
83
 
  Heap Engine will first copy fixed_data_length of data using single
84
 
  memcpy call. The rest of the columns are processed one-by-one.
85
 
  Non-VARCHAR columns are copied in their full format. VARCHAR's
86
 
  are copied based on their actual length. Any NULL values after
87
 
  fixed_data_length are skipped.
88
 
 
89
 
  The allocation and contents of the actual chunks varies between
90
 
  fixed and variable-size modes. Total chunk length is always
91
 
  aligned to the next sizeof(unsigned char*). Here is the format of
92
 
  fixed-size chunk:
93
 
      unsigned char[] - sizeof=chunk_dataspace_length, but at least
94
 
               sizeof(unsigned char*) bytes. Keeps actual data or pointer
95
 
               to the next deleted chunk.
96
 
               chunk_dataspace_length equals to full record length
97
 
      unsigned char   - status field (1 means "in use", 0 means "deleted")
98
 
  Variable-size uses different format:
99
 
      unsigned char[] - sizeof=chunk_dataspace_length, but at least
100
 
               sizeof(unsigned char*) bytes. Keeps actual data or pointer
101
 
               to the next deleted chunk.
102
 
               chunk_dataspace_length is set according to table
103
 
               setup (block_size)
104
 
      unsigned char*  - pointer to the next chunk in this chunkset,
105
 
               or NULL for the last chunk
106
 
      unsigned char  -  status field (1 means "first", 0 means "deleted",
107
 
               2 means "linked")
108
 
 
109
 
  When allocating a new chunkset of N chunks, Heap Engine will try
110
 
  to allocate chunks one-by-one, linking them as they become
111
 
  allocated. Allocation of a single chunk will attempt to reuse
112
 
  a deleted (freed) chunk. If no free chunks are available,
113
 
  it will attempt to allocate a new area inside HP_BLOCK.
114
 
  Freeing chunks will place them at the front of free list
115
 
  referenced by del_link in HP_DATASPACE. The newly freed chunk
116
 
  will contain reference to the previously freed chunk in its first
117
 
  sizeof(unsigned char*) of the payload space.
118
 
 
119
 
  Here is open issues:
120
 
    1. It is not very nice to require people to keep key columns
121
 
       at the beginning of the table creation SQL. There are three
122
 
       proposed resolutions:
123
 
       a. Leave it as is. It's a reasonable limitation
124
 
       b. Add new HA_KEEP_KEY_COLUMNS_TO_FRONT flag to handler.h and
125
 
          make table.cpp align columns when it creates the table
126
 
       c. Make HeapEngine reorder columns in the chunk data, so that
127
 
          key columns go first. Add parallel HA_KEYSEG structures
128
 
          to distinguish positions in record vs. positions in
129
 
          the first chunk. Copy all data field-by-field rather than
130
 
          using single memcpy unless DBA kept key columns to
131
 
          the beginning.
132
 
    2. heap_check_heap needs verify linked chunks, looking for
133
 
       issues such as orphans, cycles, and bad links. However,
134
 
       Heap Engine today does not do similar things even for
135
 
       free list.
136
 
    3. With new HP_DATASPACE allocation mechaism, BLOB will become
137
 
       increasingly simple to implement, but I may not have time
138
 
       for that. In one approach, BLOB data can be placed at
139
 
       the end of the same record. In another approach (which I
140
 
       prefer) BLOB data would have its own HP_DATASPACE with
141
 
       variable-size entries.
142
 
    4. In a more sophisticated implementation, some space can
143
 
       be saved even with all fixed-size columns if many of them
144
 
       have NULL value, as long as these columns are not used
145
 
       in indexes
146
 
    5. In variable-size format status should be moved to lower
147
 
       bits of the "next" pointer. Pointer is always aligned
148
 
       to sizeof(unsigned char*), which is at least 4, leaving 2 lower
149
 
       bits free. This will save 8 bytes per chunk
150
 
       on 64-bit platform.
151
 
    6. As we do not want to modify FRM format, BLOCK_SIZE option
152
 
       of "CREATE TABLE" is saved as "RAID_CHUNKSIZE" for
153
 
       Heap Engine tables.
154
 
*/
155
 
 
156
 
static unsigned char *hp_allocate_one_chunk(HP_DATASPACE *info);
157
 
 
158
 
 
159
 
/**
160
 
  Clear a dataspace
161
 
 
162
 
  Frees memory and zeros-out any relevant counters in the dataspace
163
 
 
164
 
  @param  info  the dataspace to clear
165
 
*/
166
 
 
167
 
void hp_clear_dataspace(HP_DATASPACE *info)
168
 
{
169
 
  if (info->block.levels)
170
 
  {
171
 
    hp_free_level(&info->block,info->block.levels,info->block.root,
172
 
                  (unsigned char*) 0);
173
 
  }
174
 
  info->block.levels=0;
175
 
  info->del_chunk_count= info->chunk_count= 0;
176
 
  info->del_link=0;
177
 
  info->total_data_length= 0;
178
 
}
179
 
 
180
 
 
181
 
/**
182
 
  Allocate or reallocate a chunkset in the dataspace
183
 
 
184
 
  Attempts to allocate a new chunkset or change the size of an existing chunkset
185
 
 
186
 
  @param  info            the hosting dataspace
187
 
  @param  chunk_count     the number of chunks that we expect as the result
188
 
  @param  existing_set    non-null value asks function to resize existing chunkset,
189
 
                          return value would point to this set
190
 
 
191
 
  @return  Pointer to the first chunk in the new or updated chunkset, or NULL if unsuccessful
192
 
*/
193
 
 
194
 
static unsigned char *hp_allocate_variable_chunkset(HP_DATASPACE *info,
195
 
                                           uint32_t chunk_count, unsigned char* existing_set)
196
 
{
197
 
  int alloc_count= chunk_count, i;
198
 
  unsigned char *first_chunk= 0, *curr_chunk= 0, *prev_chunk= 0, *last_existing_chunk= 0;
199
 
 
200
 
  assert(alloc_count);
201
 
 
202
 
  if (existing_set)
203
 
  {
204
 
    first_chunk= existing_set;
205
 
 
206
 
    curr_chunk= existing_set;
207
 
    while (curr_chunk && alloc_count)
208
 
    {
209
 
      prev_chunk= curr_chunk;
210
 
      curr_chunk= *((unsigned char**)(curr_chunk + info->offset_link));
211
 
      alloc_count--;
212
 
    }
213
 
 
214
 
    if (!alloc_count)
215
 
    {
216
 
      if (curr_chunk)
217
 
      {
218
 
        /* We came through all chunks and there is more left, let's truncate the list */
219
 
        *((unsigned char**)(prev_chunk + info->offset_link)) = NULL;
220
 
        hp_free_chunks(info, curr_chunk);
221
 
      }
222
 
 
223
 
      return first_chunk;
224
 
    }
225
 
 
226
 
    last_existing_chunk = prev_chunk;
227
 
  }
228
 
 
229
 
  /* We can reach this point only if we're allocating new chunkset or more chunks in existing set */
230
 
 
231
 
  for (i=0; i<alloc_count; i++)
232
 
  {
233
 
      curr_chunk= hp_allocate_one_chunk(info);
234
 
      if (!curr_chunk)
235
 
      {
236
 
        /* no space in the current block */
237
 
 
238
 
        if (last_existing_chunk)
239
 
        {
240
 
          /* Truncate whatever was added at the end of the existing chunkset */
241
 
          prev_chunk= last_existing_chunk;
242
 
          curr_chunk= *((unsigned char**)(prev_chunk + info->offset_link));
243
 
          *((unsigned char**)(prev_chunk + info->offset_link)) = NULL;
244
 
          hp_free_chunks(info, curr_chunk);
245
 
        }
246
 
        else if (first_chunk)
247
 
        {
248
 
          /* free any chunks previously allocated */
249
 
          hp_free_chunks(info, first_chunk);
250
 
        }
251
 
 
252
 
        return NULL;
253
 
      }
254
 
 
255
 
      /* mark as if this chunk is last in the chunkset */
256
 
      *((unsigned char**) (curr_chunk + info->offset_link))= 0;
257
 
 
258
 
      if (prev_chunk)
259
 
      {
260
 
        /* tie them into a linked list */
261
 
        *((unsigned char**) (prev_chunk + info->offset_link))= curr_chunk;
262
 
        curr_chunk[info->offset_status]= CHUNK_STATUS_LINKED;                   /* Record linked from active */
263
 
      }
264
 
      else
265
 
      {
266
 
        curr_chunk[info->offset_status]= CHUNK_STATUS_ACTIVE;                     /* Record active */
267
 
      }
268
 
 
269
 
      if (!first_chunk)
270
 
      {
271
 
        first_chunk= curr_chunk;
272
 
      }
273
 
 
274
 
      prev_chunk= curr_chunk;
275
 
  }
276
 
 
277
 
  return first_chunk;
278
 
}
279
 
 
280
 
 
281
 
/**
282
 
  Allocate a new chunkset in the dataspace
283
 
 
284
 
  Attempts to allocate a new chunkset
285
 
 
286
 
  @param  info            the hosting dataspace
287
 
  @param  chunk_count     the number of chunks that we expect as the result
288
 
 
289
 
  @return  Pointer to the first chunk in the new or updated chunkset, or NULL if unsuccessful
290
 
*/
291
 
 
292
 
unsigned char *hp_allocate_chunkset(HP_DATASPACE *info, uint32_t chunk_count)
293
 
{
294
 
  unsigned char* result;
295
 
 
296
 
 
297
 
  if (info->is_variable_size)
298
 
  {
299
 
    result = hp_allocate_variable_chunkset(info, chunk_count, NULL);
300
 
  }
301
 
  else
302
 
  {
303
 
    result= hp_allocate_one_chunk(info);
304
 
    if (result)
305
 
    {
306
 
      result[info->offset_status]= CHUNK_STATUS_ACTIVE;
307
 
    }
308
 
 
309
 
    return(result);
310
 
  }
311
 
 
312
 
  return(result);
313
 
}
314
 
 
315
 
 
316
 
/**
317
 
  Reallocate an existing chunkset in the dataspace
318
 
 
319
 
  Attempts to change the size of an existing chunkset
320
 
 
321
 
  @param  info            the hosting dataspace
322
 
  @param  chunk_count     the number of chunks that we expect as the result
323
 
  @param  pos             pointer to the existing chunkset
324
 
 
325
 
  @return  Error code or zero if successful
326
 
*/
327
 
 
328
 
int hp_reallocate_chunkset(HP_DATASPACE *info, uint32_t chunk_count, unsigned char* pos)
329
 
{
330
 
 
331
 
  if (!info->is_variable_size)
332
 
  {
333
 
    /* Update should never change chunk_count in fixed-size mode */
334
 
    errno=HA_ERR_WRONG_COMMAND;
335
 
    return errno;
336
 
  }
337
 
 
338
 
  /* Reallocate never moves the first chunk */
339
 
  if (!hp_allocate_variable_chunkset(info, chunk_count, pos))
340
 
    return(errno);
341
 
 
342
 
  return(0);
343
 
}
344
 
 
345
 
 
346
 
/**
347
 
  Allocate a single chunk in the dataspace
348
 
 
349
 
  Attempts to allocate a new chunk or reuse one from deleted list
350
 
 
351
 
  @param  info            the hosting dataspace
352
 
 
353
 
  @return  Pointer to the chunk, or NULL if unsuccessful
354
 
*/
355
 
 
356
 
static unsigned char *hp_allocate_one_chunk(HP_DATASPACE *info)
357
 
{
358
 
  unsigned char* curr_chunk;
359
 
  size_t length, block_pos;
360
 
 
361
 
  if (info->del_link)
362
 
  {
363
 
    curr_chunk=info->del_link;
364
 
    info->del_link= *((unsigned char**) curr_chunk);
365
 
    info->del_chunk_count--;
366
 
 
367
 
    return curr_chunk;
368
 
  }
369
 
 
370
 
  block_pos= (info->chunk_count % info->block.records_in_block);
371
 
  if (!block_pos)
372
 
  {
373
 
    if (hp_get_new_block(&info->block,&length))
374
 
    {
375
 
      /* no space in the current block */
376
 
      return NULL;
377
 
    }
378
 
 
379
 
    info->total_data_length+= length;
380
 
  }
381
 
 
382
 
  info->chunk_count++;
383
 
  curr_chunk= ((unsigned char*) info->block.level_info[0].last_blocks +
384
 
    block_pos * info->block.recbuffer);
385
 
 
386
 
 
387
 
  return curr_chunk;
388
 
}
389
 
 
390
 
 
391
 
/**
392
 
  Free a list of chunks
393
 
 
394
 
  Reclaims all chunks linked by the pointer,
395
 
  which could be the whole chunkset or a part of an existing chunkset
396
 
 
397
 
  @param  info            the hosting dataspace
398
 
  @param  pos             pointer to the head of the chunkset
399
 
*/
400
 
 
401
 
void hp_free_chunks(HP_DATASPACE *info, unsigned char *pos)
402
 
{
403
 
  unsigned char* curr_chunk= pos;
404
 
 
405
 
  while (curr_chunk) {
406
 
    info->del_chunk_count++;
407
 
    *((unsigned char**) curr_chunk)= info->del_link;
408
 
    info->del_link= curr_chunk;
409
 
 
410
 
    curr_chunk[info->offset_status]= CHUNK_STATUS_DELETED;
411
 
 
412
 
 
413
 
    if (!info->is_variable_size)
414
 
    {
415
 
      break;
416
 
    }
417
 
 
418
 
    /* Delete next chunk in this chunkset */
419
 
    curr_chunk= *((unsigned char**)(curr_chunk + info->offset_link));
420
 
  }
421
 
}