1 /*
2 Copyright (c) 2006, 2019, 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 "pc.hpp"
27 #include <stdio.h>
28 #include <assert.h>
29 #include <NdbOut.hpp>
30 #include <my_systime.h> // my_micro_time
31
32 /**
33 * Trick to be able to use ERROR_INSERTED macro inside DynArr256 and
34 * DynArr256Pool by directing to member function implemented inline in
35 * DynArr256.hpp where cerrorInsert is not hidden by below macro definition.
36 */
37 #ifdef ERROR_INSERT
38 #define cerrorInsert get_ERROR_INSERT_VALUE()
39 #endif
40
41 #define DA256_BITS 5
42 #define DA256_MASK 31
43
44 struct DA256CL
45 {
46 Uint32 m_magic;
47 Uint32 m_data[15];
48 };
49
50 struct DA256Free
51 {
52 Uint32 m_magic;
53 Uint32 m_next_free;
54 Uint32 m_prev_free;
55 };
56
57 struct DA256Node
58 {
59 struct DA256CL m_lines[17];
60 };
61
62 struct DA256Page
63 {
64 struct DA256CL m_header[2];
65 struct DA256Node m_nodes[30];
66
67 bool get(Uint32 node, Uint32 idx, Uint32 type_id, Uint32*& val_ptr) const;
68 bool is_empty() const;
69 bool is_full() const;
70 Uint32 first_free() const;
71 Uint32 last_free() const;
72 };
73
74 inline
is_empty() const75 bool DA256Page::is_empty() const
76 {
77 return !(0x7fff & (m_header[0].m_magic | m_header[1].m_magic));
78 }
79
80 inline
is_full() const81 bool DA256Page::is_full() const
82 {
83 return !(0x7fff & ~(m_header[0].m_magic & m_header[1].m_magic));
84 }
85
86 inline
first_free() const87 Uint32 DA256Page::first_free() const
88 {
89 Uint32 node = BitmaskImpl::ctz(~m_header[0].m_magic | 0x8000);
90 if (node == 15)
91 node = 15 + BitmaskImpl::ctz(~m_header[1].m_magic | 0x8000);
92 return node;
93 }
94
95 inline
last_free() const96 Uint32 DA256Page::last_free() const
97 {
98 Uint32 node = 29 - BitmaskImpl::clz((~m_header[1].m_magic << 17) | 0x10000);
99 if (node == 14)
100 node = 14 - BitmaskImpl::clz((~m_header[0].m_magic << 17) | 0x10000);
101 return node;
102 }
103
104
105 #undef require
106 #define require(x) require_exit_or_core_with_printer((x), 0, ndbout_printer)
107 //#define DA256_USE_PX
108 //#define DA256_USE_PREFETCH
109 #define DA256_EXTRA_SAFE
110
111 #ifdef TEST_DYNARR256
112 #define UNIT_TEST
113 #include "NdbTap.hpp"
114 #endif
115
116 #ifdef UNIT_TEST
117 #include "my_sys.h"
118 #ifdef USE_CALLGRIND
119 #include <valgrind/callgrind.h>
120 #else
121 #define CALLGRIND_TOGGLE_COLLECT()
122 #endif
123 Uint32 verbose = 0;
124 Uint32 allocatedpages = 0;
125 Uint32 releasedpages = 0;
126 Uint32 maxallocatedpages = 0;
127 Uint32 allocatednodes = 0;
128 Uint32 releasednodes = 0;
129 Uint32 maxallocatednodes = 0;
130 #endif
131
132 static
133 inline
div15(Uint32 x)134 Uint32 div15(Uint32 x)
135 {
136 return ((x << 8) + (x << 4) + x + 255) >> 12;
137 }
138
DynArr256Pool()139 DynArr256Pool::DynArr256Pool()
140 {
141 m_type_id = RNIL;
142 m_first_free = RNIL;
143 m_last_free = RNIL;
144 m_memroot = 0;
145 m_inuse_nodes = 0;
146 m_pg_count = 0;
147 m_used = 0;
148 m_usedHi = 0;
149 }
150
151 void
init(Uint32 type_id,const Pool_context & pc)152 DynArr256Pool::init(Uint32 type_id, const Pool_context & pc)
153 {
154 init(0, type_id, pc);
155 }
156
157 void
init(NdbMutex * m,Uint32 type_id,const Pool_context & pc)158 DynArr256Pool::init(NdbMutex* m, Uint32 type_id, const Pool_context & pc)
159 {
160 m_ctx = pc;
161 m_type_id = type_id;
162 m_memroot = (DA256Page*)m_ctx.get_memroot();
163 m_mutex = m;
164 }
165
166 inline
167 bool
get(Uint32 node,Uint32 idx,Uint32 type_id,Uint32 * & val_ptr) const168 DA256Page::get(Uint32 node, Uint32 idx, Uint32 type_id, Uint32*& val_ptr) const
169 {
170 Uint32 *magic_ptr, p;
171 if (idx != 255)
172 {
173 Uint32 line = div15(idx);
174 Uint32* ptr = (Uint32*)(m_nodes + node);
175
176 p = 0;
177 val_ptr = (ptr + 1 + idx + line);
178 magic_ptr =(ptr + (idx & ~15));
179 }
180 else
181 {
182 Uint32 b = (node + 1) >> 4;
183 Uint32 * ptr = (Uint32*)(m_header+b);
184
185 p = node - (b << 4) + b;
186 val_ptr = (ptr + 1 + p);
187 magic_ptr = ptr;
188 }
189
190 Uint32 magic = *magic_ptr;
191
192 return ((magic & (1 << p)) && (magic >> 16) == type_id);
193 }
194
getByteSize() const195 Uint32 DynArr256::Head::getByteSize() const
196 {
197 assert(m_no_of_nodes >= 0);
198 return static_cast<Uint32>(m_no_of_nodes) * sizeof(DA256Node);
199 }
200
201 static const Uint32 g_max_sizes[5] = { 0, 256, 65536, 16777216, 4294967295U };
202
203 /**
204 * sz = 0 = 1 - 0 level
205 * sz = 1 = 256^1 - 1 level
206 * sz = 2 = 256^2 - 2 level
207 * sz = 3 = 256^3 - 3 level
208 * sz = 4 = 256^4 - 4 level
209 */
210 Uint32 *
get_dirty(Uint32 pos) const211 DynArr256::get_dirty(Uint32 pos) const
212 {
213 Uint32 sz = m_head.m_sz;
214 Uint32 ptrI = m_head.m_ptr_i;
215 DA256Page * memroot = m_pool.m_memroot;
216 Uint32 type_id = (~m_pool.m_type_id) & 0xFFFF;
217
218 if (unlikely(pos >= g_max_sizes[sz]))
219 {
220 return 0;
221 }
222
223 #ifdef DA256_USE_PX
224 Uint32 px[4] = { (pos >> 24) & 255,
225 (pos >> 16) & 255,
226 (pos >> 8) & 255,
227 (pos >> 0) & 255 };
228 #endif
229
230 Uint32* retVal = &m_head.m_ptr_i;
231 for(; sz --;)
232 {
233 if (unlikely(ptrI == RNIL))
234 {
235 return 0;
236 }
237 #ifdef DA256_USE_PX
238 Uint32 p0 = px[sz];
239 #else
240 Uint32 shr = sz << 3;
241 Uint32 p0 = (pos >> shr) & 255;
242 #endif
243 Uint32 page_no = ptrI >> DA256_BITS;
244 Uint32 page_idx = ptrI & DA256_MASK;
245 DA256Page * page = memroot + page_no;
246
247 if (unlikely(! page->get(page_idx, p0, type_id, retVal)))
248 goto err;
249
250 ptrI = *retVal;
251 }
252
253 return retVal;
254 err:
255 require(false);
256 return 0;
257 }
258
259 Uint32 *
set(Uint32 pos)260 DynArr256::set(Uint32 pos)
261 {
262 Uint32 sz = m_head.m_sz;
263 Uint32 type_id = (~m_pool.m_type_id) & 0xFFFF;
264 DA256Page * memroot = m_pool.m_memroot;
265
266 if (unlikely(pos >= g_max_sizes[sz]))
267 {
268 if (unlikely(!expand(pos)))
269 {
270 return 0;
271 }
272 sz = m_head.m_sz;
273 }
274
275 #ifdef DA256_USE_PX
276 Uint32 px[4] = { (pos >> 24) & 255,
277 (pos >> 16) & 255,
278 (pos >> 8) & 255,
279 (pos >> 0) & 255 };
280 #endif
281
282 Uint32 ptrI = m_head.m_ptr_i;
283 Uint32 *retVal = &m_head.m_ptr_i;
284 for(; sz --;)
285 {
286 #ifdef DA256_USE_PX
287 Uint32 p0 = px[sz];
288 #else
289 Uint32 shr = sz << 3;
290 Uint32 p0 = (pos >> shr) & 255;
291 #endif
292 if (ptrI == RNIL)
293 {
294 if(ERROR_INSERTED(3005))
295 {
296 // Demonstrate Bug#25851801 7.6.2(DMR2):: COMPLETE CLUSTER CRASHED DURING UNIQUE KEY CREATION ...
297 // Simulate m_pool.seize() failed.
298 return 0;
299 }
300 if (unlikely((ptrI = m_pool.seize()) == RNIL))
301 {
302 return 0;
303 }
304 m_head.m_no_of_nodes++;
305 * retVal = ptrI;
306 }
307
308 Uint32 page_no = ptrI >> DA256_BITS;
309 Uint32 page_idx = ptrI & DA256_MASK;
310 DA256Page * page = memroot + page_no;
311
312 if (unlikely(! page->get(page_idx, p0, type_id, retVal)))
313 goto err;
314
315 ptrI = * retVal;
316 }
317
318 #if defined VM_TRACE || defined ERROR_INSERT
319 if (pos > m_head.m_high_pos)
320 m_head.m_high_pos = pos;
321 #endif
322
323 return retVal;
324
325 err:
326 require(false);
327 return 0;
328 }
329
330 static
331 inline
332 void
initpage(DA256Page * p,Uint32 page_no,Uint32 type_id)333 initpage(DA256Page* p, Uint32 page_no, Uint32 type_id)
334 {
335 Uint32 i, j;
336 #ifdef DA256_USE_PREFETCH
337 #if defined(__GNUC__) && !(__GNUC__ == 2 && __GNUC_MINOR__ < 96)
338 #ifdef DA256_EXTRA_SAFE
339 for (i = 0; i<(30 * 17 + 2); i++)
340 {
341 __builtin_prefetch (p->m_header + i, 1);
342 }
343 #else
344 {
345 __builtin_prefetch (p->m_header + 0, 1);
346 __builtin_prefetch (p->m_header + 1, 1);
347 for (i = 0; i<30; i++)
348 {
349 __builtin_prefetch (p->m_nodes + i, 1);
350 }
351 }
352 #endif
353 #endif
354 #endif
355 DA256CL* cl;
356 for (i = 0; i<2; i++)
357 {
358 cl = p->m_header + i;
359 cl->m_magic = (~type_id << 16);
360 }
361
362 DA256Free* free;
363
364 for (i = 0; i<30; i++)
365 {
366 free = (DA256Free*)(p->m_nodes+i);
367 free->m_magic = type_id;
368 free->m_next_free = RNIL;
369 free->m_prev_free = RNIL;
370 #ifdef DA256_EXTRA_SAFE
371 DA256Node* node = p->m_nodes+i;
372 for (j = 0; j<17; j++)
373 node->m_lines[j].m_magic = type_id;
374 #endif
375 }
376 }
377
378 bool
expand(Uint32 pos)379 DynArr256::expand(Uint32 pos)
380 {
381 Uint32 i;
382 Uint32 idx = 0;
383 Uint32 alloc[5];
384 Uint32 sz = m_head.m_sz;
385
386 for (; pos >= g_max_sizes[sz]; sz++);
387
388 if (m_head.m_sz == 0)
389 {
390 m_head.m_sz = sz;
391 return true;
392 }
393
394 sz = m_head.m_sz;
395 for (; pos >= g_max_sizes[sz]; sz++)
396 {
397 Uint32 ptrI = m_pool.seize();
398 if (unlikely(ptrI == RNIL))
399 goto err;
400 m_head.m_no_of_nodes++;
401 alloc[idx++] = ptrI;
402 }
403
404 alloc[idx] = m_head.m_ptr_i;
405 m_head.m_sz = 1;
406 for (i = 0; i<idx; i++)
407 {
408 m_head.m_ptr_i = alloc[i];
409 Uint32 * ptr = get(0);
410 * ptr = alloc[i + 1];
411 }
412
413 m_head.m_sz = sz;
414 m_head.m_ptr_i = alloc[0];
415
416 return true;
417
418 err:
419 for (i = 0; i<idx; i++)
420 m_pool.release(alloc[i]);
421
422 m_head.m_no_of_nodes -= idx;
423 assert(m_head.m_no_of_nodes >= 0);
424 return false;
425 }
426
427 void
init(ReleaseIterator & iter)428 DynArr256::init(ReleaseIterator &iter)
429 {
430 iter.m_sz = 1;
431 iter.m_pos = ~(~0U << (8 * m_head.m_sz));
432 iter.m_ptr_i[1] = m_head.m_ptr_i;
433 iter.m_ptr_i[2] = RNIL;
434 iter.m_ptr_i[3] = RNIL;
435 iter.m_ptr_i[4] = RNIL;
436 }
437
438 /**
439 * Iter is in next pos
440 *
441 * 0 - done
442 * 1 - data
443 * 2 - no data
444 *
445 * if ptrVal is NULL, truncate work in trim mode and will stop
446 * (return 0) as soon value is not RNIL
447 */
448 Uint32
truncate(Uint32 trunc_pos,ReleaseIterator & iter,Uint32 * ptrVal)449 DynArr256::truncate(Uint32 trunc_pos, ReleaseIterator& iter, Uint32* ptrVal)
450 {
451 Uint32 type_id = (~m_pool.m_type_id) & 0xFFFF;
452 DA256Page * memroot = m_pool.m_memroot;
453
454 for (;;)
455 {
456 if (iter.m_sz == 0 ||
457 iter.m_pos < trunc_pos ||
458 m_head.m_sz == 0 ||
459 m_head.m_no_of_nodes == 0)
460 {
461 if (m_head.m_sz == 1 && m_head.m_ptr_i == RNIL)
462 {
463 assert(m_head.m_no_of_nodes == 0);
464 m_head.m_sz = 0;
465 }
466 return 0;
467 }
468
469 Uint32* refPtr;
470 Uint32 ptrI = iter.m_ptr_i[iter.m_sz];
471 assert(ptrI != RNIL);
472 Uint32 page_no = ptrI >> DA256_BITS;
473 Uint32 page_idx = (ptrI & DA256_MASK) ;
474 DA256Page* page = memroot + page_no;
475 Uint32 node_addr = (iter.m_pos >> (8 * (m_head.m_sz - iter.m_sz)));
476 Uint32 node_index = node_addr & 255;
477 bool is_value = (iter.m_sz == m_head.m_sz);
478
479 if (unlikely(! page->get(page_idx, node_index, type_id, refPtr)))
480 {
481 require(false);
482 }
483 assert(refPtr != NULL);
484 if (ptrVal != NULL)
485 {
486 *ptrVal = *refPtr;
487 }
488 else if (is_value && *refPtr != RNIL)
489 {
490 return 0;
491 }
492
493 if (iter.m_sz == 1 &&
494 node_addr == 0)
495 {
496 assert(iter.m_ptr_i[iter.m_sz] == m_head.m_ptr_i);
497 assert(iter.m_ptr_i[iter.m_sz + 1] == RNIL);
498 iter.m_ptr_i[iter.m_sz] = is_value ? RNIL : *refPtr;
499 m_pool.release(m_head.m_ptr_i);
500 m_head.m_sz --;
501 m_head.m_no_of_nodes--;
502 assert(m_head.m_no_of_nodes >= 0);
503 m_head.m_ptr_i = iter.m_ptr_i[iter.m_sz];
504 if (is_value)
505 return 1;
506 }
507 else if (is_value || iter.m_ptr_i[iter.m_sz + 1] == *refPtr)
508 { // sz--
509 Uint32 ptrI = *refPtr;
510 if (!is_value)
511 {
512 if (ptrI != RNIL)
513 {
514 m_pool.release(ptrI);
515 m_head.m_no_of_nodes--;
516 assert(m_head.m_no_of_nodes >= 0);
517 *refPtr = iter.m_ptr_i[iter.m_sz+1] = RNIL;
518 }
519 }
520 if (node_index == 0)
521 {
522 iter.m_sz --;
523 }
524 else if (!is_value && ptrI == RNIL)
525 {
526 assert((~iter.m_pos & ~(0xffffffff << (8 * (m_head.m_sz - iter.m_sz)))) == 0);
527 iter.m_pos -= 1U << (8 * (m_head.m_sz - iter.m_sz));
528 }
529 else
530 {
531 assert((iter.m_pos & ~(0xffffffff << (8 * (m_head.m_sz - iter.m_sz)))) == 0);
532 iter.m_pos --;
533 }
534 #if defined VM_TRACE || defined ERROR_INSERT
535 if (iter.m_pos < m_head.m_high_pos)
536 m_head.m_high_pos = iter.m_pos;
537 #endif
538 if (is_value && ptrVal != NULL)
539 return 1;
540 }
541 else
542 { // sz++
543 assert(iter.m_ptr_i[iter.m_sz + 1] == RNIL);
544 iter.m_sz ++;
545 iter.m_ptr_i[iter.m_sz] = *refPtr;
546 return 2;
547 }
548 }
549 }
550
551 static
552 inline
553 bool
seizenode(DA256Page * page,Uint32 idx,Uint32 type_id)554 seizenode(DA256Page* page, Uint32 idx, Uint32 type_id)
555 {
556 Uint32 i;
557 Uint32 b = (idx + 1) >> 4;
558 Uint32 p = idx - (b << 4) + b;
559
560 DA256Node * ptr = (DA256Node*)(page->m_nodes + idx);
561
562 #ifdef DA256_USE_PREFETCH
563 #if defined(__GNUC__) && !(__GNUC__ == 2 && __GNUC_MINOR__ < 96)
564 __builtin_prefetch (page->m_header + b, 1);
565 for (i = 0; i<17; i++)
566 {
567 __builtin_prefetch (ptr->m_lines+i, 1);
568 }
569 #endif
570 #endif
571
572 #ifdef DA256_EXTRA_SAFE
573 Uint32 check = type_id;
574 #endif
575 type_id = ((~type_id) << 16) | 0xFFFF;
576
577 #ifdef DA256_EXTRA_SAFE
578 if (unlikely(((page->m_header + b)->m_magic & (1 << p)) != 0))
579 {
580 return false;
581 }
582 #endif
583
584 (page->m_header + b)->m_magic |= (1 << p);
585 (page->m_header + b)->m_data[p] = RNIL;
586 for (i = 0; i<17; i++)
587 {
588 DA256CL * line = ptr->m_lines + i;
589 #ifdef DA256_EXTRA_SAFE
590 if (unlikely(line->m_magic != check))
591 {
592 return false;
593 }
594 #endif
595 line->m_magic = type_id;
596 for (Uint32 j = 0; j<15; j++)
597 line->m_data[j] = RNIL;
598 }
599
600 #ifdef UNIT_TEST
601 allocatednodes++;
602 if (allocatednodes - releasednodes > maxallocatednodes)
603 maxallocatednodes = allocatednodes - releasednodes;
604 #endif
605 return true;
606 }
607
608 static
609 bool
releasenode(DA256Page * page,Uint32 idx,Uint32 type_id)610 releasenode(DA256Page* page, Uint32 idx, Uint32 type_id)
611 {
612 Uint32 i;
613 Uint32 b = (idx + 1) >> 4;
614 Uint32 p = idx - (b << 4) + b;
615
616 DA256Node * ptr = (DA256Node*)(page->m_nodes + idx);
617
618 #ifdef DA256_USE_PREFETCH
619 #if defined(__GNUC__) && !(__GNUC__ == 2 && __GNUC_MINOR__ < 96)
620 __builtin_prefetch (page->m_header + b, 1);
621 for (i = 0; i<17; i++)
622 {
623 __builtin_prefetch (ptr->m_lines+i, 1);
624 }
625 #endif
626 #endif
627
628 #ifdef DA256_EXTRA_SAFE
629 Uint32 check = ((~type_id) << 16) | 0xFFFF;
630 #endif
631
632 #ifdef DA256_EXTRA_SAFE
633 if (unlikely((((page->m_header + b)->m_magic & (1 << p)) == 0)))
634 {
635 return false;
636 }
637 #endif
638
639 (page->m_header + b)->m_magic ^= (1 << p);
640 for (i = 0; i<17; i++)
641 {
642 DA256CL * line = ptr->m_lines + i;
643 #ifdef DA256_EXTRA_SAFE
644 if (unlikely(line->m_magic != check))
645 {
646 return false;
647 }
648 #endif
649 line->m_magic = type_id;
650 }
651
652 #ifdef UNIT_TEST
653 releasednodes++;
654 #endif
655
656 return true;
657 }
658
659 Uint32
seize()660 DynArr256Pool::seize()
661 {
662 Uint32 type_id = m_type_id;
663 DA256Page* page;
664 DA256Page * memroot = m_memroot;
665
666 Guard2 g(m_mutex);
667 Uint32 ff = m_first_free;
668 if (ff == RNIL)
669 {
670 Uint32 page_no;
671 if (likely((page = (DA256Page*)m_ctx.alloc_page27(type_id, &page_no)) != 0))
672 {
673 initpage(page, page_no, type_id);
674 m_pg_count++;
675 #ifdef UNIT_TEST
676 allocatedpages++;
677 if (allocatedpages - releasedpages > maxallocatedpages)
678 maxallocatedpages = allocatedpages - releasedpages;
679 #endif
680 }
681 else
682 {
683 return RNIL;
684 }
685 m_last_free = m_first_free = ff = page_no;
686 }
687 else
688 {
689 page = memroot + ff;
690 }
691
692 Uint32 idx = page->first_free();
693 DA256Free * ptr = (DA256Free*)(page->m_nodes + idx);
694 if (likely(ptr->m_magic == type_id))
695 {
696 Uint32 last_free = page->last_free();
697 Uint32 next_page = ((DA256Free*)(page->m_nodes + last_free))->m_next_free;
698 if (likely(seizenode(page, idx, type_id)))
699 {
700 m_inuse_nodes++;
701 if (page->is_full())
702 {
703 assert(m_first_free == ff);
704 m_first_free = next_page;
705 if (m_first_free == RNIL)
706 {
707 assert(m_last_free == ff);
708 m_last_free = RNIL;
709 }
710 else
711 {
712 page = memroot + next_page;
713 ((DA256Free*)(page->m_nodes + page->last_free()))->m_prev_free = RNIL;
714 }
715 }
716
717 m_used++;
718 if (m_used < m_usedHi)
719 m_usedHi = m_used;
720
721 return (ff << DA256_BITS) | idx;
722 }
723 }
724
725 //error:
726 require(false);
727 return 0;
728 }
729
730 void
release(Uint32 ptrI)731 DynArr256Pool::release(Uint32 ptrI)
732 {
733 Uint32 type_id = m_type_id;
734
735 Uint32 page_no = ptrI >> DA256_BITS;
736 Uint32 page_idx = ptrI & DA256_MASK;
737 DA256Page * memroot = m_memroot;
738 DA256Page * page = memroot + page_no;
739 DA256Free * ptr = (DA256Free*)(page->m_nodes + page_idx);
740
741 Guard2 g(m_mutex);
742 Uint32 last_free = page->last_free();
743 if (likely(releasenode(page, page_idx, type_id)))
744 {
745 m_inuse_nodes--;
746 ptr->m_magic = type_id;
747 if (last_free > 29)
748 { // Add last to page free list
749 Uint32 lf = m_last_free;
750 ptr->m_prev_free = lf;
751 ptr->m_next_free = RNIL;
752 m_last_free = page_no;
753 if (m_first_free == RNIL)
754 m_first_free = page_no;
755
756 if (lf != RNIL)
757 {
758 page = memroot + lf;
759 DA256Free* pptr = (DA256Free*)(page->m_nodes + page->last_free());
760 pptr->m_next_free = page_no;
761 }
762 }
763 else if (page->is_empty())
764 {
765 // TODO msundell: release_page
766 // unlink from free page list
767 Uint32 nextpage = ((DA256Free*)(page->m_nodes + last_free))->m_next_free;
768 Uint32 prevpage = ((DA256Free*)(page->m_nodes + last_free))->m_prev_free;
769 m_ctx.release_page(type_id, page_no);
770 m_pg_count--;
771 #ifdef UNIT_TEST
772 releasedpages ++;
773 #endif
774 if (nextpage != RNIL)
775 {
776 page = memroot + nextpage;
777 ((DA256Free*)(page->m_nodes + page->last_free()))->m_prev_free = prevpage;
778 }
779 if (prevpage != RNIL)
780 {
781 page = memroot + prevpage;
782 ((DA256Free*)(page->m_nodes + page->last_free()))->m_next_free = nextpage;
783 }
784 if (m_first_free == page_no)
785 {
786 m_first_free = nextpage;
787 }
788 if (m_last_free == page_no)
789 m_last_free = prevpage;
790 }
791 else if (page_idx > last_free)
792 { // last free node in page tracks free page list links
793 ptr->m_next_free = ((DA256Free*)(page->m_nodes + last_free))->m_next_free;
794 ptr->m_prev_free = ((DA256Free*)(page->m_nodes + last_free))->m_prev_free;
795 }
796 assert(m_used);
797 m_used--;
798 return;
799 }
800 require(false);
801 }
802
803 const DynArr256Pool::Info
getInfo() const804 DynArr256Pool::getInfo() const
805 {
806 Info info;
807 info.pg_count = m_pg_count;
808 info.pg_byte_sz = static_cast<Uint32>(sizeof(DA256Page));
809 info.inuse_nodes = m_inuse_nodes;
810 info.node_byte_sz = static_cast<Uint32>(sizeof(DA256Node));
811 info.nodes_per_page = 30;
812
813 return info;
814 }
815
816 #ifdef UNIT_TEST
817
818 static
819 bool
release(DynArr256 & arr)820 release(DynArr256& arr)
821 {
822 DynArr256::ReleaseIterator iter;
823 arr.init(iter);
824 Uint32 val;
825 Uint32 cnt=0;
826 Uint64 start;
827 if (verbose > 2)
828 ndbout_c("allocatedpages: %d (max %d) releasedpages: %d allocatednodes: %d (max %d) releasednodes: %d",
829 allocatedpages, maxallocatedpages,
830 releasedpages,
831 allocatednodes, maxallocatednodes,
832 releasednodes);
833 start = my_micro_time();
834 while (arr.release(iter, &val))
835 cnt++;
836 start = my_micro_time() - start;
837 if (verbose > 1)
838 ndbout_c("allocatedpages: %d (max %d) releasedpages: %d allocatednodes: %d (max %d) releasednodes: %d (%llu us)"
839 " releasecnt: %d",
840 allocatedpages, maxallocatedpages,
841 releasedpages,
842 allocatednodes, maxallocatednodes,
843 releasednodes,
844 start, cnt);
845 return true;
846 }
847
848 static
849 bool
simple(DynArr256 & arr,int argc,char * argv[])850 simple(DynArr256 & arr, int argc, char* argv[])
851 {
852 if (verbose) ndbout_c("argc: %d", argc);
853 for (Uint32 i = 1; i<(Uint32)argc; i++)
854 {
855 Uint32 * s = arr.set(atoi(argv[i]));
856 {
857 bool found = false;
858 for (Uint32 j = 1; j<i; j++)
859 {
860 if (atoi(argv[i]) == atoi(argv[j]))
861 {
862 found = true;
863 break;
864 }
865 }
866 if (!found)
867 * s = i;
868 }
869
870 Uint32 * g = arr.get(atoi(argv[i]));
871 Uint32 v = g ? *g : ~0;
872 if (verbose) ndbout_c("p: %p %p %d", s, g, v);
873 }
874 return true;
875 }
876
877 static
878 bool
basic(DynArr256 & arr,int argc,char * argv[])879 basic(DynArr256& arr, int argc, char* argv[])
880 {
881 #define MAXLEN 65536
882
883 Uint32 len = 0;
884 Uint32 save[2*MAXLEN];
885 for (Uint32 i = 0; i<MAXLEN; i++)
886 {
887 int op = (rand() % 100) > 50;
888 if (len == 0)
889 op = 1;
890 if (len == MAXLEN)
891 op = 0;
892 switch(op){
893 case 0:{ // get
894 Uint32 item = (rand() % len) << 1;
895 Uint32 idx = save[item];
896 Uint32 val = save[item+1];
897 //ndbout_c("get(%d)", idx);
898 Uint32 *p = arr.get(idx);
899 require(p);
900 require(* p == val);
901 break;
902 }
903 case 1:{ // set
904 Uint32 item = len << 1;
905 Uint32 idx = i; //rand() & 0xFFFFF; // & 0xFFFFF; //rand(); //(65536*i) / 10000;
906 Uint32 val = rand();
907 #if 0
908 for(Uint32 j = 0; j < item; j += 2)
909 {
910 if (save[j] == idx)
911 {
912 item = j;
913 break;
914 }
915 }
916 #endif
917 //ndbout_c("set(%d, %x)", idx, val);
918 Uint32 *p = arr.set(idx);
919 require(p);
920 if (item == (len << 1))
921 {
922 *p = val;
923 len++;
924 }
925 else
926 {
927 require(* p == save[item+1]);
928 * p = val;
929 }
930 save[item] = idx;
931 save[item+1] = val;
932 }
933 }
934 }
935 return true;
936 }
937
938 static
939 bool
read(DynArr256 & arr,int argc,char ** argv)940 read(DynArr256& arr, int argc, char ** argv)
941 {
942 Uint32 cnt = 100000;
943 Uint64 mbytes = 16*1024;
944 Uint32 seed = (Uint32) time(0);
945 Uint32 seq = 0, seqmask = 0;
946
947 for (int i = 1; i < argc; i++)
948 {
949 if (strncmp(argv[i], "--mbytes=", sizeof("--mbytes=")-1) == 0)
950 {
951 mbytes = atoi(argv[i]+sizeof("--mbytes=")-1);
952 if (argv[i][strlen(argv[i])-1] == 'g' ||
953 argv[i][strlen(argv[i])-1] == 'G')
954 mbytes *= 1024;
955 }
956 else if (strncmp(argv[i], "--cnt=", sizeof("--cnt=")-1) == 0)
957 {
958 cnt = atoi(argv[i]+sizeof("--cnt=")-1);
959 }
960 else if (strncmp(argv[i], "--seq", sizeof("--seq")-1) == 0)
961 {
962 seq = 1;
963 }
964 }
965
966 /**
967 * Populate with 5Mb
968 */
969
970 if (mbytes >= 134217720)
971 {
972 ndberr.println("--mbytes must be less than 134217720");
973 return false;
974 }
975 Uint32 maxidx = (Uint32)((1024*mbytes+31) / 32);
976 Uint32 nodes = (maxidx+255) / 256;
977 Uint32 pages = (nodes + 29)/ 30;
978 if (verbose)
979 ndbout_c("%lldmb data -> %d entries (%dkb)",
980 mbytes, maxidx, 32*pages);
981
982 for (Uint32 i = 0; i<maxidx; i++)
983 {
984 Uint32 *ptr = arr.set(i);
985 require(ptr);
986 * ptr = i;
987 }
988
989 srand(seed);
990
991 if (seq)
992 {
993 seq = rand();
994 seqmask = ~(Uint32)0;
995 }
996
997 if (verbose)
998 ndbout_c("Timing %d %s reads (seed: %u)", cnt,
999 seq ? "sequential" : "random", seed);
1000
1001 for (Uint32 i = 0; i<10; i++)
1002 {
1003 Uint32 sum0 = 0, sum1 = 0;
1004 Uint64 start = my_micro_time();
1005 for (Uint32 i = 0; i<cnt; i++)
1006 {
1007 Uint32 idx = ((rand() & (~seqmask)) + ((i + seq) & seqmask)) % maxidx;
1008 Uint32 *ptr = arr.get(idx);
1009 sum0 += idx;
1010 sum1 += *ptr;
1011 }
1012 start = my_micro_time() - start;
1013 float uspg = (float)start; uspg /= cnt;
1014 if (verbose)
1015 ndbout_c("Elapsed %lldus diff: %d -> %f us/get", start, sum0 - sum1, uspg);
1016 }
1017 return true;
1018 }
1019
1020 static
1021 bool
write(DynArr256 & arr,int argc,char ** argv)1022 write(DynArr256& arr, int argc, char ** argv)
1023 {
1024 Uint32 seq = 0, seqmask = 0;
1025 Uint32 cnt = 100000;
1026 Uint64 mbytes = 16*1024;
1027 Uint32 seed = (Uint32) time(0);
1028
1029 for (int i = 1; i<argc; i++)
1030 {
1031 if (strncmp(argv[i], "--mbytes=", sizeof("--mbytes=")-1) == 0)
1032 {
1033 mbytes = atoi(argv[i]+sizeof("--mbytes=")-1);
1034 if (argv[i][strlen(argv[i])-1] == 'g' ||
1035 argv[i][strlen(argv[i])-1] == 'G')
1036 mbytes *= 1024;
1037 }
1038 else if (strncmp(argv[i], "--cnt=", sizeof("--cnt=")-1) == 0)
1039 {
1040 cnt = atoi(argv[i]+sizeof("--cnt=")-1);
1041 }
1042 else if (strncmp(argv[i], "--seq", sizeof("--seq")-1) == 0)
1043 {
1044 seq = 1;
1045 }
1046 }
1047
1048 /**
1049 * Populate with 5Mb
1050 */
1051
1052 if (mbytes >= 134217720)
1053 {
1054 ndberr.println("--mbytes must be less than 134217720");
1055 return false;
1056 }
1057 Uint32 maxidx = (Uint32)((1024*mbytes+31) / 32);
1058 Uint32 nodes = (maxidx+255) / 256;
1059 Uint32 pages = (nodes + 29)/ 30;
1060 if (verbose)
1061 ndbout_c("%lldmb data -> %d entries (%dkb)",
1062 mbytes, maxidx, 32*pages);
1063
1064 srand(seed);
1065
1066 if (seq)
1067 {
1068 seq = rand();
1069 seqmask = ~(Uint32)0;
1070 }
1071
1072 if (verbose)
1073 ndbout_c("Timing %d %s writes (seed: %u)", cnt,
1074 seq ? "sequential" : "random", seed);
1075 for (Uint32 i = 0; i<10; i++)
1076 {
1077 Uint64 start = my_micro_time();
1078 for (Uint32 i = 0; i<cnt; i++)
1079 {
1080 Uint32 idx = ((rand() & (~seqmask)) + ((i + seq) & seqmask)) % maxidx;
1081 Uint32 *ptr = arr.set(idx);
1082 if (ptr == NULL) break; /* out of memory */
1083 *ptr = i;
1084 }
1085 start = my_micro_time() - start;
1086 float uspg = (float)start; uspg /= cnt;
1087 if (verbose)
1088 ndbout_c("Elapsed %lldus -> %f us/set", start, uspg);
1089 if (!release(arr))
1090 return false;
1091 }
1092 return true;
1093 }
1094
1095 static
1096 void
usage(FILE * f,int argc,char ** argv)1097 usage(FILE *f, int argc, char **argv)
1098 {
1099 fprintf(stderr, "Usage:\n");
1100 fprintf(stderr, "\t%s --simple <index1> <index2> ... <indexN>\n", argv[0]);
1101 fprintf(stderr, "\t%s --basic\n", argv[0]);
1102 fprintf(stderr, "\t%s { --read | --write } [ --mbytes=<megabytes> | --mbytes=<gigabytes>[gG] ] [ --cnt=<count> ] [ --seq ]\n", argv[0]);
1103 fprintf(stderr, "defaults:\n");
1104 fprintf(stderr, "\t--mbytes=16g\n");
1105 fprintf(stderr, "\t--cnt=100000\n");
1106 }
1107
1108 # include "test_context.hpp"
1109
1110 #ifdef TEST_DYNARR256
1111 static
flatten(int argc,char ** argv)1112 char* flatten(int argc, char** argv) /* NOT MT-SAFE */
1113 {
1114 static char buf[10000];
1115 size_t off = 0;
1116 for (; argc > 0; argc--, argv++)
1117 {
1118 int i = 0;
1119 if (off > 0 && (off + 1 < sizeof(buf)))
1120 buf[off++] = ' ';
1121 for (i = 0; (off + 1 < sizeof(buf)) && argv[0][i] != 0; i++, off++)
1122 buf[off] = argv[0][i];
1123 buf[off] = 0;
1124 }
1125 return buf;
1126 }
1127 #endif
1128
1129 int
main(int argc,char ** argv)1130 main(int argc, char** argv)
1131 {
1132 #ifndef TEST_DYNARR256
1133 verbose = 1;
1134 if (argc == 1) {
1135 usage(stderr, argc, argv);
1136 exit(2);
1137 }
1138 #else
1139 verbose = 0;
1140 #endif
1141 while (argc > 1 && strcmp(argv[1], "-v") == 0)
1142 {
1143 verbose++;
1144 argc--;
1145 argv++;
1146 }
1147
1148 Pool_context pc = test_context(10000 /* pages */);
1149
1150 DynArr256Pool pool;
1151 pool.init(0x2001, pc);
1152
1153 DynArr256::Head head;
1154 DynArr256 arr(pool, head);
1155
1156 #ifdef TEST_DYNARR256
1157 if (argc == 1)
1158 {
1159 char *argv[2] = { (char*)"dummy", NULL };
1160 plan(5);
1161 ok(simple(arr, 1, argv), "simple");
1162 ok(basic(arr, 1, argv), "basic");
1163 ok(read(arr, 1, argv), "read");
1164 ok(write(arr, 1, argv), "write");
1165 }
1166 else if (strcmp(argv[1], "--simple") == 0)
1167 {
1168 plan(2);
1169 ok(simple(arr, argc - 1, argv + 1), "simple %s", flatten(argc - 1, argv + 1));
1170 }
1171 else if (strcmp(argv[1], "--basic") == 0)
1172 {
1173 plan(2);
1174 ok(basic(arr, argc - 1, argv + 1), "basic %s", flatten(argc - 1, argv + 1));
1175 }
1176 else if (strcmp(argv[1], "--read") == 0)
1177 {
1178 plan(2);
1179 ok(read(arr, argc - 1, argv + 1), "read %s", flatten(argc - 1, argv + 1));
1180 }
1181 else if (strcmp(argv[1], "--write") == 0)
1182 {
1183 plan(2);
1184 ok(write(arr, argc - 1, argv + 1), "write %s", flatten(argc - 1, argv + 1));
1185 }
1186 else
1187 {
1188 usage(stderr, argc, argv);
1189 BAIL_OUT("Bad usage: %s %s", argv[0], flatten(argc - 1, argv + 1));
1190 }
1191 #else
1192 if (strcmp(argv[1], "--simple") == 0)
1193 simple(arr, argc - 1, argv + 1);
1194 else if (strcmp(argv[1], "--basic") == 0)
1195 basic(arr, argc - 1, argv + 1);
1196 else if (strcmp(argv[1], "--read") == 0)
1197 read(arr, argc - 1, argv + 1);
1198 else if (strcmp(argv[1], "--write") == 0)
1199 write(arr, argc - 1, argv + 1);
1200 else
1201 {
1202 usage(stderr, argc, argv);
1203 exit(2);
1204 }
1205 #endif
1206
1207 release(arr);
1208 if (verbose)
1209 ndbout_c("allocatedpages: %d (max %d) releasedpages: %d allocatednodes: %d (max %d) releasednodes: %d",
1210 allocatedpages, maxallocatedpages,
1211 releasedpages,
1212 allocatednodes, maxallocatednodes,
1213 releasednodes);
1214
1215 #ifdef TEST_DYNARR256
1216 ok(allocatednodes == releasednodes &&
1217 allocatedpages == releasedpages,
1218 "release");
1219 return exit_status();
1220 #else
1221 return 0;
1222 #endif
1223 }
1224
1225 #endif
1226
1227 #define JAM_FILE_ID 233
1228
1229