← Back to branch summary

~ubuntu-branches/ubuntu/precise/mysql-5.5/precise-201203300109

« back to all changes in this revision

Viewing changes to storage/ndb/src/kernel/vm/DynArr256.cpp

  • Committer: Package Import Robot
  • Author(s): Clint Byrum
  • Date: 2011-11-08 11:31:13 UTC
  • Revision ID: package-import@ubuntu.com-20111108113113-3ulw01fvi4vn8m25
Tags: upstream-5.5.17
Import upstream version 5.5.17

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/ndb/src/kernel/vm/DynArr256.cpp
 
1
/* Copyright (C) 2003 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
#include "DynArr256.hpp"
 
17
#include <stdio.h>
 
18
#include <assert.h>
 
19
#include <NdbOut.hpp>
 
20
 
 
21
#define DA256_BITS  5
 
22
#define DA256_MASK 31
 
23
 
 
24
struct DA256CL
 
25
{
 
26
  Uint32 m_magic;
 
27
  Uint32 m_data[15];
 
28
};
 
29
 
 
30
struct DA256Free
 
31
{
 
32
  Uint32 m_magic;
 
33
  Uint32 m_next_free;
 
34
};
 
35
 
 
36
struct DA256Node
 
37
{
 
38
  struct DA256CL m_lines[17];
 
39
};
 
40
 
 
41
struct DA256Page
 
42
{
 
43
  struct DA256CL m_header[2];
 
44
  struct DA256Node m_nodes[30];
 
45
};
 
46
 
 
47
#define require(x) require_impl(x, __LINE__)
 
48
//#define DA256_USE_PX
 
49
//#define DA256_USE_PREFETCH
 
50
#define DA256_EXTRA_SAFE
 
51
 
 
52
 
 
53
#ifdef UNIT_TEST
 
54
#ifdef USE_CALLGRIND
 
55
#include <valgrind/callgrind.h>
 
56
#else
 
57
#define CALLGRIND_TOGGLE_COLLECT()
 
58
#endif
 
59
Uint32 allocatedpages = 0;
 
60
Uint32 allocatednodes = 0;
 
61
Uint32 releasednodes = 0;
 
62
#endif
 
63
 
 
64
inline
 
65
void
 
66
require_impl(bool x, int line)
 
67
{
 
68
  if (!x)
 
69
  {
 
70
    ndbout_c("LINE: %d", line);
 
71
    abort();
 
72
  }
 
73
}
 
74
 
 
75
DynArr256Pool::DynArr256Pool()
 
76
{
 
77
  m_type_id = RNIL;
 
78
  m_first_free = RNIL;
 
79
  m_memroot = 0;
 
80
}
 
81
 
 
82
void
 
83
DynArr256Pool::init(Uint32 type_id, const Pool_context & pc)
 
84
{
 
85
  m_ctx = pc;
 
86
  m_type_id = type_id;
 
87
  m_memroot = (DA256Page*)m_ctx.get_memroot();
 
88
}
 
89
 
 
90
static const Uint32 g_max_sizes[5] = { 0, 256, 65536, 16777216, ~0 };
 
91
 
 
92
/**
 
93
 * sz = 0     =     1 - 0 level
 
94
 * sz = 1     = 256^1 - 1 level
 
95
 * sz = 2     = 256^2 - 2 level
 
96
 * sz = 3     = 256^3 - 3 level
 
97
 * sz = 4     = 256^4 - 4 level
 
98
 */
 
99
Uint32 *
 
100
DynArr256::get(Uint32 pos) const
 
101
{
 
102
  Uint32 sz = m_head.m_sz;
 
103
  Uint32 ptrI = m_head.m_ptr_i;
 
104
  DA256Page * memroot = m_pool.m_memroot;
 
105
  Uint32 type_id = (~m_pool.m_type_id) & 0xFFFF;
 
106
  
 
107
  if (unlikely(pos >= g_max_sizes[sz]))
 
108
  {
 
109
    return 0;
 
110
  }
 
111
  
 
112
#ifdef DA256_USE_PX
 
113
  Uint32 px[4] = { (pos >> 24) & 255, 
 
114
                   (pos >> 16) & 255, 
 
115
                   (pos >> 8)  & 255,
 
116
                   (pos >> 0)  & 255 };
 
117
#endif
 
118
 
 
119
  Uint32* retVal = &m_head.m_ptr_i;
 
120
  for(; sz --;)
 
121
  {
 
122
    if (unlikely(ptrI == RNIL))
 
123
    {
 
124
      return 0;
 
125
    }
 
126
#ifdef DA256_USE_PX
 
127
    Uint32 p0 = px[sz];
 
128
#else
 
129
    Uint32 shr = sz << 3;
 
130
    Uint32 p0 = (pos >> shr) & 255;
 
131
#endif
 
132
    Uint32 page_no = ptrI >> DA256_BITS;
 
133
    Uint32 page_idx = ptrI & DA256_MASK;
 
134
    DA256Page * page = memroot + page_no;
 
135
    
 
136
    Uint32 *magic_ptr, p;
 
137
    if (p0 != 255)
 
138
    {
 
139
      Uint32 line = ((p0 << 8) + (p0 << 4) + p0 + 255) >> 12;
 
140
      Uint32 * ptr = (Uint32*)(page->m_nodes + page_idx);
 
141
      
 
142
      p = 0;
 
143
      retVal = (ptr + 1 + p0 + line);
 
144
      magic_ptr =(ptr + (p0 & ~15));
 
145
    }
 
146
    else
 
147
    {
 
148
      Uint32 b = (page_idx + 1) >> 4;
 
149
      Uint32 * ptr = (Uint32*)(page->m_header+b);
 
150
      
 
151
      p = page_idx - (b << 4) + b;
 
152
      retVal = (ptr + 1 + p);
 
153
      magic_ptr = ptr;
 
154
    }
 
155
    
 
156
    ptrI = *retVal;
 
157
    Uint32 magic = *magic_ptr;
 
158
    
 
159
    if (unlikely(! ((magic & (1 << p)) && (magic >> 16) == type_id)))
 
160
      goto err;
 
161
  }
 
162
  
 
163
  return retVal;
 
164
err:
 
165
  require(false);
 
166
  return 0;
 
167
}
 
168
 
 
169
Uint32 *
 
170
DynArr256::set(Uint32 pos)
 
171
{
 
172
  Uint32 sz = m_head.m_sz;
 
173
  Uint32 type_id = (~m_pool.m_type_id) & 0xFFFF;  
 
174
  DA256Page * memroot = m_pool.m_memroot;
 
175
  
 
176
  if (unlikely(pos >= g_max_sizes[sz]))
 
177
  {
 
178
    if (unlikely(!expand(pos)))
 
179
    {
 
180
      return 0;
 
181
    }
 
182
    sz = m_head.m_sz;
 
183
  }
 
184
  
 
185
#ifdef DA256_USE_PX  
 
186
  Uint32 px[4] = { (pos >> 24) & 255, 
 
187
                   (pos >> 16) & 255, 
 
188
                   (pos >> 8)  & 255,
 
189
                   (pos >> 0)  & 255 };
 
190
#endif
 
191
 
 
192
  Uint32 ptrI = m_head.m_ptr_i;
 
193
  Uint32 *retVal = &m_head.m_ptr_i;
 
194
  for(; sz --;)
 
195
  {
 
196
#ifdef DA256_USE_PX
 
197
    Uint32 p0 = px[sz];
 
198
#else
 
199
    Uint32 shr = sz << 3;
 
200
    Uint32 p0 = (pos >> shr) & 255;
 
201
#endif
 
202
    if (ptrI == RNIL)
 
203
    {
 
204
      if (unlikely((ptrI = m_pool.seize()) == RNIL))
 
205
      {
 
206
        return 0;
 
207
      }
 
208
      * retVal = ptrI;
 
209
    }
 
210
    
 
211
    Uint32 page_no = ptrI >> DA256_BITS;
 
212
    Uint32 page_idx = ptrI & DA256_MASK;
 
213
    DA256Page * page = memroot + page_no;
 
214
    
 
215
    Uint32 *magic_ptr, p;
 
216
    if (p0 != 255)
 
217
    {
 
218
      Uint32 line = ((p0 << 8) + (p0 << 4) + p0 + 255) >> 12;
 
219
      Uint32 * ptr = (Uint32*)(page->m_nodes + page_idx);
 
220
 
 
221
      p = 0;
 
222
      magic_ptr = (ptr + (p0 & ~15));
 
223
      retVal = (ptr + 1 + p0 + line);
 
224
    }
 
225
    else
 
226
    {
 
227
      Uint32 b = (page_idx + 1) >> 4;
 
228
      Uint32 * ptr = (Uint32*)(page->m_header+b);
 
229
      
 
230
      p = page_idx - (b << 4) + b;
 
231
      magic_ptr = ptr;
 
232
      retVal = (ptr + 1 + p);
 
233
    }
 
234
     
 
235
    ptrI = * retVal;
 
236
    Uint32 magic = *magic_ptr;
 
237
 
 
238
    if (unlikely(! ((magic & (1 << p)) && (magic >> 16) == type_id)))
 
239
      goto err;
 
240
  } 
 
241
  
 
242
  return retVal;
 
243
  
 
244
err:
 
245
  require(false);
 
246
  return 0;
 
247
}
 
248
 
 
249
static
 
250
inline
 
251
void
 
252
initpage(DA256Page* p, Uint32 page_no, Uint32 type_id)
 
253
{
 
254
  Uint32 i, j;
 
255
#ifdef DA256_USE_PREFETCH
 
256
#if defined(__GNUC__) && !(__GNUC__ == 2 && __GNUC_MINOR__ < 96)
 
257
#ifdef DA256_EXTRA_SAFE
 
258
  for (i = 0; i<(30 * 17 + 2); i++)
 
259
  {
 
260
    __builtin_prefetch (p->m_header + i, 1);    
 
261
  }
 
262
#else
 
263
  {
 
264
    __builtin_prefetch (p->m_header + 0, 1);    
 
265
    __builtin_prefetch (p->m_header + 1, 1);    
 
266
    for (i = 0; i<30; i++)
 
267
    {
 
268
      __builtin_prefetch (p->m_nodes + i, 1);
 
269
    }
 
270
  }
 
271
#endif
 
272
#endif
 
273
#endif
 
274
  DA256CL* cl;
 
275
  for  (i = 0; i<2; i++)
 
276
  {
 
277
    cl = p->m_header + i;
 
278
    cl->m_magic = (~type_id << 16);
 
279
  }
 
280
  
 
281
  DA256Free* free;
 
282
  
 
283
  for (i = 0; i<30; i++)
 
284
  {
 
285
    free = (DA256Free*)(p->m_nodes+i);
 
286
    free->m_magic = type_id;
 
287
    free->m_next_free = (page_no << DA256_BITS) + (i + 1);
 
288
#ifdef DA256_EXTRA_SAFE
 
289
    DA256Node* node = p->m_nodes+i;
 
290
    for (j = 0; j<17; j++)
 
291
      node->m_lines[j].m_magic = type_id;
 
292
#endif
 
293
  }
 
294
  
 
295
  free = (DA256Free*)(p->m_nodes+29);
 
296
  free->m_next_free = RNIL;
 
297
}
 
298
 
 
299
bool
 
300
DynArr256::expand(Uint32 pos)
 
301
{
 
302
  Uint32 i;
 
303
  Uint32 idx = 0;
 
304
  Uint32 alloc[5];
 
305
  Uint32 sz = m_head.m_sz;
 
306
 
 
307
  for (; pos >= g_max_sizes[sz]; sz++);
 
308
 
 
309
  if (m_head.m_sz == 0)
 
310
  {
 
311
    m_head.m_sz = sz;
 
312
    return true;
 
313
  }
 
314
 
 
315
  sz =  m_head.m_sz;
 
316
  for (; pos >= g_max_sizes[sz]; sz++)
 
317
  {
 
318
    Uint32 ptrI = m_pool.seize();
 
319
    if (unlikely(ptrI == RNIL))
 
320
      goto err;
 
321
    alloc[idx++] = ptrI;
 
322
  }
 
323
  
 
324
  alloc[idx] = m_head.m_ptr_i;
 
325
  m_head.m_sz = 1;
 
326
  for (Uint32 i = 0; i<idx; i++)
 
327
  {
 
328
    m_head.m_ptr_i = alloc[i];
 
329
    Uint32 * ptr = get(0);
 
330
    * ptr = alloc[i + 1];
 
331
  }
 
332
 
 
333
  m_head.m_sz = sz;
 
334
  m_head.m_ptr_i = alloc[0];
 
335
  
 
336
  return true;
 
337
  
 
338
err:
 
339
  for (i = 0; i<idx; i++)
 
340
    m_pool.release(alloc[i]);
 
341
  return false;
 
342
}
 
343
 
 
344
void
 
345
DynArr256::init(ReleaseIterator &iter)
 
346
{
 
347
  iter.m_sz = 1;
 
348
  iter.m_pos = 0;
 
349
  iter.m_ptr_i[0] = RNIL;
 
350
  iter.m_ptr_i[1] = m_head.m_ptr_i;
 
351
  iter.m_ptr_i[2] = RNIL;
 
352
  iter.m_ptr_i[3] = RNIL;
 
353
  iter.m_ptr_i[4] = RNIL;
 
354
}
 
355
 
 
356
/**
 
357
 * Iter is in next pos
 
358
 *
 
359
 * 0 - done
 
360
 * 1 - data
 
361
 * 2 - no data
 
362
 */
 
363
Uint32
 
364
DynArr256::release(ReleaseIterator &iter, Uint32 * retptr)
 
365
{
 
366
  Uint32 sz = iter.m_sz;
 
367
  Uint32 ptrI = iter.m_ptr_i[sz];
 
368
  Uint32 page_no = ptrI >> DA256_BITS;
 
369
  Uint32 page_idx = ptrI & DA256_MASK;
 
370
  Uint32 type_id = (~m_pool.m_type_id) & 0xFFFF;
 
371
  DA256Page * memroot = m_pool.m_memroot;
 
372
  DA256Page * page = memroot + page_no;
 
373
 
 
374
  if (ptrI != RNIL)
 
375
  {
 
376
    Uint32 p0 = iter.m_pos & 255;
 
377
    for (; p0<256; p0++)
 
378
    {
 
379
      Uint32 *retVal, *magic_ptr, p;
 
380
      if (p0 != 255)
 
381
      {
 
382
        Uint32 line = ((p0 << 8) + (p0 << 4) + p0 + 255) >> 12;
 
383
        Uint32 * ptr = (Uint32*)(page->m_nodes + page_idx);
 
384
        
 
385
        p = 0;
 
386
        retVal = (ptr + 1 + p0 + line);
 
387
        magic_ptr =(ptr + (p0 & ~15));
 
388
      }
 
389
      else
 
390
      {
 
391
        Uint32 b = (page_idx + 1) >> 4;
 
392
        Uint32 * ptr = (Uint32*)(page->m_header+b);
 
393
        
 
394
        p = page_idx - (b << 4) + b;
 
395
        retVal = (ptr + 1 + p);
 
396
        magic_ptr = ptr;
 
397
      }
 
398
      
 
399
      Uint32 magic = *magic_ptr;
 
400
      Uint32 val = *retVal;
 
401
      if (unlikely(! ((magic & (1 << p)) && (magic >> 16) == type_id)))
 
402
        goto err;
 
403
      
 
404
      if (sz == m_head.m_sz)
 
405
      {
 
406
        * retptr = val;
 
407
        p0++;
 
408
        if (p0 != 256)
 
409
        {
 
410
          /**
 
411
           * Move next
 
412
           */
 
413
          iter.m_pos &= ~(Uint32)255;
 
414
          iter.m_pos |= p0;
 
415
        }
 
416
        else
 
417
        {
 
418
          /**
 
419
           * Move up
 
420
           */
 
421
          m_pool.release(ptrI);
 
422
          iter.m_sz --;
 
423
          iter.m_pos >>= 8;
 
424
        }
 
425
        return 1;
 
426
      }
 
427
      else if (val != RNIL)
 
428
      {
 
429
        iter.m_sz++;
 
430
        iter.m_ptr_i[iter.m_sz] = val;
 
431
        iter.m_pos = (p0 << 8);
 
432
        * retVal = RNIL;
 
433
        return 2;
 
434
      }
 
435
    }
 
436
    
 
437
    assert(p0 == 256);
 
438
    m_pool.release(ptrI);
 
439
    iter.m_sz --;
 
440
    iter.m_pos >>= 8;
 
441
    return 2;
 
442
  }
 
443
  
 
444
  new (&m_head) Head();
 
445
  return 0;
 
446
  
 
447
err:
 
448
  require(false);
 
449
  return false;
 
450
}
 
451
 
 
452
static
 
453
inline
 
454
bool
 
455
seizenode(DA256Page* page, Uint32 idx, Uint32 type_id)
 
456
{
 
457
  Uint32 i;
 
458
  Uint32 b = (idx + 1) >> 4;
 
459
  Uint32 p = idx - (b << 4) + b;
 
460
  
 
461
  DA256Node * ptr = (DA256Node*)(page->m_nodes + idx);  
 
462
 
 
463
#ifdef DA256_USE_PREFETCH
 
464
#if defined(__GNUC__) && !(__GNUC__ == 2 && __GNUC_MINOR__ < 96)
 
465
  __builtin_prefetch (page->m_header + b, 1); 
 
466
  for (i = 0; i<17; i++)
 
467
  {
 
468
    __builtin_prefetch (ptr->m_lines+i, 1);    
 
469
  }
 
470
#endif
 
471
#endif
 
472
 
 
473
#ifdef DA256_EXTRA_SAFE
 
474
  Uint32 check = type_id;
 
475
#endif
 
476
  type_id = ((~type_id) << 16) | 0xFFFF;
 
477
  
 
478
#ifdef DA256_EXTRA_SAFE
 
479
  if (unlikely(((page->m_header + b)->m_magic & (1 << p)) != 0))
 
480
  {
 
481
    return false;
 
482
  }
 
483
#endif
 
484
 
 
485
  (page->m_header + b)->m_magic |= (1 << p);
 
486
  (page->m_header + b)->m_data[p] = RNIL;
 
487
  for (i = 0; i<17; i++)
 
488
  {
 
489
    DA256CL * line = ptr->m_lines + i;
 
490
#ifdef DA256_EXTRA_SAFE
 
491
    if (unlikely(line->m_magic != check))
 
492
    {
 
493
      return false;
 
494
    }
 
495
#endif
 
496
    line->m_magic = type_id;
 
497
    for (Uint32 j = 0; j<15; j++)
 
498
      line->m_data[j] = RNIL;
 
499
  }
 
500
 
 
501
#ifdef UNIT_TEST
 
502
  allocatednodes++;
 
503
#endif
 
504
  return true;
 
505
}
 
506
 
 
507
static
 
508
bool
 
509
releasenode(DA256Page* page, Uint32 idx, Uint32 type_id)
 
510
{
 
511
  Uint32 i;
 
512
  Uint32 b = (idx + 1) >> 4;
 
513
  Uint32 p = idx - (b << 4) + b;
 
514
  
 
515
  DA256Node * ptr = (DA256Node*)(page->m_nodes + idx);  
 
516
 
 
517
#ifdef DA256_USE_PREFETCH
 
518
#if defined(__GNUC__) && !(__GNUC__ == 2 && __GNUC_MINOR__ < 96)
 
519
  __builtin_prefetch (page->m_header + b, 1); 
 
520
  for (i = 0; i<17; i++)
 
521
  {
 
522
    __builtin_prefetch (ptr->m_lines+i, 1);    
 
523
  }
 
524
#endif
 
525
#endif
 
526
 
 
527
#ifdef DA256_EXTRA_SAFE
 
528
  Uint32 check = ((~type_id) << 16) | 0xFFFF;
 
529
#endif
 
530
 
 
531
#ifdef DA256_EXTRA_SAFE
 
532
  if (unlikely((((page->m_header + b)->m_magic & (1 << p)) == 0)))
 
533
  {
 
534
    return false;
 
535
  }
 
536
#endif
 
537
 
 
538
  (page->m_header + b)->m_magic ^= (1 << p);
 
539
  for (i = 0; i<17; i++)
 
540
  {
 
541
    DA256CL * line = ptr->m_lines + i;
 
542
#ifdef DA256_EXTRA_SAFE
 
543
    if (unlikely(line->m_magic != check))
 
544
    {
 
545
      return false;
 
546
    }
 
547
#endif
 
548
    line->m_magic = type_id;
 
549
  }
 
550
 
 
551
#ifdef UNIT_TEST
 
552
  releasednodes++;
 
553
#endif
 
554
 
 
555
  return true;
 
556
}
 
557
 
 
558
Uint32
 
559
DynArr256Pool::seize()
 
560
{
 
561
  Uint32 ff = m_first_free;
 
562
  Uint32 type_id = m_type_id;
 
563
 
 
564
  DA256Page* page;
 
565
  DA256Page * memroot = m_memroot;
 
566
  if (ff == RNIL)
 
567
  { 
 
568
    Uint32 page_no;
 
569
    if (likely((page = (DA256Page*)m_ctx.alloc_page(type_id, &page_no)) != 0))
 
570
    {
 
571
      initpage(page, page_no, type_id);
 
572
#ifdef UNIT_TEST
 
573
      allocatedpages++;
 
574
#endif
 
575
    }
 
576
    else
 
577
    {
 
578
      return RNIL;
 
579
    }
 
580
    ff = (page_no << DA256_BITS);
 
581
  }
 
582
  else
 
583
  {
 
584
    page = memroot + (ff >> DA256_BITS);
 
585
  }
 
586
  
 
587
  Uint32 idx = ff & DA256_MASK;
 
588
  DA256Free * ptr = (DA256Free*)(page->m_nodes + idx);
 
589
  if (likely(ptr->m_magic == type_id))
 
590
  {
 
591
    Uint32 next = ptr->m_next_free;
 
592
    if (likely(seizenode(page, idx, type_id)))
 
593
    {
 
594
      m_first_free = next;    
 
595
      return ff;
 
596
    }
 
597
  }
 
598
  
 
599
//error:
 
600
  require(false);
 
601
  return 0;
 
602
}
 
603
 
 
604
void
 
605
DynArr256Pool::release(Uint32 ptrI)
 
606
{
 
607
  Uint32 ff = m_first_free;
 
608
  Uint32 type_id = m_type_id;
 
609
 
 
610
  Uint32 page_no = ptrI >> DA256_BITS;
 
611
  Uint32 page_idx = ptrI & DA256_MASK;
 
612
  DA256Page * memroot = m_memroot;
 
613
  DA256Page * page = memroot + page_no;
 
614
  
 
615
  DA256Free * ptr = (DA256Free*)(page->m_nodes + page_idx);
 
616
  if (likely(releasenode(page, page_idx, type_id)))
 
617
  {
 
618
    ptr->m_next_free = ff;
 
619
    ptr->m_magic = type_id;
 
620
    m_first_free = ptrI;
 
621
    return;
 
622
  }
 
623
  require(false);
 
624
}
 
625
 
 
626
#ifdef UNIT_TEST
 
627
 
 
628
#include <NdbTick.h>
 
629
#include "ndbd_malloc_impl.hpp"
 
630
#include "SimulatedBlock.hpp"
 
631
 
 
632
Ndbd_mem_manager mm;
 
633
Configuration cfg;
 
634
Block_context ctx(cfg, mm);
 
635
struct BB : public SimulatedBlock
 
636
{
 
637
  BB(int no, Block_context& ctx) : SimulatedBlock(no, ctx) {}
 
638
};
 
639
 
 
640
BB block(DBACC, ctx);
 
641
 
 
642
static
 
643
void
 
644
simple(DynArr256 & arr, int argc, char* argv[])
 
645
{
 
646
  ndbout_c("argc: %d", argc);
 
647
  for (Uint32 i = 1; i<(Uint32)argc; i++)
 
648
  {
 
649
    Uint32 * s = arr.set(atoi(argv[i]));
 
650
    {
 
651
      bool found = false;
 
652
      for (Uint32 j = 1; j<i; j++)
 
653
      {
 
654
        if (atoi(argv[i]) == atoi(argv[j]))
 
655
        {
 
656
          found = true;
 
657
          break;
 
658
        }
 
659
      }  
 
660
      if (!found)
 
661
        * s = i;
 
662
    }
 
663
    
 
664
    Uint32 * g = arr.get(atoi(argv[i]));
 
665
    Uint32 v = g ? *g : ~0;
 
666
    ndbout_c("p: %p %p %d", s, g, v);
 
667
  }
 
668
}
 
669
 
 
670
static
 
671
void
 
672
basic(DynArr256& arr, int argc, char* argv[])
 
673
{
 
674
#define MAXLEN 65536
 
675
  
 
676
  Uint32 len = 0;
 
677
  Uint32 save[2*MAXLEN];
 
678
  for (Uint32 i = 0; i<MAXLEN; i++)
 
679
  {
 
680
    int op = (rand() % 100) > 50;
 
681
    if (len == 0)
 
682
      op = 1;
 
683
    if (len == MAXLEN)
 
684
      op = 0;
 
685
    switch(op){
 
686
    case 0:{ // get
 
687
      Uint32 item = (rand() % len) << 1;
 
688
      Uint32 idx = save[item];
 
689
      Uint32 val = save[item+1];
 
690
      //ndbout_c("get(%d)", idx);
 
691
      Uint32 *p = arr.get(idx);
 
692
      assert(p);
 
693
      assert(* p == val);
 
694
      break;
 
695
    }
 
696
    case 1:{ // set
 
697
      Uint32 item = len << 1;
 
698
      Uint32 idx = i; //rand() & 0xFFFFF; // & 0xFFFFF; //rand(); //(65536*i) / 10000;
 
699
      Uint32 val = rand();
 
700
#if 0
 
701
      for(Uint32 j = 0; j < item; j += 2)
 
702
      {
 
703
        if (save[j] == idx)
 
704
        {
 
705
          item = j;
 
706
          break;
 
707
        }
 
708
      }
 
709
#endif
 
710
      //ndbout_c("set(%d, %x)", idx, val);
 
711
      Uint32 *p = arr.set(idx);
 
712
      assert(* p);
 
713
      if (item == (len << 1))
 
714
      {
 
715
        *p = val;
 
716
        len++;
 
717
      }
 
718
      else
 
719
      {
 
720
        assert(* p == save[item+1]);
 
721
        * p = val;
 
722
      }
 
723
      save[item] = idx;
 
724
      save[item+1] = val;
 
725
    }
 
726
    }
 
727
  }
 
728
}
 
729
 
 
730
unsigned long long 
 
731
micro()
 
732
{
 
733
  struct timeval tv;
 
734
  gettimeofday(&tv, 0);
 
735
  unsigned long long ret = tv.tv_sec;
 
736
  ret *= 1000000;
 
737
  ret += tv.tv_usec;
 
738
  return ret;
 
739
}
 
740
 
 
741
static
 
742
void
 
743
read(DynArr256& arr, int argc, char ** argv)
 
744
{
 
745
  Uint32 cnt = 100000;
 
746
  Uint64 mbytes = 16*1024;
 
747
  Uint32 seed = time(0);
 
748
  Uint32 seq = 0, seqmask = 0;
 
749
 
 
750
  for (Uint32 i = 2; i<argc; i++)
 
751
  {
 
752
    if (strncmp(argv[i], "--mbytes=", sizeof("--mbytes=")-1) == 0)
 
753
    {
 
754
      mbytes = atoi(argv[i]+sizeof("--mbytes=")-1);
 
755
      if (argv[i][strlen(argv[i])-1] == 'g' ||
 
756
          argv[i][strlen(argv[i])-1] == 'G')
 
757
        mbytes *= 1024;
 
758
    }
 
759
    else if (strncmp(argv[i], "--cnt=", sizeof("--cnt=")-1) == 0)
 
760
    {
 
761
      cnt = atoi(argv[i]+sizeof("--cnt=")-1);
 
762
    }
 
763
    else if (strncmp(argv[i], "--seq", sizeof("--seq")-1) == 0)
 
764
    {
 
765
      seq = 1;
 
766
    }
 
767
  }
 
768
  
 
769
  /**
 
770
   * Populate with 5Mb
 
771
   */
 
772
  Uint32 maxidx = (1024*mbytes+31) / 32;
 
773
  Uint32 nodes = (maxidx+255) / 256;
 
774
  Uint32 pages = (nodes + 29)/ 30;
 
775
  ndbout_c("%lldmb data -> %d entries (%dkb)",
 
776
           mbytes, maxidx, 32*pages);
 
777
  
 
778
  for (Uint32 i = 0; i<maxidx; i++)
 
779
  {
 
780
    Uint32 *ptr = arr.set(i);
 
781
    assert(ptr);
 
782
    * ptr = i;
 
783
  }
 
784
 
 
785
  srand(seed);
 
786
 
 
787
  if (seq)
 
788
  {
 
789
    seq = rand();
 
790
    seqmask = ~(Uint32)0;
 
791
  }
 
792
 
 
793
  ndbout_c("Timing %d %s reads (seed: %u)", cnt, 
 
794
           seq ? "sequential" : "random", seed);
 
795
 
 
796
  for (Uint32 i = 0; i<10; i++)
 
797
  {
 
798
    Uint32 sum0 = 0, sum1 = 0;
 
799
    Uint64 start = micro();
 
800
    for (Uint32 i = 0; i<cnt; i++)
 
801
    {
 
802
      Uint32 idx = ((rand() & (~seqmask)) + ((i + seq) & seqmask)) % maxidx;
 
803
      Uint32 *ptr = arr.get(idx);
 
804
      sum0 += idx;
 
805
      sum1 += *ptr;
 
806
    }
 
807
    start = micro() - start;
 
808
    float uspg = start; uspg /= cnt;
 
809
    ndbout_c("Elapsed %lldus diff: %d -> %f us/get", start, sum0 - sum1, uspg);
 
810
  }
 
811
}
 
812
 
 
813
static
 
814
void
 
815
write(DynArr256& arr, int argc, char ** argv)
 
816
{
 
817
  Uint32 seq = 0, seqmask = 0;
 
818
  Uint32 cnt = 100000;
 
819
  Uint64 mbytes = 16*1024;
 
820
  Uint32 seed = time(0);
 
821
 
 
822
  for (Uint32 i = 2; i<argc; i++)
 
823
  {
 
824
    if (strncmp(argv[i], "--mbytes=", sizeof("--mbytes=")-1) == 0)
 
825
    {
 
826
      mbytes = atoi(argv[i]+sizeof("--mbytes=")-1);
 
827
      if (argv[i][strlen(argv[i])-1] == 'g' ||
 
828
          argv[i][strlen(argv[i])-1] == 'G')
 
829
        mbytes *= 1024;
 
830
    }
 
831
    else if (strncmp(argv[i], "--cnt=", sizeof("--cnt=")-1) == 0)
 
832
    {
 
833
      cnt = atoi(argv[i]+sizeof("--cnt=")-1);
 
834
    }
 
835
    else if (strncmp(argv[i], "--seq", sizeof("--seq")-1) == 0)
 
836
    {
 
837
      seq = 1;
 
838
    }
 
839
  }
 
840
  
 
841
  /**
 
842
   * Populate with 5Mb
 
843
   */
 
844
  Uint32 maxidx = (1024*mbytes+31) / 32;
 
845
  Uint32 nodes = (maxidx+255) / 256;
 
846
  Uint32 pages = (nodes + 29)/ 30;
 
847
  ndbout_c("%lldmb data -> %d entries (%dkb)",
 
848
           mbytes, maxidx, 32*pages);
 
849
 
 
850
  srand(seed);
 
851
 
 
852
  if (seq)
 
853
  {
 
854
    seq = rand();
 
855
    seqmask = ~(Uint32)0;
 
856
  }
 
857
 
 
858
  ndbout_c("Timing %d %s writes (seed: %u)", cnt, 
 
859
           seq ? "sequential" : "random", seed);
 
860
  for (Uint32 i = 0; i<10; i++)
 
861
  {
 
862
    Uint64 start = micro();
 
863
    for (Uint32 i = 0; i<cnt; i++)
 
864
    {
 
865
      Uint32 idx = ((rand() & (~seqmask)) + ((i + seq) & seqmask)) % maxidx;
 
866
      Uint32 *ptr = arr.set(idx);
 
867
      *ptr = i;
 
868
    }
 
869
    start = micro() - start;
 
870
    float uspg = start; uspg /= cnt;
 
871
    ndbout_c("Elapsed %lldus -> %f us/set", start, uspg);
 
872
    DynArr256::ReleaseIterator iter;
 
873
    arr.init(iter);
 
874
    Uint32 val;
 
875
    while(arr.release(iter, &val));
 
876
  }
 
877
}
 
878
 
 
879
int
 
880
main(int argc, char** argv)
 
881
{
 
882
  if (0)
 
883
  {
 
884
    for (Uint32 i = 0; i<30; i++)
 
885
    {
 
886
      Uint32 b = (i + 1) >> 4;
 
887
      Uint32 p = i - (b << 4) + b;
 
888
      printf("[ %d %d %d ]\n", i, b, p);
 
889
    }
 
890
    return 0;
 
891
  }
 
892
 
 
893
  Pool_context pc;
 
894
  pc.m_block = &block;
 
895
  
 
896
  Resource_limit rl;
 
897
  rl.m_min = 0;
 
898
  rl.m_max = 10000;
 
899
  rl.m_resource_id = 0;
 
900
  mm.set_resource_limit(rl);
 
901
  if(!mm.init())
 
902
  {
 
903
    abort();
 
904
  }
 
905
 
 
906
  DynArr256Pool pool;
 
907
  pool.init(0x2001, pc);
 
908
 
 
909
  DynArr256::Head head;
 
910
  DynArr256 arr(pool, head);
 
911
 
 
912
  if (strcmp(argv[1], "--simple") == 0)
 
913
    simple(arr, argc, argv);
 
914
  else if (strcmp(argv[1], "--basic") == 0)
 
915
    basic(arr, argc, argv);
 
916
  else if (strcmp(argv[1], "--read") == 0)
 
917
    read(arr, argc, argv);
 
918
  else if (strcmp(argv[1], "--write") == 0)
 
919
    write(arr, argc, argv);
 
920
 
 
921
  DynArr256::ReleaseIterator iter;
 
922
  arr.init(iter);
 
923
  Uint32 cnt = 0, val;
 
924
  while (arr.release(iter, &val)) cnt++;
 
925
  
 
926
  ndbout_c("allocatedpages: %d allocatednodes: %d releasednodes: %d"
 
927
           " releasecnt: %d",
 
928
           allocatedpages, 
 
929
           allocatednodes,
 
930
           releasednodes,
 
931
           cnt);
 
932
  
 
933
  return 0;
 
934
#if 0
 
935
  printf("sizeof(DA256Page): %d\n", sizeof(DA256Page));
 
936
 
 
937
  DA256Page page;
 
938
 
 
939
  for (Uint32 i = 0; i<10000; i++)
 
940
  {
 
941
    Uint32 arg = rand() & 255;
 
942
    Uint32 base = 0;
 
943
    Uint32 idx = arg & 256;
 
944
    printf("%d\n", arg);
 
945
 
 
946
    assert(base <= 30);
 
947
    
 
948
    if (idx == 255)
 
949
    {
 
950
      Uint32 b = (base + 1) >> 4;
 
951
      Uint32 p = base - (b << 4) + b;
 
952
      Uint32 magic = page.m_header[b].m_magic;
 
953
      Uint32 retVal = page.m_header[b].m_data[p];
 
954
      
 
955
      require(magic & (1 << p));
 
956
      return retVal;
 
957
    }
 
958
    else
 
959
    {
 
960
      // 4 bit extra offset per idx
 
961
      Uint32 line = idx / 15;
 
962
      Uint32 off = idx % 15;
 
963
      
 
964
      {
 
965
        Uint32 pos = 1 + idx + line;
 
966
        Uint32 magic = pos & ~15;
 
967
        
 
968
        Uint32 * ptr = (Uint32*)&page.m_nodes[base];
 
969
        assert((ptr + pos) == &page.m_nodes[base].m_lines[line].m_data[off]);
 
970
        assert((ptr + magic) == &page.m_nodes[base].m_lines[line].m_magic);
 
971
      }
 
972
    }
 
973
  }
 
974
#endif
 
975
}
 
976
 
 
977
Uint32 g_currentStartPhase;
 
978
Uint32 g_start_type;
 
979
NdbNodeBitmask g_nowait_nodes;
 
980
 
 
981
void childExit(int code, Uint32 currentStartPhase)
 
982
{
 
983
  abort();
 
984
}
 
985
 
 
986
void childAbort(int code, Uint32 currentStartPhase)
 
987
{
 
988
  abort();
 
989
}
 
990
 
 
991
void childReportError(int error)
 
992
{
 
993
  abort();
 
994
}
 
995
 
 
996
void
 
997
UpgradeStartup::sendCmAppChg(Ndbcntr& cntr, Signal* signal, Uint32 startLevel){
 
998
}
 
999
 
 
1000
void
 
1001
UpgradeStartup::execCM_APPCHG(SimulatedBlock & block, Signal* signal){
 
1002
}
 
1003
 
 
1004
void
 
1005
UpgradeStartup::sendCntrMasterReq(Ndbcntr& cntr, Signal* signal, Uint32 n){
 
1006
}
 
1007
 
 
1008
void
 
1009
UpgradeStartup::execCNTR_MASTER_REPLY(SimulatedBlock & block, Signal* signal){
 
1010
}
 
1011
 
 
1012
#include <SimBlockList.hpp>
 
1013
 
 
1014
void
 
1015
SimBlockList::unload()
 
1016
{
 
1017
 
 
1018
}
 
1019
 
 
1020
#endif