xref: /freebsd/contrib/llvm-project/openmp/runtime/src/kmp_alloc.cpp (revision 0d8fe2373503aeac48492f28073049a8bfa4feb5)
1 /*
2  * kmp_alloc.cpp -- private/shared dynamic memory allocation and management
3  */
4 
5 //===----------------------------------------------------------------------===//
6 //
7 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
8 // See https://llvm.org/LICENSE.txt for license information.
9 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "kmp.h"
14 #include "kmp_io.h"
15 #include "kmp_wrapper_malloc.h"
16 
17 // Disable bget when it is not used
18 #if KMP_USE_BGET
19 
20 /* Thread private buffer management code */
21 
22 typedef int (*bget_compact_t)(size_t, int);
23 typedef void *(*bget_acquire_t)(size_t);
24 typedef void (*bget_release_t)(void *);
25 
26 /* NOTE: bufsize must be a signed datatype */
27 
28 #if KMP_OS_WINDOWS
29 #if KMP_ARCH_X86 || KMP_ARCH_ARM
30 typedef kmp_int32 bufsize;
31 #else
32 typedef kmp_int64 bufsize;
33 #endif
34 #else
35 typedef ssize_t bufsize;
36 #endif // KMP_OS_WINDOWS
37 
38 /* The three modes of operation are, fifo search, lifo search, and best-fit */
39 
40 typedef enum bget_mode {
41   bget_mode_fifo = 0,
42   bget_mode_lifo = 1,
43   bget_mode_best = 2
44 } bget_mode_t;
45 
46 static void bpool(kmp_info_t *th, void *buffer, bufsize len);
47 static void *bget(kmp_info_t *th, bufsize size);
48 static void *bgetz(kmp_info_t *th, bufsize size);
49 static void *bgetr(kmp_info_t *th, void *buffer, bufsize newsize);
50 static void brel(kmp_info_t *th, void *buf);
51 static void bectl(kmp_info_t *th, bget_compact_t compact,
52                   bget_acquire_t acquire, bget_release_t release,
53                   bufsize pool_incr);
54 
55 /* BGET CONFIGURATION */
56 /* Buffer allocation size quantum: all buffers allocated are a
57    multiple of this size.  This MUST be a power of two. */
58 
59 /* On IA-32 architecture with  Linux* OS, malloc() does not
60    ensure 16 byte alignment */
61 
62 #if KMP_ARCH_X86 || !KMP_HAVE_QUAD
63 
64 #define SizeQuant 8
65 #define AlignType double
66 
67 #else
68 
69 #define SizeQuant 16
70 #define AlignType _Quad
71 
72 #endif
73 
74 // Define this symbol to enable the bstats() function which calculates the
75 // total free space in the buffer pool, the largest available buffer, and the
76 // total space currently allocated.
77 #define BufStats 1
78 
79 #ifdef KMP_DEBUG
80 
81 // Define this symbol to enable the bpoold() function which dumps the buffers
82 // in a buffer pool.
83 #define BufDump 1
84 
85 // Define this symbol to enable the bpoolv() function for validating a buffer
86 // pool.
87 #define BufValid 1
88 
89 // Define this symbol to enable the bufdump() function which allows dumping the
90 // contents of an allocated or free buffer.
91 #define DumpData 1
92 
93 #ifdef NOT_USED_NOW
94 
95 // Wipe free buffers to a guaranteed pattern of garbage to trip up miscreants
96 // who attempt to use pointers into released buffers.
97 #define FreeWipe 1
98 
99 // Use a best fit algorithm when searching for space for an allocation request.
100 // This uses memory more efficiently, but allocation will be much slower.
101 #define BestFit 1
102 
103 #endif /* NOT_USED_NOW */
104 #endif /* KMP_DEBUG */
105 
106 static bufsize bget_bin_size[] = {
107     0,
108     //    1 << 6,    /* .5 Cache line */
109     1 << 7, /* 1 Cache line, new */
110     1 << 8, /* 2 Cache lines */
111     1 << 9, /* 4 Cache lines, new */
112     1 << 10, /* 8 Cache lines */
113     1 << 11, /* 16 Cache lines, new */
114     1 << 12, 1 << 13, /* new */
115     1 << 14, 1 << 15, /* new */
116     1 << 16, 1 << 17, 1 << 18, 1 << 19, 1 << 20, /*  1MB */
117     1 << 21, /*  2MB */
118     1 << 22, /*  4MB */
119     1 << 23, /*  8MB */
120     1 << 24, /* 16MB */
121     1 << 25, /* 32MB */
122 };
123 
124 #define MAX_BGET_BINS (int)(sizeof(bget_bin_size) / sizeof(bufsize))
125 
126 struct bfhead;
127 
128 //  Declare the interface, including the requested buffer size type, bufsize.
129 
130 /* Queue links */
131 typedef struct qlinks {
132   struct bfhead *flink; /* Forward link */
133   struct bfhead *blink; /* Backward link */
134 } qlinks_t;
135 
136 /* Header in allocated and free buffers */
137 typedef struct bhead2 {
138   kmp_info_t *bthr; /* The thread which owns the buffer pool */
139   bufsize prevfree; /* Relative link back to previous free buffer in memory or
140                        0 if previous buffer is allocated.  */
141   bufsize bsize; /* Buffer size: positive if free, negative if allocated. */
142 } bhead2_t;
143 
144 /* Make sure the bhead structure is a multiple of SizeQuant in size. */
145 typedef union bhead {
146   KMP_ALIGN(SizeQuant)
147   AlignType b_align;
148   char b_pad[sizeof(bhead2_t) + (SizeQuant - (sizeof(bhead2_t) % SizeQuant))];
149   bhead2_t bb;
150 } bhead_t;
151 #define BH(p) ((bhead_t *)(p))
152 
153 /*  Header in directly allocated buffers (by acqfcn) */
154 typedef struct bdhead {
155   bufsize tsize; /* Total size, including overhead */
156   bhead_t bh; /* Common header */
157 } bdhead_t;
158 #define BDH(p) ((bdhead_t *)(p))
159 
160 /* Header in free buffers */
161 typedef struct bfhead {
162   bhead_t bh; /* Common allocated/free header */
163   qlinks_t ql; /* Links on free list */
164 } bfhead_t;
165 #define BFH(p) ((bfhead_t *)(p))
166 
167 typedef struct thr_data {
168   bfhead_t freelist[MAX_BGET_BINS];
169 #if BufStats
170   size_t totalloc; /* Total space currently allocated */
171   long numget, numrel; /* Number of bget() and brel() calls */
172   long numpblk; /* Number of pool blocks */
173   long numpget, numprel; /* Number of block gets and rels */
174   long numdget, numdrel; /* Number of direct gets and rels */
175 #endif /* BufStats */
176 
177   /* Automatic expansion block management functions */
178   bget_compact_t compfcn;
179   bget_acquire_t acqfcn;
180   bget_release_t relfcn;
181 
182   bget_mode_t mode; /* what allocation mode to use? */
183 
184   bufsize exp_incr; /* Expansion block size */
185   bufsize pool_len; /* 0: no bpool calls have been made
186                        -1: not all pool blocks are the same size
187                        >0: (common) block size for all bpool calls made so far
188                     */
189   bfhead_t *last_pool; /* Last pool owned by this thread (delay deallocation) */
190 } thr_data_t;
191 
192 /*  Minimum allocation quantum: */
193 #define QLSize (sizeof(qlinks_t))
194 #define SizeQ ((SizeQuant > QLSize) ? SizeQuant : QLSize)
195 #define MaxSize                                                                \
196   (bufsize)(                                                                   \
197       ~(((bufsize)(1) << (sizeof(bufsize) * CHAR_BIT - 1)) | (SizeQuant - 1)))
198 // Maximum for the requested size.
199 
200 /* End sentinel: value placed in bsize field of dummy block delimiting
201    end of pool block.  The most negative number which will  fit  in  a
202    bufsize, defined in a way that the compiler will accept. */
203 
204 #define ESent                                                                  \
205   ((bufsize)(-(((((bufsize)1) << ((int)sizeof(bufsize) * 8 - 2)) - 1) * 2) - 2))
206 
207 /* Thread Data management routines */
208 static int bget_get_bin(bufsize size) {
209   // binary chop bins
210   int lo = 0, hi = MAX_BGET_BINS - 1;
211 
212   KMP_DEBUG_ASSERT(size > 0);
213 
214   while ((hi - lo) > 1) {
215     int mid = (lo + hi) >> 1;
216     if (size < bget_bin_size[mid])
217       hi = mid - 1;
218     else
219       lo = mid;
220   }
221 
222   KMP_DEBUG_ASSERT((lo >= 0) && (lo < MAX_BGET_BINS));
223 
224   return lo;
225 }
226 
227 static void set_thr_data(kmp_info_t *th) {
228   int i;
229   thr_data_t *data;
230 
231   data = (thr_data_t *)((!th->th.th_local.bget_data)
232                             ? __kmp_allocate(sizeof(*data))
233                             : th->th.th_local.bget_data);
234 
235   memset(data, '\0', sizeof(*data));
236 
237   for (i = 0; i < MAX_BGET_BINS; ++i) {
238     data->freelist[i].ql.flink = &data->freelist[i];
239     data->freelist[i].ql.blink = &data->freelist[i];
240   }
241 
242   th->th.th_local.bget_data = data;
243   th->th.th_local.bget_list = 0;
244 #if !USE_CMP_XCHG_FOR_BGET
245 #ifdef USE_QUEUING_LOCK_FOR_BGET
246   __kmp_init_lock(&th->th.th_local.bget_lock);
247 #else
248   __kmp_init_bootstrap_lock(&th->th.th_local.bget_lock);
249 #endif /* USE_LOCK_FOR_BGET */
250 #endif /* ! USE_CMP_XCHG_FOR_BGET */
251 }
252 
253 static thr_data_t *get_thr_data(kmp_info_t *th) {
254   thr_data_t *data;
255 
256   data = (thr_data_t *)th->th.th_local.bget_data;
257 
258   KMP_DEBUG_ASSERT(data != 0);
259 
260   return data;
261 }
262 
263 /* Walk the free list and release the enqueued buffers */
264 static void __kmp_bget_dequeue(kmp_info_t *th) {
265   void *p = TCR_SYNC_PTR(th->th.th_local.bget_list);
266 
267   if (p != 0) {
268 #if USE_CMP_XCHG_FOR_BGET
269     {
270       volatile void *old_value = TCR_SYNC_PTR(th->th.th_local.bget_list);
271       while (!KMP_COMPARE_AND_STORE_PTR(&th->th.th_local.bget_list,
272                                         CCAST(void *, old_value), nullptr)) {
273         KMP_CPU_PAUSE();
274         old_value = TCR_SYNC_PTR(th->th.th_local.bget_list);
275       }
276       p = CCAST(void *, old_value);
277     }
278 #else /* ! USE_CMP_XCHG_FOR_BGET */
279 #ifdef USE_QUEUING_LOCK_FOR_BGET
280     __kmp_acquire_lock(&th->th.th_local.bget_lock, __kmp_gtid_from_thread(th));
281 #else
282     __kmp_acquire_bootstrap_lock(&th->th.th_local.bget_lock);
283 #endif /* USE_QUEUING_LOCK_FOR_BGET */
284 
285     p = (void *)th->th.th_local.bget_list;
286     th->th.th_local.bget_list = 0;
287 
288 #ifdef USE_QUEUING_LOCK_FOR_BGET
289     __kmp_release_lock(&th->th.th_local.bget_lock, __kmp_gtid_from_thread(th));
290 #else
291     __kmp_release_bootstrap_lock(&th->th.th_local.bget_lock);
292 #endif
293 #endif /* USE_CMP_XCHG_FOR_BGET */
294 
295     /* Check again to make sure the list is not empty */
296     while (p != 0) {
297       void *buf = p;
298       bfhead_t *b = BFH(((char *)p) - sizeof(bhead_t));
299 
300       KMP_DEBUG_ASSERT(b->bh.bb.bsize != 0);
301       KMP_DEBUG_ASSERT(((kmp_uintptr_t)TCR_PTR(b->bh.bb.bthr) & ~1) ==
302                        (kmp_uintptr_t)th); // clear possible mark
303       KMP_DEBUG_ASSERT(b->ql.blink == 0);
304 
305       p = (void *)b->ql.flink;
306 
307       brel(th, buf);
308     }
309   }
310 }
311 
312 /* Chain together the free buffers by using the thread owner field */
313 static void __kmp_bget_enqueue(kmp_info_t *th, void *buf
314 #ifdef USE_QUEUING_LOCK_FOR_BGET
315                                ,
316                                kmp_int32 rel_gtid
317 #endif
318                                ) {
319   bfhead_t *b = BFH(((char *)buf) - sizeof(bhead_t));
320 
321   KMP_DEBUG_ASSERT(b->bh.bb.bsize != 0);
322   KMP_DEBUG_ASSERT(((kmp_uintptr_t)TCR_PTR(b->bh.bb.bthr) & ~1) ==
323                    (kmp_uintptr_t)th); // clear possible mark
324 
325   b->ql.blink = 0;
326 
327   KC_TRACE(10, ("__kmp_bget_enqueue: moving buffer to T#%d list\n",
328                 __kmp_gtid_from_thread(th)));
329 
330 #if USE_CMP_XCHG_FOR_BGET
331   {
332     volatile void *old_value = TCR_PTR(th->th.th_local.bget_list);
333     /* the next pointer must be set before setting bget_list to buf to avoid
334        exposing a broken list to other threads, even for an instant. */
335     b->ql.flink = BFH(CCAST(void *, old_value));
336 
337     while (!KMP_COMPARE_AND_STORE_PTR(&th->th.th_local.bget_list,
338                                       CCAST(void *, old_value), buf)) {
339       KMP_CPU_PAUSE();
340       old_value = TCR_PTR(th->th.th_local.bget_list);
341       /* the next pointer must be set before setting bget_list to buf to avoid
342          exposing a broken list to other threads, even for an instant. */
343       b->ql.flink = BFH(CCAST(void *, old_value));
344     }
345   }
346 #else /* ! USE_CMP_XCHG_FOR_BGET */
347 #ifdef USE_QUEUING_LOCK_FOR_BGET
348   __kmp_acquire_lock(&th->th.th_local.bget_lock, rel_gtid);
349 #else
350   __kmp_acquire_bootstrap_lock(&th->th.th_local.bget_lock);
351 #endif
352 
353   b->ql.flink = BFH(th->th.th_local.bget_list);
354   th->th.th_local.bget_list = (void *)buf;
355 
356 #ifdef USE_QUEUING_LOCK_FOR_BGET
357   __kmp_release_lock(&th->th.th_local.bget_lock, rel_gtid);
358 #else
359   __kmp_release_bootstrap_lock(&th->th.th_local.bget_lock);
360 #endif
361 #endif /* USE_CMP_XCHG_FOR_BGET */
362 }
363 
364 /* insert buffer back onto a new freelist */
365 static void __kmp_bget_insert_into_freelist(thr_data_t *thr, bfhead_t *b) {
366   int bin;
367 
368   KMP_DEBUG_ASSERT(((size_t)b) % SizeQuant == 0);
369   KMP_DEBUG_ASSERT(b->bh.bb.bsize % SizeQuant == 0);
370 
371   bin = bget_get_bin(b->bh.bb.bsize);
372 
373   KMP_DEBUG_ASSERT(thr->freelist[bin].ql.blink->ql.flink ==
374                    &thr->freelist[bin]);
375   KMP_DEBUG_ASSERT(thr->freelist[bin].ql.flink->ql.blink ==
376                    &thr->freelist[bin]);
377 
378   b->ql.flink = &thr->freelist[bin];
379   b->ql.blink = thr->freelist[bin].ql.blink;
380 
381   thr->freelist[bin].ql.blink = b;
382   b->ql.blink->ql.flink = b;
383 }
384 
385 /* unlink the buffer from the old freelist */
386 static void __kmp_bget_remove_from_freelist(bfhead_t *b) {
387   KMP_DEBUG_ASSERT(b->ql.blink->ql.flink == b);
388   KMP_DEBUG_ASSERT(b->ql.flink->ql.blink == b);
389 
390   b->ql.blink->ql.flink = b->ql.flink;
391   b->ql.flink->ql.blink = b->ql.blink;
392 }
393 
394 /*  GET STATS -- check info on free list */
395 static void bcheck(kmp_info_t *th, bufsize *max_free, bufsize *total_free) {
396   thr_data_t *thr = get_thr_data(th);
397   int bin;
398 
399   *total_free = *max_free = 0;
400 
401   for (bin = 0; bin < MAX_BGET_BINS; ++bin) {
402     bfhead_t *b, *best;
403 
404     best = &thr->freelist[bin];
405     b = best->ql.flink;
406 
407     while (b != &thr->freelist[bin]) {
408       *total_free += (b->bh.bb.bsize - sizeof(bhead_t));
409       if ((best == &thr->freelist[bin]) || (b->bh.bb.bsize < best->bh.bb.bsize))
410         best = b;
411 
412       /* Link to next buffer */
413       b = b->ql.flink;
414     }
415 
416     if (*max_free < best->bh.bb.bsize)
417       *max_free = best->bh.bb.bsize;
418   }
419 
420   if (*max_free > (bufsize)sizeof(bhead_t))
421     *max_free -= sizeof(bhead_t);
422 }
423 
424 /*  BGET  --  Allocate a buffer.  */
425 static void *bget(kmp_info_t *th, bufsize requested_size) {
426   thr_data_t *thr = get_thr_data(th);
427   bufsize size = requested_size;
428   bfhead_t *b;
429   void *buf;
430   int compactseq = 0;
431   int use_blink = 0;
432   /* For BestFit */
433   bfhead_t *best;
434 
435   if (size < 0 || size + sizeof(bhead_t) > MaxSize) {
436     return NULL;
437   }
438 
439   __kmp_bget_dequeue(th); /* Release any queued buffers */
440 
441   if (size < (bufsize)SizeQ) { // Need at least room for the queue links.
442     size = SizeQ;
443   }
444 #if defined(SizeQuant) && (SizeQuant > 1)
445   size = (size + (SizeQuant - 1)) & (~(SizeQuant - 1));
446 #endif
447 
448   size += sizeof(bhead_t); // Add overhead in allocated buffer to size required.
449   KMP_DEBUG_ASSERT(size >= 0);
450   KMP_DEBUG_ASSERT(size % SizeQuant == 0);
451 
452   use_blink = (thr->mode == bget_mode_lifo);
453 
454   /* If a compact function was provided in the call to bectl(), wrap
455      a loop around the allocation process  to  allow  compaction  to
456      intervene in case we don't find a suitable buffer in the chain. */
457 
458   for (;;) {
459     int bin;
460 
461     for (bin = bget_get_bin(size); bin < MAX_BGET_BINS; ++bin) {
462       /* Link to next buffer */
463       b = (use_blink ? thr->freelist[bin].ql.blink
464                      : thr->freelist[bin].ql.flink);
465 
466       if (thr->mode == bget_mode_best) {
467         best = &thr->freelist[bin];
468 
469         /* Scan the free list searching for the first buffer big enough
470            to hold the requested size buffer. */
471         while (b != &thr->freelist[bin]) {
472           if (b->bh.bb.bsize >= (bufsize)size) {
473             if ((best == &thr->freelist[bin]) ||
474                 (b->bh.bb.bsize < best->bh.bb.bsize)) {
475               best = b;
476             }
477           }
478 
479           /* Link to next buffer */
480           b = (use_blink ? b->ql.blink : b->ql.flink);
481         }
482         b = best;
483       }
484 
485       while (b != &thr->freelist[bin]) {
486         if ((bufsize)b->bh.bb.bsize >= (bufsize)size) {
487 
488           // Buffer is big enough to satisfy the request. Allocate it to the
489           // caller. We must decide whether the buffer is large enough to split
490           // into the part given to the caller and a free buffer that remains
491           // on the free list, or whether the entire buffer should be removed
492           // from the free list and given to the caller in its entirety. We
493           // only split the buffer if enough room remains for a header plus the
494           // minimum quantum of allocation.
495           if ((b->bh.bb.bsize - (bufsize)size) >
496               (bufsize)(SizeQ + (sizeof(bhead_t)))) {
497             bhead_t *ba, *bn;
498 
499             ba = BH(((char *)b) + (b->bh.bb.bsize - (bufsize)size));
500             bn = BH(((char *)ba) + size);
501 
502             KMP_DEBUG_ASSERT(bn->bb.prevfree == b->bh.bb.bsize);
503 
504             /* Subtract size from length of free block. */
505             b->bh.bb.bsize -= (bufsize)size;
506 
507             /* Link allocated buffer to the previous free buffer. */
508             ba->bb.prevfree = b->bh.bb.bsize;
509 
510             /* Plug negative size into user buffer. */
511             ba->bb.bsize = -size;
512 
513             /* Mark this buffer as owned by this thread. */
514             TCW_PTR(ba->bb.bthr,
515                     th); // not an allocated address (do not mark it)
516             /* Mark buffer after this one not preceded by free block. */
517             bn->bb.prevfree = 0;
518 
519             // unlink buffer from old freelist, and reinsert into new freelist
520             __kmp_bget_remove_from_freelist(b);
521             __kmp_bget_insert_into_freelist(thr, b);
522 #if BufStats
523             thr->totalloc += (size_t)size;
524             thr->numget++; /* Increment number of bget() calls */
525 #endif
526             buf = (void *)((((char *)ba) + sizeof(bhead_t)));
527             KMP_DEBUG_ASSERT(((size_t)buf) % SizeQuant == 0);
528             return buf;
529           } else {
530             bhead_t *ba;
531 
532             ba = BH(((char *)b) + b->bh.bb.bsize);
533 
534             KMP_DEBUG_ASSERT(ba->bb.prevfree == b->bh.bb.bsize);
535 
536             /* The buffer isn't big enough to split.  Give  the  whole
537                shebang to the caller and remove it from the free list. */
538 
539             __kmp_bget_remove_from_freelist(b);
540 #if BufStats
541             thr->totalloc += (size_t)b->bh.bb.bsize;
542             thr->numget++; /* Increment number of bget() calls */
543 #endif
544             /* Negate size to mark buffer allocated. */
545             b->bh.bb.bsize = -(b->bh.bb.bsize);
546 
547             /* Mark this buffer as owned by this thread. */
548             TCW_PTR(ba->bb.bthr, th); // not an allocated address (do not mark)
549             /* Zero the back pointer in the next buffer in memory
550                to indicate that this buffer is allocated. */
551             ba->bb.prevfree = 0;
552 
553             /* Give user buffer starting at queue links. */
554             buf = (void *)&(b->ql);
555             KMP_DEBUG_ASSERT(((size_t)buf) % SizeQuant == 0);
556             return buf;
557           }
558         }
559 
560         /* Link to next buffer */
561         b = (use_blink ? b->ql.blink : b->ql.flink);
562       }
563     }
564 
565     /* We failed to find a buffer. If there's a compact function defined,
566        notify it of the size requested. If it returns TRUE, try the allocation
567        again. */
568 
569     if ((thr->compfcn == 0) || (!(*thr->compfcn)(size, ++compactseq))) {
570       break;
571     }
572   }
573 
574   /* No buffer available with requested size free. */
575 
576   /* Don't give up yet -- look in the reserve supply. */
577   if (thr->acqfcn != 0) {
578     if (size > (bufsize)(thr->exp_incr - sizeof(bhead_t))) {
579       /* Request is too large to fit in a single expansion block.
580          Try to satisfy it by a direct buffer acquisition. */
581       bdhead_t *bdh;
582 
583       size += sizeof(bdhead_t) - sizeof(bhead_t);
584 
585       KE_TRACE(10, ("%%%%%% MALLOC( %d )\n", (int)size));
586 
587       /* richryan */
588       bdh = BDH((*thr->acqfcn)((bufsize)size));
589       if (bdh != NULL) {
590 
591         // Mark the buffer special by setting size field of its header to zero.
592         bdh->bh.bb.bsize = 0;
593 
594         /* Mark this buffer as owned by this thread. */
595         TCW_PTR(bdh->bh.bb.bthr, th); // don't mark buffer as allocated,
596         // because direct buffer never goes to free list
597         bdh->bh.bb.prevfree = 0;
598         bdh->tsize = size;
599 #if BufStats
600         thr->totalloc += (size_t)size;
601         thr->numget++; /* Increment number of bget() calls */
602         thr->numdget++; /* Direct bget() call count */
603 #endif
604         buf = (void *)(bdh + 1);
605         KMP_DEBUG_ASSERT(((size_t)buf) % SizeQuant == 0);
606         return buf;
607       }
608 
609     } else {
610 
611       /*  Try to obtain a new expansion block */
612       void *newpool;
613 
614       KE_TRACE(10, ("%%%%%% MALLOCB( %d )\n", (int)thr->exp_incr));
615 
616       /* richryan */
617       newpool = (*thr->acqfcn)((bufsize)thr->exp_incr);
618       KMP_DEBUG_ASSERT(((size_t)newpool) % SizeQuant == 0);
619       if (newpool != NULL) {
620         bpool(th, newpool, thr->exp_incr);
621         buf = bget(
622             th, requested_size); /* This can't, I say, can't get into a loop. */
623         return buf;
624       }
625     }
626   }
627 
628   /*  Still no buffer available */
629 
630   return NULL;
631 }
632 
633 /*  BGETZ  --  Allocate a buffer and clear its contents to zero.  We clear
634                the  entire  contents  of  the buffer to zero, not just the
635                region requested by the caller. */
636 
637 static void *bgetz(kmp_info_t *th, bufsize size) {
638   char *buf = (char *)bget(th, size);
639 
640   if (buf != NULL) {
641     bhead_t *b;
642     bufsize rsize;
643 
644     b = BH(buf - sizeof(bhead_t));
645     rsize = -(b->bb.bsize);
646     if (rsize == 0) {
647       bdhead_t *bd;
648 
649       bd = BDH(buf - sizeof(bdhead_t));
650       rsize = bd->tsize - (bufsize)sizeof(bdhead_t);
651     } else {
652       rsize -= sizeof(bhead_t);
653     }
654 
655     KMP_DEBUG_ASSERT(rsize >= size);
656 
657     (void)memset(buf, 0, (bufsize)rsize);
658   }
659   return ((void *)buf);
660 }
661 
662 /*  BGETR  --  Reallocate a buffer.  This is a minimal implementation,
663                simply in terms of brel()  and  bget().   It  could  be
664                enhanced to allow the buffer to grow into adjacent free
665                blocks and to avoid moving data unnecessarily.  */
666 
667 static void *bgetr(kmp_info_t *th, void *buf, bufsize size) {
668   void *nbuf;
669   bufsize osize; /* Old size of buffer */
670   bhead_t *b;
671 
672   nbuf = bget(th, size);
673   if (nbuf == NULL) { /* Acquire new buffer */
674     return NULL;
675   }
676   if (buf == NULL) {
677     return nbuf;
678   }
679   b = BH(((char *)buf) - sizeof(bhead_t));
680   osize = -b->bb.bsize;
681   if (osize == 0) {
682     /*  Buffer acquired directly through acqfcn. */
683     bdhead_t *bd;
684 
685     bd = BDH(((char *)buf) - sizeof(bdhead_t));
686     osize = bd->tsize - (bufsize)sizeof(bdhead_t);
687   } else {
688     osize -= sizeof(bhead_t);
689   }
690 
691   KMP_DEBUG_ASSERT(osize > 0);
692 
693   (void)KMP_MEMCPY((char *)nbuf, (char *)buf, /* Copy the data */
694                    (size_t)((size < osize) ? size : osize));
695   brel(th, buf);
696 
697   return nbuf;
698 }
699 
700 /*  BREL  --  Release a buffer.  */
701 static void brel(kmp_info_t *th, void *buf) {
702   thr_data_t *thr = get_thr_data(th);
703   bfhead_t *b, *bn;
704   kmp_info_t *bth;
705 
706   KMP_DEBUG_ASSERT(buf != NULL);
707   KMP_DEBUG_ASSERT(((size_t)buf) % SizeQuant == 0);
708 
709   b = BFH(((char *)buf) - sizeof(bhead_t));
710 
711   if (b->bh.bb.bsize == 0) { /* Directly-acquired buffer? */
712     bdhead_t *bdh;
713 
714     bdh = BDH(((char *)buf) - sizeof(bdhead_t));
715     KMP_DEBUG_ASSERT(b->bh.bb.prevfree == 0);
716 #if BufStats
717     thr->totalloc -= (size_t)bdh->tsize;
718     thr->numdrel++; /* Number of direct releases */
719     thr->numrel++; /* Increment number of brel() calls */
720 #endif /* BufStats */
721 #ifdef FreeWipe
722     (void)memset((char *)buf, 0x55, (size_t)(bdh->tsize - sizeof(bdhead_t)));
723 #endif /* FreeWipe */
724 
725     KE_TRACE(10, ("%%%%%% FREE( %p )\n", (void *)bdh));
726 
727     KMP_DEBUG_ASSERT(thr->relfcn != 0);
728     (*thr->relfcn)((void *)bdh); /* Release it directly. */
729     return;
730   }
731 
732   bth = (kmp_info_t *)((kmp_uintptr_t)TCR_PTR(b->bh.bb.bthr) &
733                        ~1); // clear possible mark before comparison
734   if (bth != th) {
735     /* Add this buffer to be released by the owning thread later */
736     __kmp_bget_enqueue(bth, buf
737 #ifdef USE_QUEUING_LOCK_FOR_BGET
738                        ,
739                        __kmp_gtid_from_thread(th)
740 #endif
741                            );
742     return;
743   }
744 
745   /* Buffer size must be negative, indicating that the buffer is allocated. */
746   if (b->bh.bb.bsize >= 0) {
747     bn = NULL;
748   }
749   KMP_DEBUG_ASSERT(b->bh.bb.bsize < 0);
750 
751   /*  Back pointer in next buffer must be zero, indicating the same thing: */
752 
753   KMP_DEBUG_ASSERT(BH((char *)b - b->bh.bb.bsize)->bb.prevfree == 0);
754 
755 #if BufStats
756   thr->numrel++; /* Increment number of brel() calls */
757   thr->totalloc += (size_t)b->bh.bb.bsize;
758 #endif
759 
760   /* If the back link is nonzero, the previous buffer is free.  */
761 
762   if (b->bh.bb.prevfree != 0) {
763     /* The previous buffer is free. Consolidate this buffer with it by adding
764        the length of this buffer to the previous free buffer. Note that we
765        subtract the size in the buffer being released, since it's negative to
766        indicate that the buffer is allocated. */
767     bufsize size = b->bh.bb.bsize;
768 
769     /* Make the previous buffer the one we're working on. */
770     KMP_DEBUG_ASSERT(BH((char *)b - b->bh.bb.prevfree)->bb.bsize ==
771                      b->bh.bb.prevfree);
772     b = BFH(((char *)b) - b->bh.bb.prevfree);
773     b->bh.bb.bsize -= size;
774 
775     /* unlink the buffer from the old freelist */
776     __kmp_bget_remove_from_freelist(b);
777   } else {
778     /* The previous buffer isn't allocated. Mark this buffer size as positive
779        (i.e. free) and fall through to place the buffer on the free list as an
780        isolated free block. */
781     b->bh.bb.bsize = -b->bh.bb.bsize;
782   }
783 
784   /* insert buffer back onto a new freelist */
785   __kmp_bget_insert_into_freelist(thr, b);
786 
787   /* Now we look at the next buffer in memory, located by advancing from
788      the  start  of  this  buffer  by its size, to see if that buffer is
789      free.  If it is, we combine  this  buffer  with  the  next  one  in
790      memory, dechaining the second buffer from the free list. */
791   bn = BFH(((char *)b) + b->bh.bb.bsize);
792   if (bn->bh.bb.bsize > 0) {
793 
794     /* The buffer is free.  Remove it from the free list and add
795        its size to that of our buffer. */
796     KMP_DEBUG_ASSERT(BH((char *)bn + bn->bh.bb.bsize)->bb.prevfree ==
797                      bn->bh.bb.bsize);
798 
799     __kmp_bget_remove_from_freelist(bn);
800 
801     b->bh.bb.bsize += bn->bh.bb.bsize;
802 
803     /* unlink the buffer from the old freelist, and reinsert it into the new
804      * freelist */
805     __kmp_bget_remove_from_freelist(b);
806     __kmp_bget_insert_into_freelist(thr, b);
807 
808     /* Finally,  advance  to   the  buffer  that   follows  the  newly
809        consolidated free block.  We must set its  backpointer  to  the
810        head  of  the  consolidated free block.  We know the next block
811        must be an allocated block because the process of recombination
812        guarantees  that  two  free  blocks will never be contiguous in
813        memory.  */
814     bn = BFH(((char *)b) + b->bh.bb.bsize);
815   }
816 #ifdef FreeWipe
817   (void)memset(((char *)b) + sizeof(bfhead_t), 0x55,
818                (size_t)(b->bh.bb.bsize - sizeof(bfhead_t)));
819 #endif
820   KMP_DEBUG_ASSERT(bn->bh.bb.bsize < 0);
821 
822   /* The next buffer is allocated.  Set the backpointer in it  to  point
823      to this buffer; the previous free buffer in memory. */
824 
825   bn->bh.bb.prevfree = b->bh.bb.bsize;
826 
827   /*  If  a  block-release function is defined, and this free buffer
828       constitutes the entire block, release it.  Note that  pool_len
829       is  defined  in  such a way that the test will fail unless all
830       pool blocks are the same size.  */
831   if (thr->relfcn != 0 &&
832       b->bh.bb.bsize == (bufsize)(thr->pool_len - sizeof(bhead_t))) {
833 #if BufStats
834     if (thr->numpblk !=
835         1) { /* Do not release the last buffer until finalization time */
836 #endif
837 
838       KMP_DEBUG_ASSERT(b->bh.bb.prevfree == 0);
839       KMP_DEBUG_ASSERT(BH((char *)b + b->bh.bb.bsize)->bb.bsize == ESent);
840       KMP_DEBUG_ASSERT(BH((char *)b + b->bh.bb.bsize)->bb.prevfree ==
841                        b->bh.bb.bsize);
842 
843       /*  Unlink the buffer from the free list  */
844       __kmp_bget_remove_from_freelist(b);
845 
846       KE_TRACE(10, ("%%%%%% FREE( %p )\n", (void *)b));
847 
848       (*thr->relfcn)(b);
849 #if BufStats
850       thr->numprel++; /* Nr of expansion block releases */
851       thr->numpblk--; /* Total number of blocks */
852       KMP_DEBUG_ASSERT(thr->numpblk == thr->numpget - thr->numprel);
853 
854       // avoid leaving stale last_pool pointer around if it is being dealloced
855       if (thr->last_pool == b)
856         thr->last_pool = 0;
857     } else {
858       thr->last_pool = b;
859     }
860 #endif /* BufStats */
861   }
862 }
863 
864 /*  BECTL  --  Establish automatic pool expansion control  */
865 static void bectl(kmp_info_t *th, bget_compact_t compact,
866                   bget_acquire_t acquire, bget_release_t release,
867                   bufsize pool_incr) {
868   thr_data_t *thr = get_thr_data(th);
869 
870   thr->compfcn = compact;
871   thr->acqfcn = acquire;
872   thr->relfcn = release;
873   thr->exp_incr = pool_incr;
874 }
875 
876 /*  BPOOL  --  Add a region of memory to the buffer pool.  */
877 static void bpool(kmp_info_t *th, void *buf, bufsize len) {
878   /*    int bin = 0; */
879   thr_data_t *thr = get_thr_data(th);
880   bfhead_t *b = BFH(buf);
881   bhead_t *bn;
882 
883   __kmp_bget_dequeue(th); /* Release any queued buffers */
884 
885 #ifdef SizeQuant
886   len &= ~(SizeQuant - 1);
887 #endif
888   if (thr->pool_len == 0) {
889     thr->pool_len = len;
890   } else if (len != thr->pool_len) {
891     thr->pool_len = -1;
892   }
893 #if BufStats
894   thr->numpget++; /* Number of block acquisitions */
895   thr->numpblk++; /* Number of blocks total */
896   KMP_DEBUG_ASSERT(thr->numpblk == thr->numpget - thr->numprel);
897 #endif /* BufStats */
898 
899   /* Since the block is initially occupied by a single free  buffer,
900      it  had  better  not  be  (much) larger than the largest buffer
901      whose size we can store in bhead.bb.bsize. */
902   KMP_DEBUG_ASSERT(len - sizeof(bhead_t) <= -((bufsize)ESent + 1));
903 
904   /* Clear  the  backpointer at  the start of the block to indicate that
905      there  is  no  free  block  prior  to  this   one.    That   blocks
906      recombination when the first block in memory is released. */
907   b->bh.bb.prevfree = 0;
908 
909   /* Create a dummy allocated buffer at the end of the pool.  This dummy
910      buffer is seen when a buffer at the end of the pool is released and
911      blocks  recombination  of  the last buffer with the dummy buffer at
912      the end.  The length in the dummy buffer  is  set  to  the  largest
913      negative  number  to  denote  the  end  of  the pool for diagnostic
914      routines (this specific value is  not  counted  on  by  the  actual
915      allocation and release functions). */
916   len -= sizeof(bhead_t);
917   b->bh.bb.bsize = (bufsize)len;
918   /* Set the owner of this buffer */
919   TCW_PTR(b->bh.bb.bthr,
920           (kmp_info_t *)((kmp_uintptr_t)th |
921                          1)); // mark the buffer as allocated address
922 
923   /* Chain the new block to the free list. */
924   __kmp_bget_insert_into_freelist(thr, b);
925 
926 #ifdef FreeWipe
927   (void)memset(((char *)b) + sizeof(bfhead_t), 0x55,
928                (size_t)(len - sizeof(bfhead_t)));
929 #endif
930   bn = BH(((char *)b) + len);
931   bn->bb.prevfree = (bufsize)len;
932   /* Definition of ESent assumes two's complement! */
933   KMP_DEBUG_ASSERT((~0) == -1 && (bn != 0));
934 
935   bn->bb.bsize = ESent;
936 }
937 
938 /*  BFREED  --  Dump the free lists for this thread. */
939 static void bfreed(kmp_info_t *th) {
940   int bin = 0, count = 0;
941   int gtid = __kmp_gtid_from_thread(th);
942   thr_data_t *thr = get_thr_data(th);
943 
944 #if BufStats
945   __kmp_printf_no_lock("__kmp_printpool: T#%d total=%" KMP_UINT64_SPEC
946                        " get=%" KMP_INT64_SPEC " rel=%" KMP_INT64_SPEC
947                        " pblk=%" KMP_INT64_SPEC " pget=%" KMP_INT64_SPEC
948                        " prel=%" KMP_INT64_SPEC " dget=%" KMP_INT64_SPEC
949                        " drel=%" KMP_INT64_SPEC "\n",
950                        gtid, (kmp_uint64)thr->totalloc, (kmp_int64)thr->numget,
951                        (kmp_int64)thr->numrel, (kmp_int64)thr->numpblk,
952                        (kmp_int64)thr->numpget, (kmp_int64)thr->numprel,
953                        (kmp_int64)thr->numdget, (kmp_int64)thr->numdrel);
954 #endif
955 
956   for (bin = 0; bin < MAX_BGET_BINS; ++bin) {
957     bfhead_t *b;
958 
959     for (b = thr->freelist[bin].ql.flink; b != &thr->freelist[bin];
960          b = b->ql.flink) {
961       bufsize bs = b->bh.bb.bsize;
962 
963       KMP_DEBUG_ASSERT(b->ql.blink->ql.flink == b);
964       KMP_DEBUG_ASSERT(b->ql.flink->ql.blink == b);
965       KMP_DEBUG_ASSERT(bs > 0);
966 
967       count += 1;
968 
969       __kmp_printf_no_lock(
970           "__kmp_printpool: T#%d Free block: 0x%p size %6ld bytes.\n", gtid, b,
971           (long)bs);
972 #ifdef FreeWipe
973       {
974         char *lerr = ((char *)b) + sizeof(bfhead_t);
975         if ((bs > sizeof(bfhead_t)) &&
976             ((*lerr != 0x55) ||
977              (memcmp(lerr, lerr + 1, (size_t)(bs - (sizeof(bfhead_t) + 1))) !=
978               0))) {
979           __kmp_printf_no_lock("__kmp_printpool: T#%d     (Contents of above "
980                                "free block have been overstored.)\n",
981                                gtid);
982         }
983       }
984 #endif
985     }
986   }
987 
988   if (count == 0)
989     __kmp_printf_no_lock("__kmp_printpool: T#%d No free blocks\n", gtid);
990 }
991 
992 void __kmp_initialize_bget(kmp_info_t *th) {
993   KMP_DEBUG_ASSERT(SizeQuant >= sizeof(void *) && (th != 0));
994 
995   set_thr_data(th);
996 
997   bectl(th, (bget_compact_t)0, (bget_acquire_t)malloc, (bget_release_t)free,
998         (bufsize)__kmp_malloc_pool_incr);
999 }
1000 
1001 void __kmp_finalize_bget(kmp_info_t *th) {
1002   thr_data_t *thr;
1003   bfhead_t *b;
1004 
1005   KMP_DEBUG_ASSERT(th != 0);
1006 
1007 #if BufStats
1008   thr = (thr_data_t *)th->th.th_local.bget_data;
1009   KMP_DEBUG_ASSERT(thr != NULL);
1010   b = thr->last_pool;
1011 
1012   /*  If a block-release function is defined, and this free buffer constitutes
1013       the entire block, release it. Note that pool_len is defined in such a way
1014       that the test will fail unless all pool blocks are the same size.  */
1015 
1016   // Deallocate the last pool if one exists because we no longer do it in brel()
1017   if (thr->relfcn != 0 && b != 0 && thr->numpblk != 0 &&
1018       b->bh.bb.bsize == (bufsize)(thr->pool_len - sizeof(bhead_t))) {
1019     KMP_DEBUG_ASSERT(b->bh.bb.prevfree == 0);
1020     KMP_DEBUG_ASSERT(BH((char *)b + b->bh.bb.bsize)->bb.bsize == ESent);
1021     KMP_DEBUG_ASSERT(BH((char *)b + b->bh.bb.bsize)->bb.prevfree ==
1022                      b->bh.bb.bsize);
1023 
1024     /*  Unlink the buffer from the free list  */
1025     __kmp_bget_remove_from_freelist(b);
1026 
1027     KE_TRACE(10, ("%%%%%% FREE( %p )\n", (void *)b));
1028 
1029     (*thr->relfcn)(b);
1030     thr->numprel++; /* Nr of expansion block releases */
1031     thr->numpblk--; /* Total number of blocks */
1032     KMP_DEBUG_ASSERT(thr->numpblk == thr->numpget - thr->numprel);
1033   }
1034 #endif /* BufStats */
1035 
1036   /* Deallocate bget_data */
1037   if (th->th.th_local.bget_data != NULL) {
1038     __kmp_free(th->th.th_local.bget_data);
1039     th->th.th_local.bget_data = NULL;
1040   }
1041 }
1042 
1043 void kmpc_set_poolsize(size_t size) {
1044   bectl(__kmp_get_thread(), (bget_compact_t)0, (bget_acquire_t)malloc,
1045         (bget_release_t)free, (bufsize)size);
1046 }
1047 
1048 size_t kmpc_get_poolsize(void) {
1049   thr_data_t *p;
1050 
1051   p = get_thr_data(__kmp_get_thread());
1052 
1053   return p->exp_incr;
1054 }
1055 
1056 void kmpc_set_poolmode(int mode) {
1057   thr_data_t *p;
1058 
1059   if (mode == bget_mode_fifo || mode == bget_mode_lifo ||
1060       mode == bget_mode_best) {
1061     p = get_thr_data(__kmp_get_thread());
1062     p->mode = (bget_mode_t)mode;
1063   }
1064 }
1065 
1066 int kmpc_get_poolmode(void) {
1067   thr_data_t *p;
1068 
1069   p = get_thr_data(__kmp_get_thread());
1070 
1071   return p->mode;
1072 }
1073 
1074 void kmpc_get_poolstat(size_t *maxmem, size_t *allmem) {
1075   kmp_info_t *th = __kmp_get_thread();
1076   bufsize a, b;
1077 
1078   __kmp_bget_dequeue(th); /* Release any queued buffers */
1079 
1080   bcheck(th, &a, &b);
1081 
1082   *maxmem = a;
1083   *allmem = b;
1084 }
1085 
1086 void kmpc_poolprint(void) {
1087   kmp_info_t *th = __kmp_get_thread();
1088 
1089   __kmp_bget_dequeue(th); /* Release any queued buffers */
1090 
1091   bfreed(th);
1092 }
1093 
1094 #endif // #if KMP_USE_BGET
1095 
1096 void *kmpc_malloc(size_t size) {
1097   void *ptr;
1098   ptr = bget(__kmp_entry_thread(), (bufsize)(size + sizeof(ptr)));
1099   if (ptr != NULL) {
1100     // save allocated pointer just before one returned to user
1101     *(void **)ptr = ptr;
1102     ptr = (void **)ptr + 1;
1103   }
1104   return ptr;
1105 }
1106 
1107 #define IS_POWER_OF_TWO(n) (((n) & ((n)-1)) == 0)
1108 
1109 void *kmpc_aligned_malloc(size_t size, size_t alignment) {
1110   void *ptr;
1111   void *ptr_allocated;
1112   KMP_DEBUG_ASSERT(alignment < 32 * 1024); // Alignment should not be too big
1113   if (!IS_POWER_OF_TWO(alignment)) {
1114     // AC: do we need to issue a warning here?
1115     errno = EINVAL;
1116     return NULL;
1117   }
1118   size = size + sizeof(void *) + alignment;
1119   ptr_allocated = bget(__kmp_entry_thread(), (bufsize)size);
1120   if (ptr_allocated != NULL) {
1121     // save allocated pointer just before one returned to user
1122     ptr = (void *)(((kmp_uintptr_t)ptr_allocated + sizeof(void *) + alignment) &
1123                    ~(alignment - 1));
1124     *((void **)ptr - 1) = ptr_allocated;
1125   } else {
1126     ptr = NULL;
1127   }
1128   return ptr;
1129 }
1130 
1131 void *kmpc_calloc(size_t nelem, size_t elsize) {
1132   void *ptr;
1133   ptr = bgetz(__kmp_entry_thread(), (bufsize)(nelem * elsize + sizeof(ptr)));
1134   if (ptr != NULL) {
1135     // save allocated pointer just before one returned to user
1136     *(void **)ptr = ptr;
1137     ptr = (void **)ptr + 1;
1138   }
1139   return ptr;
1140 }
1141 
1142 void *kmpc_realloc(void *ptr, size_t size) {
1143   void *result = NULL;
1144   if (ptr == NULL) {
1145     // If pointer is NULL, realloc behaves like malloc.
1146     result = bget(__kmp_entry_thread(), (bufsize)(size + sizeof(ptr)));
1147     // save allocated pointer just before one returned to user
1148     if (result != NULL) {
1149       *(void **)result = result;
1150       result = (void **)result + 1;
1151     }
1152   } else if (size == 0) {
1153     // If size is 0, realloc behaves like free.
1154     // The thread must be registered by the call to kmpc_malloc() or
1155     // kmpc_calloc() before.
1156     // So it should be safe to call __kmp_get_thread(), not
1157     // __kmp_entry_thread().
1158     KMP_ASSERT(*((void **)ptr - 1));
1159     brel(__kmp_get_thread(), *((void **)ptr - 1));
1160   } else {
1161     result = bgetr(__kmp_entry_thread(), *((void **)ptr - 1),
1162                    (bufsize)(size + sizeof(ptr)));
1163     if (result != NULL) {
1164       *(void **)result = result;
1165       result = (void **)result + 1;
1166     }
1167   }
1168   return result;
1169 }
1170 
1171 // NOTE: the library must have already been initialized by a previous allocate
1172 void kmpc_free(void *ptr) {
1173   if (!__kmp_init_serial) {
1174     return;
1175   }
1176   if (ptr != NULL) {
1177     kmp_info_t *th = __kmp_get_thread();
1178     __kmp_bget_dequeue(th); /* Release any queued buffers */
1179     // extract allocated pointer and free it
1180     KMP_ASSERT(*((void **)ptr - 1));
1181     brel(th, *((void **)ptr - 1));
1182   }
1183 }
1184 
1185 void *___kmp_thread_malloc(kmp_info_t *th, size_t size KMP_SRC_LOC_DECL) {
1186   void *ptr;
1187   KE_TRACE(30, ("-> __kmp_thread_malloc( %p, %d ) called from %s:%d\n", th,
1188                 (int)size KMP_SRC_LOC_PARM));
1189   ptr = bget(th, (bufsize)size);
1190   KE_TRACE(30, ("<- __kmp_thread_malloc() returns %p\n", ptr));
1191   return ptr;
1192 }
1193 
1194 void *___kmp_thread_calloc(kmp_info_t *th, size_t nelem,
1195                            size_t elsize KMP_SRC_LOC_DECL) {
1196   void *ptr;
1197   KE_TRACE(30, ("-> __kmp_thread_calloc( %p, %d, %d ) called from %s:%d\n", th,
1198                 (int)nelem, (int)elsize KMP_SRC_LOC_PARM));
1199   ptr = bgetz(th, (bufsize)(nelem * elsize));
1200   KE_TRACE(30, ("<- __kmp_thread_calloc() returns %p\n", ptr));
1201   return ptr;
1202 }
1203 
1204 void *___kmp_thread_realloc(kmp_info_t *th, void *ptr,
1205                             size_t size KMP_SRC_LOC_DECL) {
1206   KE_TRACE(30, ("-> __kmp_thread_realloc( %p, %p, %d ) called from %s:%d\n", th,
1207                 ptr, (int)size KMP_SRC_LOC_PARM));
1208   ptr = bgetr(th, ptr, (bufsize)size);
1209   KE_TRACE(30, ("<- __kmp_thread_realloc() returns %p\n", ptr));
1210   return ptr;
1211 }
1212 
1213 void ___kmp_thread_free(kmp_info_t *th, void *ptr KMP_SRC_LOC_DECL) {
1214   KE_TRACE(30, ("-> __kmp_thread_free( %p, %p ) called from %s:%d\n", th,
1215                 ptr KMP_SRC_LOC_PARM));
1216   if (ptr != NULL) {
1217     __kmp_bget_dequeue(th); /* Release any queued buffers */
1218     brel(th, ptr);
1219   }
1220   KE_TRACE(30, ("<- __kmp_thread_free()\n"));
1221 }
1222 
1223 /* OMP 5.0 Memory Management support */
1224 static const char *kmp_mk_lib_name;
1225 static void *h_memkind;
1226 /* memkind experimental API: */
1227 // memkind_alloc
1228 static void *(*kmp_mk_alloc)(void *k, size_t sz);
1229 // memkind_free
1230 static void (*kmp_mk_free)(void *kind, void *ptr);
1231 // memkind_check_available
1232 static int (*kmp_mk_check)(void *kind);
1233 // kinds we are going to use
1234 static void **mk_default;
1235 static void **mk_interleave;
1236 static void **mk_hbw;
1237 static void **mk_hbw_interleave;
1238 static void **mk_hbw_preferred;
1239 static void **mk_hugetlb;
1240 static void **mk_hbw_hugetlb;
1241 static void **mk_hbw_preferred_hugetlb;
1242 static void **mk_dax_kmem;
1243 static void **mk_dax_kmem_all;
1244 static void **mk_dax_kmem_preferred;
1245 
1246 #if KMP_OS_UNIX && KMP_DYNAMIC_LIB
1247 static inline void chk_kind(void ***pkind) {
1248   KMP_DEBUG_ASSERT(pkind);
1249   if (*pkind) // symbol found
1250     if (kmp_mk_check(**pkind)) // kind not available or error
1251       *pkind = NULL;
1252 }
1253 #endif
1254 
1255 void __kmp_init_memkind() {
1256 // as of 2018-07-31 memkind does not support Windows*, exclude it for now
1257 #if KMP_OS_UNIX && KMP_DYNAMIC_LIB
1258   // use of statically linked memkind is problematic, as it depends on libnuma
1259   kmp_mk_lib_name = "libmemkind.so";
1260   h_memkind = dlopen(kmp_mk_lib_name, RTLD_LAZY);
1261   if (h_memkind) {
1262     kmp_mk_check = (int (*)(void *))dlsym(h_memkind, "memkind_check_available");
1263     kmp_mk_alloc =
1264         (void *(*)(void *, size_t))dlsym(h_memkind, "memkind_malloc");
1265     kmp_mk_free = (void (*)(void *, void *))dlsym(h_memkind, "memkind_free");
1266     mk_default = (void **)dlsym(h_memkind, "MEMKIND_DEFAULT");
1267     if (kmp_mk_check && kmp_mk_alloc && kmp_mk_free && mk_default &&
1268         !kmp_mk_check(*mk_default)) {
1269       __kmp_memkind_available = 1;
1270       mk_interleave = (void **)dlsym(h_memkind, "MEMKIND_INTERLEAVE");
1271       chk_kind(&mk_interleave);
1272       mk_hbw = (void **)dlsym(h_memkind, "MEMKIND_HBW");
1273       chk_kind(&mk_hbw);
1274       mk_hbw_interleave = (void **)dlsym(h_memkind, "MEMKIND_HBW_INTERLEAVE");
1275       chk_kind(&mk_hbw_interleave);
1276       mk_hbw_preferred = (void **)dlsym(h_memkind, "MEMKIND_HBW_PREFERRED");
1277       chk_kind(&mk_hbw_preferred);
1278       mk_hugetlb = (void **)dlsym(h_memkind, "MEMKIND_HUGETLB");
1279       chk_kind(&mk_hugetlb);
1280       mk_hbw_hugetlb = (void **)dlsym(h_memkind, "MEMKIND_HBW_HUGETLB");
1281       chk_kind(&mk_hbw_hugetlb);
1282       mk_hbw_preferred_hugetlb =
1283           (void **)dlsym(h_memkind, "MEMKIND_HBW_PREFERRED_HUGETLB");
1284       chk_kind(&mk_hbw_preferred_hugetlb);
1285       mk_dax_kmem = (void **)dlsym(h_memkind, "MEMKIND_DAX_KMEM");
1286       chk_kind(&mk_dax_kmem);
1287       mk_dax_kmem_all = (void **)dlsym(h_memkind, "MEMKIND_DAX_KMEM_ALL");
1288       chk_kind(&mk_dax_kmem_all);
1289       mk_dax_kmem_preferred =
1290           (void **)dlsym(h_memkind, "MEMKIND_DAX_KMEM_PREFERRED");
1291       chk_kind(&mk_dax_kmem_preferred);
1292       KE_TRACE(25, ("__kmp_init_memkind: memkind library initialized\n"));
1293       return; // success
1294     }
1295     dlclose(h_memkind); // failure
1296   }
1297 #else // !(KMP_OS_UNIX && KMP_DYNAMIC_LIB)
1298   kmp_mk_lib_name = "";
1299 #endif // !(KMP_OS_UNIX && KMP_DYNAMIC_LIB)
1300   h_memkind = NULL;
1301   kmp_mk_check = NULL;
1302   kmp_mk_alloc = NULL;
1303   kmp_mk_free = NULL;
1304   mk_default = NULL;
1305   mk_interleave = NULL;
1306   mk_hbw = NULL;
1307   mk_hbw_interleave = NULL;
1308   mk_hbw_preferred = NULL;
1309   mk_hugetlb = NULL;
1310   mk_hbw_hugetlb = NULL;
1311   mk_hbw_preferred_hugetlb = NULL;
1312   mk_dax_kmem = NULL;
1313   mk_dax_kmem_all = NULL;
1314   mk_dax_kmem_preferred = NULL;
1315 }
1316 
1317 void __kmp_fini_memkind() {
1318 #if KMP_OS_UNIX && KMP_DYNAMIC_LIB
1319   if (__kmp_memkind_available)
1320     KE_TRACE(25, ("__kmp_fini_memkind: finalize memkind library\n"));
1321   if (h_memkind) {
1322     dlclose(h_memkind);
1323     h_memkind = NULL;
1324   }
1325   kmp_mk_check = NULL;
1326   kmp_mk_alloc = NULL;
1327   kmp_mk_free = NULL;
1328   mk_default = NULL;
1329   mk_interleave = NULL;
1330   mk_hbw = NULL;
1331   mk_hbw_interleave = NULL;
1332   mk_hbw_preferred = NULL;
1333   mk_hugetlb = NULL;
1334   mk_hbw_hugetlb = NULL;
1335   mk_hbw_preferred_hugetlb = NULL;
1336   mk_dax_kmem = NULL;
1337   mk_dax_kmem_all = NULL;
1338   mk_dax_kmem_preferred = NULL;
1339 #endif
1340 }
1341 
1342 omp_allocator_handle_t __kmpc_init_allocator(int gtid, omp_memspace_handle_t ms,
1343                                              int ntraits,
1344                                              omp_alloctrait_t traits[]) {
1345   // OpenMP 5.0 only allows predefined memspaces
1346   KMP_DEBUG_ASSERT(ms == omp_default_mem_space || ms == omp_low_lat_mem_space ||
1347                    ms == omp_large_cap_mem_space || ms == omp_const_mem_space ||
1348                    ms == omp_high_bw_mem_space);
1349   kmp_allocator_t *al;
1350   int i;
1351   al = (kmp_allocator_t *)__kmp_allocate(sizeof(kmp_allocator_t)); // zeroed
1352   al->memspace = ms; // not used currently
1353   for (i = 0; i < ntraits; ++i) {
1354     switch (traits[i].key) {
1355     case omp_atk_sync_hint:
1356     case omp_atk_access:
1357     case omp_atk_pinned:
1358       break;
1359     case omp_atk_alignment:
1360       __kmp_type_convert(traits[i].value, &(al->alignment));
1361       KMP_ASSERT(IS_POWER_OF_TWO(al->alignment));
1362       break;
1363     case omp_atk_pool_size:
1364       al->pool_size = traits[i].value;
1365       break;
1366     case omp_atk_fallback:
1367       al->fb = (omp_alloctrait_value_t)traits[i].value;
1368       KMP_DEBUG_ASSERT(
1369           al->fb == omp_atv_default_mem_fb || al->fb == omp_atv_null_fb ||
1370           al->fb == omp_atv_abort_fb || al->fb == omp_atv_allocator_fb);
1371       break;
1372     case omp_atk_fb_data:
1373       al->fb_data = RCAST(kmp_allocator_t *, traits[i].value);
1374       break;
1375     case omp_atk_partition:
1376       al->memkind = RCAST(void **, traits[i].value);
1377       break;
1378     default:
1379       KMP_ASSERT2(0, "Unexpected allocator trait");
1380     }
1381   }
1382   if (al->fb == 0) {
1383     // set default allocator
1384     al->fb = omp_atv_default_mem_fb;
1385     al->fb_data = (kmp_allocator_t *)omp_default_mem_alloc;
1386   } else if (al->fb == omp_atv_allocator_fb) {
1387     KMP_ASSERT(al->fb_data != NULL);
1388   } else if (al->fb == omp_atv_default_mem_fb) {
1389     al->fb_data = (kmp_allocator_t *)omp_default_mem_alloc;
1390   }
1391   if (__kmp_memkind_available) {
1392     // Let's use memkind library if available
1393     if (ms == omp_high_bw_mem_space) {
1394       if (al->memkind == (void *)omp_atv_interleaved && mk_hbw_interleave) {
1395         al->memkind = mk_hbw_interleave;
1396       } else if (mk_hbw_preferred) {
1397         // AC: do not try to use MEMKIND_HBW for now, because memkind library
1398         // cannot reliably detect exhaustion of HBW memory.
1399         // It could be possible using hbw_verify_memory_region() but memkind
1400         // manual says: "Using this function in production code may result in
1401         // serious performance penalty".
1402         al->memkind = mk_hbw_preferred;
1403       } else {
1404         // HBW is requested but not available --> return NULL allocator
1405         __kmp_free(al);
1406         return omp_null_allocator;
1407       }
1408     } else if (ms == omp_large_cap_mem_space) {
1409       if (mk_dax_kmem_all) {
1410         // All pmem nodes are visited
1411         al->memkind = mk_dax_kmem_all;
1412       } else if (mk_dax_kmem) {
1413         // Only closest pmem node is visited
1414         al->memkind = mk_dax_kmem;
1415       } else {
1416         __kmp_free(al);
1417         return omp_null_allocator;
1418       }
1419     } else {
1420       if (al->memkind == (void *)omp_atv_interleaved && mk_interleave) {
1421         al->memkind = mk_interleave;
1422       } else {
1423         al->memkind = mk_default;
1424       }
1425     }
1426   } else {
1427     if (ms == omp_high_bw_mem_space) {
1428       // cannot detect HBW memory presence without memkind library
1429       __kmp_free(al);
1430       return omp_null_allocator;
1431     }
1432   }
1433   return (omp_allocator_handle_t)al;
1434 }
1435 
1436 void __kmpc_destroy_allocator(int gtid, omp_allocator_handle_t allocator) {
1437   if (allocator > kmp_max_mem_alloc)
1438     __kmp_free(allocator);
1439 }
1440 
1441 void __kmpc_set_default_allocator(int gtid, omp_allocator_handle_t allocator) {
1442   if (allocator == omp_null_allocator)
1443     allocator = omp_default_mem_alloc;
1444   __kmp_threads[gtid]->th.th_def_allocator = allocator;
1445 }
1446 
1447 omp_allocator_handle_t __kmpc_get_default_allocator(int gtid) {
1448   return __kmp_threads[gtid]->th.th_def_allocator;
1449 }
1450 
1451 typedef struct kmp_mem_desc { // Memory block descriptor
1452   void *ptr_alloc; // Pointer returned by allocator
1453   size_t size_a; // Size of allocated memory block (initial+descriptor+align)
1454   size_t size_orig; // Original size requested
1455   void *ptr_align; // Pointer to aligned memory, returned
1456   kmp_allocator_t *allocator; // allocator
1457 } kmp_mem_desc_t;
1458 static int alignment = sizeof(void *); // let's align to pointer size
1459 
1460 void *__kmpc_alloc(int gtid, size_t size, omp_allocator_handle_t allocator) {
1461   void *ptr = NULL;
1462   kmp_allocator_t *al;
1463   KMP_DEBUG_ASSERT(__kmp_init_serial);
1464 
1465   if (size == 0)
1466     return NULL;
1467 
1468   if (allocator == omp_null_allocator)
1469     allocator = __kmp_threads[gtid]->th.th_def_allocator;
1470 
1471   KE_TRACE(25, ("__kmpc_alloc: T#%d (%d, %p)\n", gtid, (int)size, allocator));
1472   al = RCAST(kmp_allocator_t *, CCAST(omp_allocator_handle_t, allocator));
1473 
1474   int sz_desc = sizeof(kmp_mem_desc_t);
1475   kmp_mem_desc_t desc;
1476   kmp_uintptr_t addr; // address returned by allocator
1477   kmp_uintptr_t addr_align; // address to return to caller
1478   kmp_uintptr_t addr_descr; // address of memory block descriptor
1479   int align = alignment; // default alignment
1480   if (allocator > kmp_max_mem_alloc && al->alignment > 0) {
1481     align = al->alignment; // alignment requested by user
1482   }
1483   desc.size_orig = size;
1484   desc.size_a = size + sz_desc + align;
1485 
1486   if (__kmp_memkind_available) {
1487     if (allocator < kmp_max_mem_alloc) {
1488       // pre-defined allocator
1489       if (allocator == omp_high_bw_mem_alloc && mk_hbw_preferred) {
1490         ptr = kmp_mk_alloc(*mk_hbw_preferred, desc.size_a);
1491       } else if (allocator == omp_large_cap_mem_alloc && mk_dax_kmem_all) {
1492         ptr = kmp_mk_alloc(*mk_dax_kmem_all, desc.size_a);
1493       } else {
1494         ptr = kmp_mk_alloc(*mk_default, desc.size_a);
1495       }
1496     } else if (al->pool_size > 0) {
1497       // custom allocator with pool size requested
1498       kmp_uint64 used =
1499           KMP_TEST_THEN_ADD64((kmp_int64 *)&al->pool_used, desc.size_a);
1500       if (used + desc.size_a > al->pool_size) {
1501         // not enough space, need to go fallback path
1502         KMP_TEST_THEN_ADD64((kmp_int64 *)&al->pool_used, -desc.size_a);
1503         if (al->fb == omp_atv_default_mem_fb) {
1504           al = (kmp_allocator_t *)omp_default_mem_alloc;
1505           ptr = kmp_mk_alloc(*mk_default, desc.size_a);
1506         } else if (al->fb == omp_atv_abort_fb) {
1507           KMP_ASSERT(0); // abort fallback requested
1508         } else if (al->fb == omp_atv_allocator_fb) {
1509           KMP_ASSERT(al != al->fb_data);
1510           al = al->fb_data;
1511           return __kmpc_alloc(gtid, size, (omp_allocator_handle_t)al);
1512         } // else ptr == NULL;
1513       } else {
1514         // pool has enough space
1515         ptr = kmp_mk_alloc(*al->memkind, desc.size_a);
1516         if (ptr == NULL) {
1517           if (al->fb == omp_atv_default_mem_fb) {
1518             al = (kmp_allocator_t *)omp_default_mem_alloc;
1519             ptr = kmp_mk_alloc(*mk_default, desc.size_a);
1520           } else if (al->fb == omp_atv_abort_fb) {
1521             KMP_ASSERT(0); // abort fallback requested
1522           } else if (al->fb == omp_atv_allocator_fb) {
1523             KMP_ASSERT(al != al->fb_data);
1524             al = al->fb_data;
1525             return __kmpc_alloc(gtid, size, (omp_allocator_handle_t)al);
1526           }
1527         }
1528       }
1529     } else {
1530       // custom allocator, pool size not requested
1531       ptr = kmp_mk_alloc(*al->memkind, desc.size_a);
1532       if (ptr == NULL) {
1533         if (al->fb == omp_atv_default_mem_fb) {
1534           al = (kmp_allocator_t *)omp_default_mem_alloc;
1535           ptr = kmp_mk_alloc(*mk_default, desc.size_a);
1536         } else if (al->fb == omp_atv_abort_fb) {
1537           KMP_ASSERT(0); // abort fallback requested
1538         } else if (al->fb == omp_atv_allocator_fb) {
1539           KMP_ASSERT(al != al->fb_data);
1540           al = al->fb_data;
1541           return __kmpc_alloc(gtid, size, (omp_allocator_handle_t)al);
1542         }
1543       }
1544     }
1545   } else if (allocator < kmp_max_mem_alloc) {
1546     // pre-defined allocator
1547     if (allocator == omp_high_bw_mem_alloc) {
1548       // ptr = NULL;
1549     } else if (allocator == omp_large_cap_mem_alloc) {
1550       // warnings?
1551     } else {
1552       ptr = __kmp_thread_malloc(__kmp_thread_from_gtid(gtid), desc.size_a);
1553     }
1554   } else if (al->pool_size > 0) {
1555     // custom allocator with pool size requested
1556     kmp_uint64 used =
1557         KMP_TEST_THEN_ADD64((kmp_int64 *)&al->pool_used, desc.size_a);
1558     if (used + desc.size_a > al->pool_size) {
1559       // not enough space, need to go fallback path
1560       KMP_TEST_THEN_ADD64((kmp_int64 *)&al->pool_used, -desc.size_a);
1561       if (al->fb == omp_atv_default_mem_fb) {
1562         al = (kmp_allocator_t *)omp_default_mem_alloc;
1563         ptr = __kmp_thread_malloc(__kmp_thread_from_gtid(gtid), desc.size_a);
1564       } else if (al->fb == omp_atv_abort_fb) {
1565         KMP_ASSERT(0); // abort fallback requested
1566       } else if (al->fb == omp_atv_allocator_fb) {
1567         KMP_ASSERT(al != al->fb_data);
1568         al = al->fb_data;
1569         return __kmpc_alloc(gtid, size, (omp_allocator_handle_t)al);
1570       } // else ptr == NULL;
1571     } else {
1572       // pool has enough space
1573       ptr = __kmp_thread_malloc(__kmp_thread_from_gtid(gtid), desc.size_a);
1574       if (ptr == NULL && al->fb == omp_atv_abort_fb) {
1575         KMP_ASSERT(0); // abort fallback requested
1576       } // no sense to look for another fallback because of same internal alloc
1577     }
1578   } else {
1579     // custom allocator, pool size not requested
1580     ptr = __kmp_thread_malloc(__kmp_thread_from_gtid(gtid), desc.size_a);
1581     if (ptr == NULL && al->fb == omp_atv_abort_fb) {
1582       KMP_ASSERT(0); // abort fallback requested
1583     } // no sense to look for another fallback because of same internal alloc
1584   }
1585   KE_TRACE(10, ("__kmpc_alloc: T#%d %p=alloc(%d)\n", gtid, ptr, desc.size_a));
1586   if (ptr == NULL)
1587     return NULL;
1588 
1589   addr = (kmp_uintptr_t)ptr;
1590   addr_align = (addr + sz_desc + align - 1) & ~(align - 1);
1591   addr_descr = addr_align - sz_desc;
1592 
1593   desc.ptr_alloc = ptr;
1594   desc.ptr_align = (void *)addr_align;
1595   desc.allocator = al;
1596   *((kmp_mem_desc_t *)addr_descr) = desc; // save descriptor contents
1597   KMP_MB();
1598 
1599   KE_TRACE(25, ("__kmpc_alloc returns %p, T#%d\n", desc.ptr_align, gtid));
1600   return desc.ptr_align;
1601 }
1602 
1603 void *__kmpc_calloc(int gtid, size_t nmemb, size_t size,
1604                     omp_allocator_handle_t allocator) {
1605   void *ptr = NULL;
1606   kmp_allocator_t *al;
1607   KMP_DEBUG_ASSERT(__kmp_init_serial);
1608 
1609   if (allocator == omp_null_allocator)
1610     allocator = __kmp_threads[gtid]->th.th_def_allocator;
1611 
1612   KE_TRACE(25, ("__kmpc_calloc: T#%d (%d, %d, %p)\n", gtid, (int)nmemb,
1613                 (int)size, allocator));
1614 
1615   al = RCAST(kmp_allocator_t *, CCAST(omp_allocator_handle_t, allocator));
1616 
1617   if (nmemb == 0 || size == 0)
1618     return ptr;
1619 
1620   if ((SIZE_MAX - sizeof(kmp_mem_desc_t)) / size < nmemb) {
1621     if (al->fb == omp_atv_abort_fb) {
1622       KMP_ASSERT(0);
1623     }
1624     return ptr;
1625   }
1626 
1627   ptr = __kmpc_alloc(gtid, nmemb * size, allocator);
1628 
1629   if (ptr) {
1630     memset(ptr, 0x00, nmemb * size);
1631   }
1632   KE_TRACE(25, ("__kmpc_calloc returns %p, T#%d\n", ptr, gtid));
1633   return ptr;
1634 }
1635 
1636 void *__kmpc_realloc(int gtid, void *ptr, size_t size,
1637                      omp_allocator_handle_t allocator,
1638                      omp_allocator_handle_t free_allocator) {
1639   void *nptr = NULL;
1640   KMP_DEBUG_ASSERT(__kmp_init_serial);
1641 
1642   if (size == 0) {
1643     if (ptr != NULL)
1644       __kmpc_free(gtid, ptr, free_allocator);
1645     return nptr;
1646   }
1647 
1648   KE_TRACE(25, ("__kmpc_realloc: T#%d (%p, %d, %p, %p)\n", gtid, ptr, (int)size,
1649                 allocator, free_allocator));
1650 
1651   nptr = __kmpc_alloc(gtid, size, allocator);
1652 
1653   if (nptr != NULL && ptr != NULL) {
1654     kmp_mem_desc_t desc;
1655     kmp_uintptr_t addr_align; // address to return to caller
1656     kmp_uintptr_t addr_descr; // address of memory block descriptor
1657 
1658     addr_align = (kmp_uintptr_t)ptr;
1659     addr_descr = addr_align - sizeof(kmp_mem_desc_t);
1660     desc = *((kmp_mem_desc_t *)addr_descr); // read descriptor
1661 
1662     KMP_DEBUG_ASSERT(desc.ptr_align == ptr);
1663     KMP_DEBUG_ASSERT(desc.size_orig > 0);
1664     KMP_DEBUG_ASSERT(desc.size_orig < desc.size_a);
1665     KMP_MEMCPY((char *)nptr, (char *)ptr,
1666                (size_t)((size < desc.size_orig) ? size : desc.size_orig));
1667   }
1668 
1669   if (nptr != NULL) {
1670     __kmpc_free(gtid, ptr, free_allocator);
1671   }
1672 
1673   KE_TRACE(25, ("__kmpc_realloc returns %p, T#%d\n", nptr, gtid));
1674   return nptr;
1675 }
1676 
1677 void __kmpc_free(int gtid, void *ptr, const omp_allocator_handle_t allocator) {
1678   KE_TRACE(25, ("__kmpc_free: T#%d free(%p,%p)\n", gtid, ptr, allocator));
1679   if (ptr == NULL)
1680     return;
1681 
1682   kmp_allocator_t *al;
1683   omp_allocator_handle_t oal;
1684   al = RCAST(kmp_allocator_t *, CCAST(omp_allocator_handle_t, allocator));
1685   kmp_mem_desc_t desc;
1686   kmp_uintptr_t addr_align; // address to return to caller
1687   kmp_uintptr_t addr_descr; // address of memory block descriptor
1688 
1689   addr_align = (kmp_uintptr_t)ptr;
1690   addr_descr = addr_align - sizeof(kmp_mem_desc_t);
1691   desc = *((kmp_mem_desc_t *)addr_descr); // read descriptor
1692 
1693   KMP_DEBUG_ASSERT(desc.ptr_align == ptr);
1694   if (allocator) {
1695     KMP_DEBUG_ASSERT(desc.allocator == al || desc.allocator == al->fb_data);
1696   }
1697   al = desc.allocator;
1698   oal = (omp_allocator_handle_t)al; // cast to void* for comparisons
1699   KMP_DEBUG_ASSERT(al);
1700 
1701   if (__kmp_memkind_available) {
1702     if (oal < kmp_max_mem_alloc) {
1703       // pre-defined allocator
1704       if (oal == omp_high_bw_mem_alloc && mk_hbw_preferred) {
1705         kmp_mk_free(*mk_hbw_preferred, desc.ptr_alloc);
1706       } else if (oal == omp_large_cap_mem_alloc && mk_dax_kmem_all) {
1707         kmp_mk_free(*mk_dax_kmem_all, desc.ptr_alloc);
1708       } else {
1709         kmp_mk_free(*mk_default, desc.ptr_alloc);
1710       }
1711     } else {
1712       if (al->pool_size > 0) { // custom allocator with pool size requested
1713         kmp_uint64 used =
1714             KMP_TEST_THEN_ADD64((kmp_int64 *)&al->pool_used, -desc.size_a);
1715         (void)used; // to suppress compiler warning
1716         KMP_DEBUG_ASSERT(used >= desc.size_a);
1717       }
1718       kmp_mk_free(*al->memkind, desc.ptr_alloc);
1719     }
1720   } else {
1721     if (oal > kmp_max_mem_alloc && al->pool_size > 0) {
1722       kmp_uint64 used =
1723           KMP_TEST_THEN_ADD64((kmp_int64 *)&al->pool_used, -desc.size_a);
1724       (void)used; // to suppress compiler warning
1725       KMP_DEBUG_ASSERT(used >= desc.size_a);
1726     }
1727     __kmp_thread_free(__kmp_thread_from_gtid(gtid), desc.ptr_alloc);
1728   }
1729   KE_TRACE(10, ("__kmpc_free: T#%d freed %p (%p)\n", gtid, desc.ptr_alloc,
1730                 allocator));
1731 }
1732 
1733 /* If LEAK_MEMORY is defined, __kmp_free() will *not* free memory. It causes
1734    memory leaks, but it may be useful for debugging memory corruptions, used
1735    freed pointers, etc. */
1736 /* #define LEAK_MEMORY */
1737 struct kmp_mem_descr { // Memory block descriptor.
1738   void *ptr_allocated; // Pointer returned by malloc(), subject for free().
1739   size_t size_allocated; // Size of allocated memory block.
1740   void *ptr_aligned; // Pointer to aligned memory, to be used by client code.
1741   size_t size_aligned; // Size of aligned memory block.
1742 };
1743 typedef struct kmp_mem_descr kmp_mem_descr_t;
1744 
1745 /* Allocate memory on requested boundary, fill allocated memory with 0x00.
1746    NULL is NEVER returned, __kmp_abort() is called in case of memory allocation
1747    error. Must use __kmp_free when freeing memory allocated by this routine! */
1748 static void *___kmp_allocate_align(size_t size,
1749                                    size_t alignment KMP_SRC_LOC_DECL) {
1750   /* __kmp_allocate() allocates (by call to malloc()) bigger memory block than
1751      requested to return properly aligned pointer. Original pointer returned
1752      by malloc() and size of allocated block is saved in descriptor just
1753      before the aligned pointer. This information used by __kmp_free() -- it
1754      has to pass to free() original pointer, not aligned one.
1755 
1756           +---------+------------+-----------------------------------+---------+
1757           | padding | descriptor |           aligned block           | padding |
1758           +---------+------------+-----------------------------------+---------+
1759           ^                      ^
1760           |                      |
1761           |                      +- Aligned pointer returned to caller
1762           +- Pointer returned by malloc()
1763 
1764       Aligned block is filled with zeros, paddings are filled with 0xEF. */
1765 
1766   kmp_mem_descr_t descr;
1767   kmp_uintptr_t addr_allocated; // Address returned by malloc().
1768   kmp_uintptr_t addr_aligned; // Aligned address to return to caller.
1769   kmp_uintptr_t addr_descr; // Address of memory block descriptor.
1770 
1771   KE_TRACE(25, ("-> ___kmp_allocate_align( %d, %d ) called from %s:%d\n",
1772                 (int)size, (int)alignment KMP_SRC_LOC_PARM));
1773 
1774   KMP_DEBUG_ASSERT(alignment < 32 * 1024); // Alignment should not be too
1775   KMP_DEBUG_ASSERT(sizeof(void *) <= sizeof(kmp_uintptr_t));
1776   // Make sure kmp_uintptr_t is enough to store addresses.
1777 
1778   descr.size_aligned = size;
1779   descr.size_allocated =
1780       descr.size_aligned + sizeof(kmp_mem_descr_t) + alignment;
1781 
1782 #if KMP_DEBUG
1783   descr.ptr_allocated = _malloc_src_loc(descr.size_allocated, _file_, _line_);
1784 #else
1785   descr.ptr_allocated = malloc_src_loc(descr.size_allocated KMP_SRC_LOC_PARM);
1786 #endif
1787   KE_TRACE(10, ("   malloc( %d ) returned %p\n", (int)descr.size_allocated,
1788                 descr.ptr_allocated));
1789   if (descr.ptr_allocated == NULL) {
1790     KMP_FATAL(OutOfHeapMemory);
1791   }
1792 
1793   addr_allocated = (kmp_uintptr_t)descr.ptr_allocated;
1794   addr_aligned =
1795       (addr_allocated + sizeof(kmp_mem_descr_t) + alignment) & ~(alignment - 1);
1796   addr_descr = addr_aligned - sizeof(kmp_mem_descr_t);
1797 
1798   descr.ptr_aligned = (void *)addr_aligned;
1799 
1800   KE_TRACE(26, ("   ___kmp_allocate_align: "
1801                 "ptr_allocated=%p, size_allocated=%d, "
1802                 "ptr_aligned=%p, size_aligned=%d\n",
1803                 descr.ptr_allocated, (int)descr.size_allocated,
1804                 descr.ptr_aligned, (int)descr.size_aligned));
1805 
1806   KMP_DEBUG_ASSERT(addr_allocated <= addr_descr);
1807   KMP_DEBUG_ASSERT(addr_descr + sizeof(kmp_mem_descr_t) == addr_aligned);
1808   KMP_DEBUG_ASSERT(addr_aligned + descr.size_aligned <=
1809                    addr_allocated + descr.size_allocated);
1810   KMP_DEBUG_ASSERT(addr_aligned % alignment == 0);
1811 #ifdef KMP_DEBUG
1812   memset(descr.ptr_allocated, 0xEF, descr.size_allocated);
1813 // Fill allocated memory block with 0xEF.
1814 #endif
1815   memset(descr.ptr_aligned, 0x00, descr.size_aligned);
1816   // Fill the aligned memory block (which is intended for using by caller) with
1817   // 0x00. Do not
1818   // put this filling under KMP_DEBUG condition! Many callers expect zeroed
1819   // memory. (Padding
1820   // bytes remain filled with 0xEF in debugging library.)
1821   *((kmp_mem_descr_t *)addr_descr) = descr;
1822 
1823   KMP_MB();
1824 
1825   KE_TRACE(25, ("<- ___kmp_allocate_align() returns %p\n", descr.ptr_aligned));
1826   return descr.ptr_aligned;
1827 } // func ___kmp_allocate_align
1828 
1829 /* Allocate memory on cache line boundary, fill allocated memory with 0x00.
1830    Do not call this func directly! Use __kmp_allocate macro instead.
1831    NULL is NEVER returned, __kmp_abort() is called in case of memory allocation
1832    error. Must use __kmp_free when freeing memory allocated by this routine! */
1833 void *___kmp_allocate(size_t size KMP_SRC_LOC_DECL) {
1834   void *ptr;
1835   KE_TRACE(25, ("-> __kmp_allocate( %d ) called from %s:%d\n",
1836                 (int)size KMP_SRC_LOC_PARM));
1837   ptr = ___kmp_allocate_align(size, __kmp_align_alloc KMP_SRC_LOC_PARM);
1838   KE_TRACE(25, ("<- __kmp_allocate() returns %p\n", ptr));
1839   return ptr;
1840 } // func ___kmp_allocate
1841 
1842 /* Allocate memory on page boundary, fill allocated memory with 0x00.
1843    Does not call this func directly! Use __kmp_page_allocate macro instead.
1844    NULL is NEVER returned, __kmp_abort() is called in case of memory allocation
1845    error. Must use __kmp_free when freeing memory allocated by this routine! */
1846 void *___kmp_page_allocate(size_t size KMP_SRC_LOC_DECL) {
1847   int page_size = 8 * 1024;
1848   void *ptr;
1849 
1850   KE_TRACE(25, ("-> __kmp_page_allocate( %d ) called from %s:%d\n",
1851                 (int)size KMP_SRC_LOC_PARM));
1852   ptr = ___kmp_allocate_align(size, page_size KMP_SRC_LOC_PARM);
1853   KE_TRACE(25, ("<- __kmp_page_allocate( %d ) returns %p\n", (int)size, ptr));
1854   return ptr;
1855 } // ___kmp_page_allocate
1856 
1857 /* Free memory allocated by __kmp_allocate() and __kmp_page_allocate().
1858    In debug mode, fill the memory block with 0xEF before call to free(). */
1859 void ___kmp_free(void *ptr KMP_SRC_LOC_DECL) {
1860   kmp_mem_descr_t descr;
1861   kmp_uintptr_t addr_allocated; // Address returned by malloc().
1862   kmp_uintptr_t addr_aligned; // Aligned address passed by caller.
1863 
1864   KE_TRACE(25,
1865            ("-> __kmp_free( %p ) called from %s:%d\n", ptr KMP_SRC_LOC_PARM));
1866   KMP_ASSERT(ptr != NULL);
1867 
1868   descr = *(kmp_mem_descr_t *)((kmp_uintptr_t)ptr - sizeof(kmp_mem_descr_t));
1869 
1870   KE_TRACE(26, ("   __kmp_free:     "
1871                 "ptr_allocated=%p, size_allocated=%d, "
1872                 "ptr_aligned=%p, size_aligned=%d\n",
1873                 descr.ptr_allocated, (int)descr.size_allocated,
1874                 descr.ptr_aligned, (int)descr.size_aligned));
1875 
1876   addr_allocated = (kmp_uintptr_t)descr.ptr_allocated;
1877   addr_aligned = (kmp_uintptr_t)descr.ptr_aligned;
1878 
1879   KMP_DEBUG_ASSERT(addr_aligned % CACHE_LINE == 0);
1880   KMP_DEBUG_ASSERT(descr.ptr_aligned == ptr);
1881   KMP_DEBUG_ASSERT(addr_allocated + sizeof(kmp_mem_descr_t) <= addr_aligned);
1882   KMP_DEBUG_ASSERT(descr.size_aligned < descr.size_allocated);
1883   KMP_DEBUG_ASSERT(addr_aligned + descr.size_aligned <=
1884                    addr_allocated + descr.size_allocated);
1885 
1886 #ifdef KMP_DEBUG
1887   memset(descr.ptr_allocated, 0xEF, descr.size_allocated);
1888 // Fill memory block with 0xEF, it helps catch using freed memory.
1889 #endif
1890 
1891 #ifndef LEAK_MEMORY
1892   KE_TRACE(10, ("   free( %p )\n", descr.ptr_allocated));
1893 #ifdef KMP_DEBUG
1894   _free_src_loc(descr.ptr_allocated, _file_, _line_);
1895 #else
1896   free_src_loc(descr.ptr_allocated KMP_SRC_LOC_PARM);
1897 #endif
1898 #endif
1899   KMP_MB();
1900   KE_TRACE(25, ("<- __kmp_free() returns\n"));
1901 } // func ___kmp_free
1902 
1903 #if USE_FAST_MEMORY == 3
1904 // Allocate fast memory by first scanning the thread's free lists
1905 // If a chunk the right size exists, grab it off the free list.
1906 // Otherwise allocate normally using kmp_thread_malloc.
1907 
1908 // AC: How to choose the limit? Just get 16 for now...
1909 #define KMP_FREE_LIST_LIMIT 16
1910 
1911 // Always use 128 bytes for determining buckets for caching memory blocks
1912 #define DCACHE_LINE 128
1913 
1914 void *___kmp_fast_allocate(kmp_info_t *this_thr, size_t size KMP_SRC_LOC_DECL) {
1915   void *ptr;
1916   size_t num_lines, idx;
1917   int index;
1918   void *alloc_ptr;
1919   size_t alloc_size;
1920   kmp_mem_descr_t *descr;
1921 
1922   KE_TRACE(25, ("-> __kmp_fast_allocate( T#%d, %d ) called from %s:%d\n",
1923                 __kmp_gtid_from_thread(this_thr), (int)size KMP_SRC_LOC_PARM));
1924 
1925   num_lines = (size + DCACHE_LINE - 1) / DCACHE_LINE;
1926   idx = num_lines - 1;
1927   KMP_DEBUG_ASSERT(idx >= 0);
1928   if (idx < 2) {
1929     index = 0; // idx is [ 0, 1 ], use first free list
1930     num_lines = 2; // 1, 2 cache lines or less than cache line
1931   } else if ((idx >>= 2) == 0) {
1932     index = 1; // idx is [ 2, 3 ], use second free list
1933     num_lines = 4; // 3, 4 cache lines
1934   } else if ((idx >>= 2) == 0) {
1935     index = 2; // idx is [ 4, 15 ], use third free list
1936     num_lines = 16; // 5, 6, ..., 16 cache lines
1937   } else if ((idx >>= 2) == 0) {
1938     index = 3; // idx is [ 16, 63 ], use fourth free list
1939     num_lines = 64; // 17, 18, ..., 64 cache lines
1940   } else {
1941     goto alloc_call; // 65 or more cache lines ( > 8KB ), don't use free lists
1942   }
1943 
1944   ptr = this_thr->th.th_free_lists[index].th_free_list_self;
1945   if (ptr != NULL) {
1946     // pop the head of no-sync free list
1947     this_thr->th.th_free_lists[index].th_free_list_self = *((void **)ptr);
1948     KMP_DEBUG_ASSERT(
1949         this_thr ==
1950         ((kmp_mem_descr_t *)((kmp_uintptr_t)ptr - sizeof(kmp_mem_descr_t)))
1951             ->ptr_aligned);
1952     goto end;
1953   }
1954   ptr = TCR_SYNC_PTR(this_thr->th.th_free_lists[index].th_free_list_sync);
1955   if (ptr != NULL) {
1956     // no-sync free list is empty, use sync free list (filled in by other
1957     // threads only)
1958     // pop the head of the sync free list, push NULL instead
1959     while (!KMP_COMPARE_AND_STORE_PTR(
1960         &this_thr->th.th_free_lists[index].th_free_list_sync, ptr, nullptr)) {
1961       KMP_CPU_PAUSE();
1962       ptr = TCR_SYNC_PTR(this_thr->th.th_free_lists[index].th_free_list_sync);
1963     }
1964     // push the rest of chain into no-sync free list (can be NULL if there was
1965     // the only block)
1966     this_thr->th.th_free_lists[index].th_free_list_self = *((void **)ptr);
1967     KMP_DEBUG_ASSERT(
1968         this_thr ==
1969         ((kmp_mem_descr_t *)((kmp_uintptr_t)ptr - sizeof(kmp_mem_descr_t)))
1970             ->ptr_aligned);
1971     goto end;
1972   }
1973 
1974 alloc_call:
1975   // haven't found block in the free lists, thus allocate it
1976   size = num_lines * DCACHE_LINE;
1977 
1978   alloc_size = size + sizeof(kmp_mem_descr_t) + DCACHE_LINE;
1979   KE_TRACE(25, ("__kmp_fast_allocate: T#%d Calling __kmp_thread_malloc with "
1980                 "alloc_size %d\n",
1981                 __kmp_gtid_from_thread(this_thr), alloc_size));
1982   alloc_ptr = bget(this_thr, (bufsize)alloc_size);
1983 
1984   // align ptr to DCACHE_LINE
1985   ptr = (void *)((((kmp_uintptr_t)alloc_ptr) + sizeof(kmp_mem_descr_t) +
1986                   DCACHE_LINE) &
1987                  ~(DCACHE_LINE - 1));
1988   descr = (kmp_mem_descr_t *)(((kmp_uintptr_t)ptr) - sizeof(kmp_mem_descr_t));
1989 
1990   descr->ptr_allocated = alloc_ptr; // remember allocated pointer
1991   // we don't need size_allocated
1992   descr->ptr_aligned = (void *)this_thr; // remember allocating thread
1993   // (it is already saved in bget buffer,
1994   // but we may want to use another allocator in future)
1995   descr->size_aligned = size;
1996 
1997 end:
1998   KE_TRACE(25, ("<- __kmp_fast_allocate( T#%d ) returns %p\n",
1999                 __kmp_gtid_from_thread(this_thr), ptr));
2000   return ptr;
2001 } // func __kmp_fast_allocate
2002 
2003 // Free fast memory and place it on the thread's free list if it is of
2004 // the correct size.
2005 void ___kmp_fast_free(kmp_info_t *this_thr, void *ptr KMP_SRC_LOC_DECL) {
2006   kmp_mem_descr_t *descr;
2007   kmp_info_t *alloc_thr;
2008   size_t size;
2009   size_t idx;
2010   int index;
2011 
2012   KE_TRACE(25, ("-> __kmp_fast_free( T#%d, %p ) called from %s:%d\n",
2013                 __kmp_gtid_from_thread(this_thr), ptr KMP_SRC_LOC_PARM));
2014   KMP_ASSERT(ptr != NULL);
2015 
2016   descr = (kmp_mem_descr_t *)(((kmp_uintptr_t)ptr) - sizeof(kmp_mem_descr_t));
2017 
2018   KE_TRACE(26, ("   __kmp_fast_free:     size_aligned=%d\n",
2019                 (int)descr->size_aligned));
2020 
2021   size = descr->size_aligned; // 2, 4, 16, 64, 65, 66, ... cache lines
2022 
2023   idx = DCACHE_LINE * 2; // 2 cache lines is minimal size of block
2024   if (idx == size) {
2025     index = 0; // 2 cache lines
2026   } else if ((idx <<= 1) == size) {
2027     index = 1; // 4 cache lines
2028   } else if ((idx <<= 2) == size) {
2029     index = 2; // 16 cache lines
2030   } else if ((idx <<= 2) == size) {
2031     index = 3; // 64 cache lines
2032   } else {
2033     KMP_DEBUG_ASSERT(size > DCACHE_LINE * 64);
2034     goto free_call; // 65 or more cache lines ( > 8KB )
2035   }
2036 
2037   alloc_thr = (kmp_info_t *)descr->ptr_aligned; // get thread owning the block
2038   if (alloc_thr == this_thr) {
2039     // push block to self no-sync free list, linking previous head (LIFO)
2040     *((void **)ptr) = this_thr->th.th_free_lists[index].th_free_list_self;
2041     this_thr->th.th_free_lists[index].th_free_list_self = ptr;
2042   } else {
2043     void *head = this_thr->th.th_free_lists[index].th_free_list_other;
2044     if (head == NULL) {
2045       // Create new free list
2046       this_thr->th.th_free_lists[index].th_free_list_other = ptr;
2047       *((void **)ptr) = NULL; // mark the tail of the list
2048       descr->size_allocated = (size_t)1; // head of the list keeps its length
2049     } else {
2050       // need to check existed "other" list's owner thread and size of queue
2051       kmp_mem_descr_t *dsc =
2052           (kmp_mem_descr_t *)((char *)head - sizeof(kmp_mem_descr_t));
2053       // allocating thread, same for all queue nodes
2054       kmp_info_t *q_th = (kmp_info_t *)(dsc->ptr_aligned);
2055       size_t q_sz =
2056           dsc->size_allocated + 1; // new size in case we add current task
2057       if (q_th == alloc_thr && q_sz <= KMP_FREE_LIST_LIMIT) {
2058         // we can add current task to "other" list, no sync needed
2059         *((void **)ptr) = head;
2060         descr->size_allocated = q_sz;
2061         this_thr->th.th_free_lists[index].th_free_list_other = ptr;
2062       } else {
2063         // either queue blocks owner is changing or size limit exceeded
2064         // return old queue to allocating thread (q_th) synchronously,
2065         // and start new list for alloc_thr's tasks
2066         void *old_ptr;
2067         void *tail = head;
2068         void *next = *((void **)head);
2069         while (next != NULL) {
2070           KMP_DEBUG_ASSERT(
2071               // queue size should decrease by 1 each step through the list
2072               ((kmp_mem_descr_t *)((char *)next - sizeof(kmp_mem_descr_t)))
2073                       ->size_allocated +
2074                   1 ==
2075               ((kmp_mem_descr_t *)((char *)tail - sizeof(kmp_mem_descr_t)))
2076                   ->size_allocated);
2077           tail = next; // remember tail node
2078           next = *((void **)next);
2079         }
2080         KMP_DEBUG_ASSERT(q_th != NULL);
2081         // push block to owner's sync free list
2082         old_ptr = TCR_PTR(q_th->th.th_free_lists[index].th_free_list_sync);
2083         /* the next pointer must be set before setting free_list to ptr to avoid
2084            exposing a broken list to other threads, even for an instant. */
2085         *((void **)tail) = old_ptr;
2086 
2087         while (!KMP_COMPARE_AND_STORE_PTR(
2088             &q_th->th.th_free_lists[index].th_free_list_sync, old_ptr, head)) {
2089           KMP_CPU_PAUSE();
2090           old_ptr = TCR_PTR(q_th->th.th_free_lists[index].th_free_list_sync);
2091           *((void **)tail) = old_ptr;
2092         }
2093 
2094         // start new list of not-selt tasks
2095         this_thr->th.th_free_lists[index].th_free_list_other = ptr;
2096         *((void **)ptr) = NULL;
2097         descr->size_allocated = (size_t)1; // head of queue keeps its length
2098       }
2099     }
2100   }
2101   goto end;
2102 
2103 free_call:
2104   KE_TRACE(25, ("__kmp_fast_free: T#%d Calling __kmp_thread_free for size %d\n",
2105                 __kmp_gtid_from_thread(this_thr), size));
2106   __kmp_bget_dequeue(this_thr); /* Release any queued buffers */
2107   brel(this_thr, descr->ptr_allocated);
2108 
2109 end:
2110   KE_TRACE(25, ("<- __kmp_fast_free() returns\n"));
2111 
2112 } // func __kmp_fast_free
2113 
2114 // Initialize the thread free lists related to fast memory
2115 // Only do this when a thread is initially created.
2116 void __kmp_initialize_fast_memory(kmp_info_t *this_thr) {
2117   KE_TRACE(10, ("__kmp_initialize_fast_memory: Called from th %p\n", this_thr));
2118 
2119   memset(this_thr->th.th_free_lists, 0, NUM_LISTS * sizeof(kmp_free_list_t));
2120 }
2121 
2122 // Free the memory in the thread free lists related to fast memory
2123 // Only do this when a thread is being reaped (destroyed).
2124 void __kmp_free_fast_memory(kmp_info_t *th) {
2125   // Suppose we use BGET underlying allocator, walk through its structures...
2126   int bin;
2127   thr_data_t *thr = get_thr_data(th);
2128   void **lst = NULL;
2129 
2130   KE_TRACE(
2131       5, ("__kmp_free_fast_memory: Called T#%d\n", __kmp_gtid_from_thread(th)));
2132 
2133   __kmp_bget_dequeue(th); // Release any queued buffers
2134 
2135   // Dig through free lists and extract all allocated blocks
2136   for (bin = 0; bin < MAX_BGET_BINS; ++bin) {
2137     bfhead_t *b = thr->freelist[bin].ql.flink;
2138     while (b != &thr->freelist[bin]) {
2139       if ((kmp_uintptr_t)b->bh.bb.bthr & 1) { // the buffer is allocated address
2140         *((void **)b) =
2141             lst; // link the list (override bthr, but keep flink yet)
2142         lst = (void **)b; // push b into lst
2143       }
2144       b = b->ql.flink; // get next buffer
2145     }
2146   }
2147   while (lst != NULL) {
2148     void *next = *lst;
2149     KE_TRACE(10, ("__kmp_free_fast_memory: freeing %p, next=%p th %p (%d)\n",
2150                   lst, next, th, __kmp_gtid_from_thread(th)));
2151     (*thr->relfcn)(lst);
2152 #if BufStats
2153     // count blocks to prevent problems in __kmp_finalize_bget()
2154     thr->numprel++; /* Nr of expansion block releases */
2155     thr->numpblk--; /* Total number of blocks */
2156 #endif
2157     lst = (void **)next;
2158   }
2159 
2160   KE_TRACE(
2161       5, ("__kmp_free_fast_memory: Freed T#%d\n", __kmp_gtid_from_thread(th)));
2162 }
2163 
2164 #endif // USE_FAST_MEMORY
2165