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