| /* |
| * kmp_alloc.c -- private/shared dyanmic memory allocation and management |
| */ |
| |
| |
| //===----------------------------------------------------------------------===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is dual licensed under the MIT and the University of Illinois Open |
| // Source Licenses. See LICENSE.txt for details. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| |
| #include "kmp.h" |
| #include "kmp_wrapper_malloc.h" |
| #include "kmp_io.h" |
| |
| // Disable bget when it is not used |
| #if KMP_USE_BGET |
| |
| /* Thread private buffer management code */ |
| |
| typedef int (*bget_compact_t)(size_t, int); |
| typedef void *(*bget_acquire_t)(size_t); |
| typedef void (*bget_release_t)(void *); |
| |
| /* NOTE: bufsize must be a signed datatype */ |
| |
| #if KMP_OS_WINDOWS |
| # if KMP_ARCH_X86 || KMP_ARCH_ARM |
| typedef kmp_int32 bufsize; |
| # else |
| typedef kmp_int64 bufsize; |
| # endif |
| #else |
| typedef ssize_t bufsize; |
| #endif |
| |
| /* The three modes of operation are, fifo search, lifo search, and best-fit */ |
| |
| typedef enum bget_mode { |
| bget_mode_fifo = 0, |
| bget_mode_lifo = 1, |
| bget_mode_best = 2 |
| } bget_mode_t; |
| |
| |
| static void bpool( kmp_info_t *th, void *buffer, bufsize len); |
| static void *bget( kmp_info_t *th, bufsize size); |
| static void *bgetz( kmp_info_t *th, bufsize size); |
| static void *bgetr( kmp_info_t *th, void *buffer, bufsize newsize); |
| static void brel( kmp_info_t *th, void *buf); |
| static void bectl( kmp_info_t *th, bget_compact_t compact, bget_acquire_t acquire, bget_release_t release, bufsize pool_incr ); |
| |
| #ifdef KMP_DEBUG |
| static void bstats( kmp_info_t *th, bufsize *curalloc, bufsize *totfree, bufsize *maxfree, long *nget, long *nrel); |
| static void bstatse( kmp_info_t *th, bufsize *pool_incr, long *npool, long *npget, long *nprel, long *ndget, long *ndrel); |
| static void bufdump( kmp_info_t *th, void *buf); |
| static void bpoold( kmp_info_t *th, void *pool, int dumpalloc, int dumpfree); |
| static int bpoolv( kmp_info_t *th, void *pool); |
| #endif |
| |
| /* BGET CONFIGURATION */ |
| /* Buffer allocation size quantum: |
| all buffers allocated are a |
| multiple of this size. This |
| MUST be a power of two. */ |
| |
| /* On IA-32 architecture with Linux* OS, |
| malloc() does not |
| ensure 16 byte alignmnent */ |
| |
| #if KMP_ARCH_X86 || !KMP_HAVE_QUAD |
| |
| #define SizeQuant 8 |
| #define AlignType double |
| |
| #else |
| |
| #define SizeQuant 16 |
| #define AlignType _Quad |
| |
| #endif |
| |
| #define BufStats 1 /* Define this symbol to enable the |
| bstats() function which calculates |
| the total free space in the buffer |
| pool, the largest available |
| buffer, and the total space |
| currently allocated. */ |
| |
| #ifdef KMP_DEBUG |
| |
| #define BufDump 1 /* Define this symbol to enable the |
| bpoold() function which dumps the |
| buffers in a buffer pool. */ |
| |
| #define BufValid 1 /* Define this symbol to enable the |
| bpoolv() function for validating |
| a buffer pool. */ |
| |
| #define DumpData 1 /* Define this symbol to enable the |
| bufdump() function which allows |
| dumping the contents of an allocated |
| or free buffer. */ |
| #ifdef NOT_USED_NOW |
| |
| #define FreeWipe 1 /* Wipe free buffers to a guaranteed |
| pattern of garbage to trip up |
| miscreants who attempt to use |
| pointers into released buffers. */ |
| |
| #define BestFit 1 /* Use a best fit algorithm when |
| searching for space for an |
| allocation request. This uses |
| memory more efficiently, but |
| allocation will be much slower. */ |
| #endif /* NOT_USED_NOW */ |
| #endif /* KMP_DEBUG */ |
| |
| |
| static bufsize bget_bin_size[ ] = { |
| 0, |
| // 1 << 6, /* .5 Cache line */ |
| 1 << 7, /* 1 Cache line, new */ |
| 1 << 8, /* 2 Cache lines */ |
| 1 << 9, /* 4 Cache lines, new */ |
| 1 << 10, /* 8 Cache lines */ |
| 1 << 11, /* 16 Cache lines, new */ |
| 1 << 12, |
| 1 << 13, /* new */ |
| 1 << 14, |
| 1 << 15, /* new */ |
| 1 << 16, |
| 1 << 17, |
| 1 << 18, |
| 1 << 19, |
| 1 << 20, /* 1MB */ |
| 1 << 21, /* 2MB */ |
| 1 << 22, /* 4MB */ |
| 1 << 23, /* 8MB */ |
| 1 << 24, /* 16MB */ |
| 1 << 25, /* 32MB */ |
| }; |
| |
| #define MAX_BGET_BINS (int)(sizeof(bget_bin_size) / sizeof(bufsize)) |
| |
| struct bfhead; |
| |
| /* Declare the interface, including the requested buffer size type, |
| bufsize. */ |
| |
| /* Queue links */ |
| |
| typedef struct qlinks { |
| struct bfhead *flink; /* Forward link */ |
| struct bfhead *blink; /* Backward link */ |
| } qlinks_t; |
| |
| /* Header in allocated and free buffers */ |
| |
| typedef struct bhead2 { |
| kmp_info_t *bthr; /* The thread which owns the buffer pool */ |
| bufsize prevfree; /* Relative link back to previous |
| free buffer in memory or 0 if |
| previous buffer is allocated. */ |
| bufsize bsize; /* Buffer size: positive if free, |
| negative if allocated. */ |
| } bhead2_t; |
| |
| /* Make sure the bhead structure is a multiple of SizeQuant in size. */ |
| |
| typedef union bhead { |
| KMP_ALIGN( SizeQuant ) |
| AlignType b_align; |
| char b_pad[ sizeof(bhead2_t) + (SizeQuant - (sizeof(bhead2_t) % SizeQuant)) ]; |
| bhead2_t bb; |
| } bhead_t; |
| #define BH(p) ((bhead_t *) (p)) |
| |
| /* Header in directly allocated buffers (by acqfcn) */ |
| |
| typedef struct bdhead |
| { |
| bufsize tsize; /* Total size, including overhead */ |
| bhead_t bh; /* Common header */ |
| } bdhead_t; |
| #define BDH(p) ((bdhead_t *) (p)) |
| |
| /* Header in free buffers */ |
| |
| typedef struct bfhead { |
| bhead_t bh; /* Common allocated/free header */ |
| qlinks_t ql; /* Links on free list */ |
| } bfhead_t; |
| #define BFH(p) ((bfhead_t *) (p)) |
| |
| typedef struct thr_data { |
| bfhead_t freelist[ MAX_BGET_BINS ]; |
| #if BufStats |
| size_t totalloc; /* Total space currently allocated */ |
| long numget, numrel; /* Number of bget() and brel() calls */ |
| long numpblk; /* Number of pool blocks */ |
| long numpget, numprel; /* Number of block gets and rels */ |
| long numdget, numdrel; /* Number of direct gets and rels */ |
| #endif /* BufStats */ |
| |
| /* Automatic expansion block management functions */ |
| bget_compact_t compfcn; |
| bget_acquire_t acqfcn; |
| bget_release_t relfcn; |
| |
| bget_mode_t mode; /* what allocation mode to use? */ |
| |
| bufsize exp_incr; /* Expansion block size */ |
| bufsize pool_len; /* 0: no bpool calls have been made |
| -1: not all pool blocks are |
| the same size |
| >0: (common) block size for all |
| bpool calls made so far |
| */ |
| bfhead_t * last_pool; /* Last pool owned by this thread (delay dealocation) */ |
| } thr_data_t; |
| |
| /* Minimum allocation quantum: */ |
| |
| #define QLSize (sizeof(qlinks_t)) |
| #define SizeQ ((SizeQuant > QLSize) ? SizeQuant : QLSize) |
| #define MaxSize (bufsize)( ~ ( ( (bufsize)( 1 ) << ( sizeof( bufsize ) * CHAR_BIT - 1 ) ) | ( SizeQuant - 1 ) ) ) |
| // Maximun for the requested size. |
| |
| /* End sentinel: value placed in bsize field of dummy block delimiting |
| end of pool block. The most negative number which will fit in a |
| bufsize, defined in a way that the compiler will accept. */ |
| |
| #define ESent ((bufsize) (-(((((bufsize)1)<<((int)sizeof(bufsize)*8-2))-1)*2)-2)) |
| |
| /* ------------------------------------------------------------------------ */ |
| |
| /* Thread Data management routines */ |
| |
| static int |
| bget_get_bin( bufsize size ) |
| { |
| // binary chop bins |
| int lo = 0, hi = MAX_BGET_BINS - 1; |
| |
| KMP_DEBUG_ASSERT( size > 0 ); |
| |
| while ( (hi - lo) > 1 ) { |
| int mid = (lo + hi) >> 1; |
| if (size < bget_bin_size[ mid ]) |
| hi = mid - 1; |
| else |
| lo = mid; |
| } |
| |
| KMP_DEBUG_ASSERT( (lo >= 0) && (lo < MAX_BGET_BINS) ); |
| |
| return lo; |
| } |
| |
| static void |
| set_thr_data( kmp_info_t *th ) |
| { |
| int i; |
| thr_data_t *data; |
| |
| data = |
| (thr_data_t *)( |
| ( ! th->th.th_local.bget_data ) ? __kmp_allocate( sizeof( *data ) ) : th->th.th_local.bget_data |
| ); |
| |
| memset( data, '\0', sizeof( *data ) ); |
| |
| for (i = 0; i < MAX_BGET_BINS; ++i) { |
| data->freelist[ i ].ql.flink = & data->freelist[ i ]; |
| data->freelist[ i ].ql.blink = & data->freelist[ i ]; |
| } |
| |
| th->th.th_local.bget_data = data; |
| th->th.th_local.bget_list = 0; |
| #if ! USE_CMP_XCHG_FOR_BGET |
| #ifdef USE_QUEUING_LOCK_FOR_BGET |
| __kmp_init_lock( & th->th.th_local.bget_lock ); |
| #else |
| __kmp_init_bootstrap_lock( & th->th.th_local.bget_lock ); |
| #endif /* USE_LOCK_FOR_BGET */ |
| #endif /* ! USE_CMP_XCHG_FOR_BGET */ |
| } |
| |
| static thr_data_t * |
| get_thr_data( kmp_info_t *th ) |
| { |
| thr_data_t *data; |
| |
| data = (thr_data_t *) th->th.th_local.bget_data; |
| |
| KMP_DEBUG_ASSERT( data != 0 ); |
| |
| return data; |
| } |
| |
| |
| #ifdef KMP_DEBUG |
| |
| static void |
| __kmp_bget_validate_queue( kmp_info_t *th ) |
| { |
| /* NOTE: assume that the global_lock is held */ |
| |
| void *p = (void *) th->th.th_local.bget_list; |
| |
| while (p != 0) { |
| bfhead_t *b = BFH(((char *) p) - sizeof(bhead_t)); |
| |
| KMP_DEBUG_ASSERT(b->bh.bb.bsize != 0); |
| p = (void *) b->ql.flink; |
| } |
| } |
| |
| #endif |
| |
| /* Walk the free list and release the enqueued buffers */ |
| |
| static void |
| __kmp_bget_dequeue( kmp_info_t *th ) |
| { |
| void *p = TCR_SYNC_PTR(th->th.th_local.bget_list); |
| |
| if (p != 0) { |
| #if USE_CMP_XCHG_FOR_BGET |
| { |
| volatile void *old_value = TCR_SYNC_PTR(th->th.th_local.bget_list); |
| while ( ! KMP_COMPARE_AND_STORE_PTR( |
| & th->th.th_local.bget_list, old_value, NULL ) ) |
| { |
| KMP_CPU_PAUSE(); |
| old_value = TCR_SYNC_PTR(th->th.th_local.bget_list); |
| } |
| p = (void *) old_value; |
| } |
| #else /* ! USE_CMP_XCHG_FOR_BGET */ |
| #ifdef USE_QUEUING_LOCK_FOR_BGET |
| __kmp_acquire_lock( & th->th.th_local.bget_lock, |
| __kmp_gtid_from_thread(th) ); |
| #else |
| __kmp_acquire_bootstrap_lock( & th->th.th_local.bget_lock ); |
| #endif /* USE_QUEUING_LOCK_FOR_BGET */ |
| |
| p = (void *) th->th.th_local.bget_list; |
| th->th.th_local.bget_list = 0; |
| |
| #ifdef USE_QUEUING_LOCK_FOR_BGET |
| __kmp_release_lock( & th->th.th_local.bget_lock, |
| __kmp_gtid_from_thread(th) ); |
| #else |
| __kmp_release_bootstrap_lock( & th->th.th_local.bget_lock ); |
| #endif |
| #endif /* USE_CMP_XCHG_FOR_BGET */ |
| |
| /* Check again to make sure the list is not empty */ |
| |
| while (p != 0) { |
| void *buf = p; |
| bfhead_t *b = BFH(((char *) p) - sizeof(bhead_t)); |
| |
| KMP_DEBUG_ASSERT( b->bh.bb.bsize != 0 ); |
| KMP_DEBUG_ASSERT( ( (kmp_uintptr_t)TCR_PTR(b->bh.bb.bthr) & ~1 ) == |
| (kmp_uintptr_t)th ); // clear possible mark |
| KMP_DEBUG_ASSERT( b->ql.blink == 0 ); |
| |
| p = (void *) b->ql.flink; |
| |
| brel( th, buf ); |
| } |
| } |
| } |
| |
| /* Chain together the free buffers by using the thread owner field */ |
| |
| static void |
| __kmp_bget_enqueue( kmp_info_t *th, void *buf |
| #ifdef USE_QUEUING_LOCK_FOR_BGET |
| , kmp_int32 rel_gtid |
| #endif |
| ) |
| { |
| bfhead_t *b = BFH(((char *) buf) - sizeof(bhead_t)); |
| |
| KMP_DEBUG_ASSERT( b->bh.bb.bsize != 0 ); |
| KMP_DEBUG_ASSERT( ( (kmp_uintptr_t)TCR_PTR(b->bh.bb.bthr) & ~1 ) == |
| (kmp_uintptr_t)th ); // clear possible mark |
| |
| b->ql.blink = 0; |
| |
| KC_TRACE( 10, ( "__kmp_bget_enqueue: moving buffer to T#%d list\n", |
| __kmp_gtid_from_thread( th ) ) ); |
| |
| #if USE_CMP_XCHG_FOR_BGET |
| { |
| volatile void *old_value = TCR_PTR(th->th.th_local.bget_list); |
| /* the next pointer must be set before setting bget_list to buf to avoid |
| exposing a broken list to other threads, even for an instant. */ |
| b->ql.flink = BFH( old_value ); |
| |
| while ( ! KMP_COMPARE_AND_STORE_PTR( |
| & th->th.th_local.bget_list, old_value, buf ) ) |
| { |
| KMP_CPU_PAUSE(); |
| old_value = TCR_PTR(th->th.th_local.bget_list); |
| /* the next pointer must be set before setting bget_list to buf to avoid |
| exposing a broken list to other threads, even for an instant. */ |
| b->ql.flink = BFH( old_value ); |
| } |
| } |
| #else /* ! USE_CMP_XCHG_FOR_BGET */ |
| # ifdef USE_QUEUING_LOCK_FOR_BGET |
| __kmp_acquire_lock( & th->th.th_local.bget_lock, rel_gtid ); |
| # else |
| __kmp_acquire_bootstrap_lock( & th->th.th_local.bget_lock ); |
| # endif |
| |
| b->ql.flink = BFH( th->th.th_local.bget_list ); |
| th->th.th_local.bget_list = (void *) buf; |
| |
| # ifdef USE_QUEUING_LOCK_FOR_BGET |
| __kmp_release_lock( & th->th.th_local.bget_lock, rel_gtid ); |
| # else |
| __kmp_release_bootstrap_lock( & th->th.th_local.bget_lock ); |
| # endif |
| #endif /* USE_CMP_XCHG_FOR_BGET */ |
| } |
| |
| /* insert buffer back onto a new freelist */ |
| |
| static void |
| __kmp_bget_insert_into_freelist( thr_data_t *thr, bfhead_t *b ) |
| { |
| int bin; |
| |
| KMP_DEBUG_ASSERT( ((size_t)b ) % SizeQuant == 0 ); |
| KMP_DEBUG_ASSERT( b->bh.bb.bsize % SizeQuant == 0 ); |
| |
| bin = bget_get_bin( b->bh.bb.bsize ); |
| |
| KMP_DEBUG_ASSERT(thr->freelist[ bin ].ql.blink->ql.flink == &thr->freelist[ bin ]); |
| KMP_DEBUG_ASSERT(thr->freelist[ bin ].ql.flink->ql.blink == &thr->freelist[ bin ]); |
| |
| b->ql.flink = &thr->freelist[ bin ]; |
| b->ql.blink = thr->freelist[ bin ].ql.blink; |
| |
| thr->freelist[ bin ].ql.blink = b; |
| b->ql.blink->ql.flink = b; |
| } |
| |
| /* unlink the buffer from the old freelist */ |
| |
| static void |
| __kmp_bget_remove_from_freelist( bfhead_t *b ) |
| { |
| KMP_DEBUG_ASSERT(b->ql.blink->ql.flink == b); |
| KMP_DEBUG_ASSERT(b->ql.flink->ql.blink == b); |
| |
| b->ql.blink->ql.flink = b->ql.flink; |
| b->ql.flink->ql.blink = b->ql.blink; |
| } |
| |
| /* ------------------------------------------------------------------------ */ |
| |
| /* GET STATS -- check info on free list */ |
| |
| static void |
| bcheck( kmp_info_t *th, bufsize *max_free, bufsize *total_free ) |
| { |
| thr_data_t *thr = get_thr_data( th ); |
| int bin; |
| |
| *total_free = *max_free = 0; |
| |
| for (bin = 0; bin < MAX_BGET_BINS; ++bin) { |
| bfhead_t *b, *best; |
| |
| best = &thr->freelist[ bin ]; |
| b = best->ql.flink; |
| |
| while (b != &thr->freelist[ bin ]) { |
| *total_free += (b->bh.bb.bsize - sizeof( bhead_t )); |
| if ((best == &thr->freelist[ bin ]) || (b->bh.bb.bsize < best->bh.bb.bsize)) |
| best = b; |
| |
| /* Link to next buffer */ |
| b = b->ql.flink; |
| } |
| |
| if (*max_free < best->bh.bb.bsize) |
| *max_free = best->bh.bb.bsize; |
| } |
| |
| if (*max_free > (bufsize)sizeof( bhead_t )) |
| *max_free -= sizeof( bhead_t ); |
| } |
| |
| /* ------------------------------------------------------------------------ */ |
| |
| /* BGET -- Allocate a buffer. */ |
| |
| static void * |
| bget( kmp_info_t *th, bufsize requested_size ) |
| { |
| thr_data_t *thr = get_thr_data( th ); |
| bufsize size = requested_size; |
| bfhead_t *b; |
| void *buf; |
| int compactseq = 0; |
| int use_blink = 0; |
| /* For BestFit */ |
| bfhead_t *best; |
| |
| if ( size < 0 || size + sizeof( bhead_t ) > MaxSize ) { |
| return NULL; |
| }; // if |
| |
| __kmp_bget_dequeue( th ); /* Release any queued buffers */ |
| |
| if (size < (bufsize)SizeQ) { /* Need at least room for the */ |
| size = SizeQ; /* queue links. */ |
| } |
| #if defined( SizeQuant ) && ( SizeQuant > 1 ) |
| size = (size + (SizeQuant - 1)) & (~(SizeQuant - 1)); |
| #endif |
| |
| size += sizeof(bhead_t); /* Add overhead in allocated buffer |
| to size required. */ |
| KMP_DEBUG_ASSERT( size >= 0 ); |
| KMP_DEBUG_ASSERT( size % SizeQuant == 0 ); |
| |
| use_blink = ( thr->mode == bget_mode_lifo ); |
| |
| /* If a compact function was provided in the call to bectl(), wrap |
| a loop around the allocation process to allow compaction to |
| intervene in case we don't find a suitable buffer in the chain. */ |
| |
| for (;;) { |
| int bin; |
| |
| for (bin = bget_get_bin( size ); bin < MAX_BGET_BINS; ++bin) { |
| /* Link to next buffer */ |
| b = ( use_blink ? thr->freelist[ bin ].ql.blink : thr->freelist[ bin ].ql.flink ); |
| |
| if (thr->mode == bget_mode_best) { |
| best = &thr->freelist[ bin ]; |
| |
| /* Scan the free list searching for the first buffer big enough |
| to hold the requested size buffer. */ |
| |
| while (b != &thr->freelist[ bin ]) { |
| if (b->bh.bb.bsize >= (bufsize) size) { |
| if ((best == &thr->freelist[ bin ]) || (b->bh.bb.bsize < best->bh.bb.bsize)) { |
| best = b; |
| } |
| } |
| |
| /* Link to next buffer */ |
| b = ( use_blink ? b->ql.blink : b->ql.flink ); |
| } |
| b = best; |
| } |
| |
| while (b != &thr->freelist[ bin ]) { |
| if ((bufsize) b->bh.bb.bsize >= (bufsize) size) { |
| |
| /* Buffer is big enough to satisfy the request. Allocate it |
| to the caller. We must decide whether the buffer is large |
| enough to split into the part given to the caller and a |
| free buffer that remains on the free list, or whether the |
| entire buffer should be removed from the free list and |
| given to the caller in its entirety. We only split the |
| buffer if enough room remains for a header plus the minimum |
| quantum of allocation. */ |
| |
| if ((b->bh.bb.bsize - (bufsize) size) > (bufsize)(SizeQ + (sizeof(bhead_t)))) { |
| bhead_t *ba, *bn; |
| |
| ba = BH(((char *) b) + (b->bh.bb.bsize - (bufsize) size)); |
| bn = BH(((char *) ba) + size); |
| |
| KMP_DEBUG_ASSERT(bn->bb.prevfree == b->bh.bb.bsize); |
| |
| /* Subtract size from length of free block. */ |
| b->bh.bb.bsize -= (bufsize) size; |
| |
| /* Link allocated buffer to the previous free buffer. */ |
| ba->bb.prevfree = b->bh.bb.bsize; |
| |
| /* Plug negative size into user buffer. */ |
| ba->bb.bsize = -size; |
| |
| /* Mark this buffer as owned by this thread. */ |
| TCW_PTR(ba->bb.bthr, th); // not an allocated address (do not mark it) |
| /* Mark buffer after this one not preceded by free block. */ |
| bn->bb.prevfree = 0; |
| |
| /* unlink the buffer from the old freelist, and reinsert it into the new freelist */ |
| __kmp_bget_remove_from_freelist( b ); |
| __kmp_bget_insert_into_freelist( thr, b ); |
| #if BufStats |
| thr->totalloc += (size_t) size; |
| thr->numget++; /* Increment number of bget() calls */ |
| #endif |
| buf = (void *) ((((char *) ba) + sizeof(bhead_t))); |
| KMP_DEBUG_ASSERT( ((size_t)buf) % SizeQuant == 0 ); |
| return buf; |
| } else { |
| bhead_t *ba; |
| |
| ba = BH(((char *) b) + b->bh.bb.bsize); |
| |
| KMP_DEBUG_ASSERT(ba->bb.prevfree == b->bh.bb.bsize); |
| |
| /* The buffer isn't big enough to split. Give the whole |
| shebang to the caller and remove it from the free list. */ |
| |
| __kmp_bget_remove_from_freelist( b ); |
| #if BufStats |
| thr->totalloc += (size_t) b->bh.bb.bsize; |
| thr->numget++; /* Increment number of bget() calls */ |
| #endif |
| /* Negate size to mark buffer allocated. */ |
| b->bh.bb.bsize = -(b->bh.bb.bsize); |
| |
| /* Mark this buffer as owned by this thread. */ |
| TCW_PTR(ba->bb.bthr, th); // not an allocated address (do not mark it) |
| /* Zero the back pointer in the next buffer in memory |
| to indicate that this buffer is allocated. */ |
| ba->bb.prevfree = 0; |
| |
| /* Give user buffer starting at queue links. */ |
| buf = (void *) &(b->ql); |
| KMP_DEBUG_ASSERT( ((size_t)buf) % SizeQuant == 0 ); |
| return buf; |
| } |
| } |
| |
| /* Link to next buffer */ |
| b = ( use_blink ? b->ql.blink : b->ql.flink ); |
| } |
| } |
| |
| /* We failed to find a buffer. If there's a compact function |
| defined, notify it of the size requested. If it returns |
| TRUE, try the allocation again. */ |
| |
| if ((thr->compfcn == 0) || (!(*thr->compfcn)(size, ++compactseq))) { |
| break; |
| } |
| } |
| |
| /* No buffer available with requested size free. */ |
| |
| /* Don't give up yet -- look in the reserve supply. */ |
| |
| if (thr->acqfcn != 0) { |
| if (size > (bufsize) (thr->exp_incr - sizeof(bhead_t))) { |
| |
| /* Request is too large to fit in a single expansion |
| block. Try to satisy it by a direct buffer acquisition. */ |
| |
| bdhead_t *bdh; |
| |
| size += sizeof(bdhead_t) - sizeof(bhead_t); |
| |
| KE_TRACE( 10, ("%%%%%% MALLOC( %d )\n", (int) size ) ); |
| |
| /* richryan */ |
| bdh = BDH((*thr->acqfcn)((bufsize) size)); |
| if (bdh != NULL) { |
| |
| /* Mark the buffer special by setting the size field |
| of its header to zero. */ |
| bdh->bh.bb.bsize = 0; |
| |
| /* Mark this buffer as owned by this thread. */ |
| TCW_PTR(bdh->bh.bb.bthr, th); // don't mark buffer as allocated, |
| // because direct buffer never goes to free list |
| bdh->bh.bb.prevfree = 0; |
| bdh->tsize = size; |
| #if BufStats |
| thr->totalloc += (size_t) size; |
| thr->numget++; /* Increment number of bget() calls */ |
| thr->numdget++; /* Direct bget() call count */ |
| #endif |
| buf = (void *) (bdh + 1); |
| KMP_DEBUG_ASSERT( ((size_t)buf) % SizeQuant == 0 ); |
| return buf; |
| } |
| |
| } else { |
| |
| /* Try to obtain a new expansion block */ |
| |
| void *newpool; |
| |
| KE_TRACE( 10, ("%%%%%% MALLOCB( %d )\n", (int) thr->exp_incr ) ); |
| |
| /* richryan */ |
| newpool = (*thr->acqfcn)((bufsize) thr->exp_incr); |
| KMP_DEBUG_ASSERT( ((size_t)newpool) % SizeQuant == 0 ); |
| if (newpool != NULL) { |
| bpool( th, newpool, thr->exp_incr); |
| buf = bget( th, requested_size); /* This can't, I say, can't get into a loop. */ |
| return buf; |
| } |
| } |
| } |
| |
| /* Still no buffer available */ |
| |
| return NULL; |
| } |
| |
| /* BGETZ -- Allocate a buffer and clear its contents to zero. We clear |
| the entire contents of the buffer to zero, not just the |
| region requested by the caller. */ |
| |
| static void * |
| bgetz( kmp_info_t *th, bufsize size ) |
| { |
| char *buf = (char *) bget( th, size); |
| |
| if (buf != NULL) { |
| bhead_t *b; |
| bufsize rsize; |
| |
| b = BH(buf - sizeof(bhead_t)); |
| rsize = -(b->bb.bsize); |
| if (rsize == 0) { |
| bdhead_t *bd; |
| |
| bd = BDH(buf - sizeof(bdhead_t)); |
| rsize = bd->tsize - (bufsize) sizeof(bdhead_t); |
| } else { |
| rsize -= sizeof(bhead_t); |
| } |
| |
| KMP_DEBUG_ASSERT(rsize >= size); |
| |
| (void) memset(buf, 0, (bufsize) rsize); |
| } |
| return ((void *) buf); |
| } |
| |
| /* BGETR -- Reallocate a buffer. This is a minimal implementation, |
| simply in terms of brel() and bget(). It could be |
| enhanced to allow the buffer to grow into adjacent free |
| blocks and to avoid moving data unnecessarily. */ |
| |
| static void * |
| bgetr( kmp_info_t *th, void *buf, bufsize size) |
| { |
| void *nbuf; |
| bufsize osize; /* Old size of buffer */ |
| bhead_t *b; |
| |
| nbuf = bget( th, size ); |
| if ( nbuf == NULL ) { /* Acquire new buffer */ |
| return NULL; |
| } |
| if ( buf == NULL ) { |
| return nbuf; |
| } |
| b = BH(((char *) buf) - sizeof(bhead_t)); |
| osize = -b->bb.bsize; |
| if (osize == 0) { |
| /* Buffer acquired directly through acqfcn. */ |
| bdhead_t *bd; |
| |
| bd = BDH(((char *) buf) - sizeof(bdhead_t)); |
| osize = bd->tsize - (bufsize) sizeof(bdhead_t); |
| } else { |
| osize -= sizeof(bhead_t); |
| }; |
| |
| KMP_DEBUG_ASSERT(osize > 0); |
| |
| (void) KMP_MEMCPY((char *) nbuf, (char *) buf, /* Copy the data */ |
| (size_t) ((size < osize) ? size : osize)); |
| brel( th, buf ); |
| |
| return nbuf; |
| } |
| |
| /* BREL -- Release a buffer. */ |
| |
| static void |
| brel( kmp_info_t *th, void *buf ) |
| { |
| thr_data_t *thr = get_thr_data( th ); |
| bfhead_t *b, *bn; |
| kmp_info_t *bth; |
| |
| KMP_DEBUG_ASSERT(buf != NULL); |
| KMP_DEBUG_ASSERT( ((size_t)buf) % SizeQuant == 0 ); |
| |
| b = BFH(((char *) buf) - sizeof(bhead_t)); |
| |
| if (b->bh.bb.bsize == 0) { /* Directly-acquired buffer? */ |
| bdhead_t *bdh; |
| |
| bdh = BDH(((char *) buf) - sizeof(bdhead_t)); |
| KMP_DEBUG_ASSERT(b->bh.bb.prevfree == 0); |
| #if BufStats |
| thr->totalloc -= (size_t) bdh->tsize; |
| thr->numdrel++; /* Number of direct releases */ |
| thr->numrel++; /* Increment number of brel() calls */ |
| #endif /* BufStats */ |
| #ifdef FreeWipe |
| (void) memset((char *) buf, 0x55, |
| (size_t) (bdh->tsize - sizeof(bdhead_t))); |
| #endif /* FreeWipe */ |
| |
| KE_TRACE( 10, ("%%%%%% FREE( %p )\n", (void *) bdh ) ); |
| |
| KMP_DEBUG_ASSERT( thr->relfcn != 0 ); |
| (*thr->relfcn)((void *) bdh); /* Release it directly. */ |
| return; |
| } |
| |
| bth = (kmp_info_t *)( (kmp_uintptr_t)TCR_PTR(b->bh.bb.bthr) & ~1 ); // clear possible mark before comparison |
| if ( bth != th ) { |
| /* Add this buffer to be released by the owning thread later */ |
| __kmp_bget_enqueue( bth, buf |
| #ifdef USE_QUEUING_LOCK_FOR_BGET |
| , __kmp_gtid_from_thread( th ) |
| #endif |
| ); |
| return; |
| } |
| |
| /* Buffer size must be negative, indicating that the buffer is |
| allocated. */ |
| |
| if (b->bh.bb.bsize >= 0) { |
| bn = NULL; |
| } |
| KMP_DEBUG_ASSERT(b->bh.bb.bsize < 0); |
| |
| /* Back pointer in next buffer must be zero, indicating the |
| same thing: */ |
| |
| KMP_DEBUG_ASSERT(BH((char *) b - b->bh.bb.bsize)->bb.prevfree == 0); |
| |
| #if BufStats |
| thr->numrel++; /* Increment number of brel() calls */ |
| thr->totalloc += (size_t) b->bh.bb.bsize; |
| #endif |
| |
| /* If the back link is nonzero, the previous buffer is free. */ |
| |
| if (b->bh.bb.prevfree != 0) { |
| /* The previous buffer is free. Consolidate this buffer with it |
| by adding the length of this buffer to the previous free |
| buffer. Note that we subtract the size in the buffer being |
| released, since it's negative to indicate that the buffer is |
| allocated. */ |
| |
| register bufsize size = b->bh.bb.bsize; |
| |
| /* Make the previous buffer the one we're working on. */ |
| KMP_DEBUG_ASSERT(BH((char *) b - b->bh.bb.prevfree)->bb.bsize == b->bh.bb.prevfree); |
| b = BFH(((char *) b) - b->bh.bb.prevfree); |
| b->bh.bb.bsize -= size; |
| |
| /* unlink the buffer from the old freelist */ |
| __kmp_bget_remove_from_freelist( b ); |
| } |
| else { |
| /* The previous buffer isn't allocated. Mark this buffer |
| size as positive (i.e. free) and fall through to place |
| the buffer on the free list as an isolated free block. */ |
| |
| b->bh.bb.bsize = -b->bh.bb.bsize; |
| } |
| |
| /* insert buffer back onto a new freelist */ |
| __kmp_bget_insert_into_freelist( thr, b ); |
| |
| |
| /* Now we look at the next buffer in memory, located by advancing from |
| the start of this buffer by its size, to see if that buffer is |
| free. If it is, we combine this buffer with the next one in |
| memory, dechaining the second buffer from the free list. */ |
| |
| bn = BFH(((char *) b) + b->bh.bb.bsize); |
| if (bn->bh.bb.bsize > 0) { |
| |
| /* The buffer is free. Remove it from the free list and add |
| its size to that of our buffer. */ |
| |
| KMP_DEBUG_ASSERT(BH((char *) bn + bn->bh.bb.bsize)->bb.prevfree == bn->bh.bb.bsize); |
| |
| __kmp_bget_remove_from_freelist( bn ); |
| |
| b->bh.bb.bsize += bn->bh.bb.bsize; |
| |
| /* unlink the buffer from the old freelist, and reinsert it into the new freelist */ |
| |
| __kmp_bget_remove_from_freelist( b ); |
| __kmp_bget_insert_into_freelist( thr, b ); |
| |
| /* Finally, advance to the buffer that follows the newly |
| consolidated free block. We must set its backpointer to the |
| head of the consolidated free block. We know the next block |
| must be an allocated block because the process of recombination |
| guarantees that two free blocks will never be contiguous in |
| memory. */ |
| |
| bn = BFH(((char *) b) + b->bh.bb.bsize); |
| } |
| #ifdef FreeWipe |
| (void) memset(((char *) b) + sizeof(bfhead_t), 0x55, |
| (size_t) (b->bh.bb.bsize - sizeof(bfhead_t))); |
| #endif |
| KMP_DEBUG_ASSERT(bn->bh.bb.bsize < 0); |
| |
| /* The next buffer is allocated. Set the backpointer in it to point |
| to this buffer; the previous free buffer in memory. */ |
| |
| bn->bh.bb.prevfree = b->bh.bb.bsize; |
| |
| /* If a block-release function is defined, and this free buffer |
| constitutes the entire block, release it. Note that pool_len |
| is defined in such a way that the test will fail unless all |
| pool blocks are the same size. */ |
| |
| if (thr->relfcn != 0 && |
| b->bh.bb.bsize == (bufsize)(thr->pool_len - sizeof(bhead_t))) |
| { |
| #if BufStats |
| if (thr->numpblk != 1) { /* Do not release the last buffer until finalization time */ |
| #endif |
| |
| KMP_DEBUG_ASSERT(b->bh.bb.prevfree == 0); |
| KMP_DEBUG_ASSERT(BH((char *) b + b->bh.bb.bsize)->bb.bsize == ESent); |
| KMP_DEBUG_ASSERT(BH((char *) b + b->bh.bb.bsize)->bb.prevfree == b->bh.bb.bsize); |
| |
| /* Unlink the buffer from the free list */ |
| __kmp_bget_remove_from_freelist( b ); |
| |
| KE_TRACE( 10, ("%%%%%% FREE( %p )\n", (void *) b ) ); |
| |
| (*thr->relfcn)(b); |
| #if BufStats |
| thr->numprel++; /* Nr of expansion block releases */ |
| thr->numpblk--; /* Total number of blocks */ |
| KMP_DEBUG_ASSERT(thr->numpblk == thr->numpget - thr->numprel); |
| |
| /* avoid leaving stale last_pool pointer around if it is being dealloced */ |
| if (thr->last_pool == b) thr->last_pool = 0; |
| } |
| else { |
| thr->last_pool = b; |
| } |
| #endif /* BufStats */ |
| } |
| } |
| |
| /* BECTL -- Establish automatic pool expansion control */ |
| |
| static void |
| bectl( kmp_info_t *th, bget_compact_t compact, bget_acquire_t acquire, bget_release_t release, bufsize pool_incr) |
| { |
| thr_data_t *thr = get_thr_data( th ); |
| |
| thr->compfcn = compact; |
| thr->acqfcn = acquire; |
| thr->relfcn = release; |
| thr->exp_incr = pool_incr; |
| } |
| |
| /* BPOOL -- Add a region of memory to the buffer pool. */ |
| |
| static void |
| bpool( kmp_info_t *th, void *buf, bufsize len) |
| { |
| /* int bin = 0; */ |
| thr_data_t *thr = get_thr_data( th ); |
| bfhead_t *b = BFH(buf); |
| bhead_t *bn; |
| |
| __kmp_bget_dequeue( th ); /* Release any queued buffers */ |
| |
| #ifdef SizeQuant |
| len &= ~(SizeQuant - 1); |
| #endif |
| if (thr->pool_len == 0) { |
| thr->pool_len = len; |
| } else if (len != thr->pool_len) { |
| thr->pool_len = -1; |
| } |
| #if BufStats |
| thr->numpget++; /* Number of block acquisitions */ |
| thr->numpblk++; /* Number of blocks total */ |
| KMP_DEBUG_ASSERT(thr->numpblk == thr->numpget - thr->numprel); |
| #endif /* BufStats */ |
| |
| /* Since the block is initially occupied by a single free buffer, |
| it had better not be (much) larger than the largest buffer |
| whose size we can store in bhead.bb.bsize. */ |
| |
| KMP_DEBUG_ASSERT(len - sizeof(bhead_t) <= -((bufsize) ESent + 1)); |
| |
| /* Clear the backpointer at the start of the block to indicate that |
| there is no free block prior to this one. That blocks |
| recombination when the first block in memory is released. */ |
| |
| b->bh.bb.prevfree = 0; |
| |
| /* Create a dummy allocated buffer at the end of the pool. This dummy |
| buffer is seen when a buffer at the end of the pool is released and |
| blocks recombination of the last buffer with the dummy buffer at |
| the end. The length in the dummy buffer is set to the largest |
| negative number to denote the end of the pool for diagnostic |
| routines (this specific value is not counted on by the actual |
| allocation and release functions). */ |
| |
| len -= sizeof(bhead_t); |
| b->bh.bb.bsize = (bufsize) len; |
| /* Set the owner of this buffer */ |
| TCW_PTR( b->bh.bb.bthr, (kmp_info_t*)((kmp_uintptr_t)th | 1) ); // mark the buffer as allocated address |
| |
| /* Chain the new block to the free list. */ |
| __kmp_bget_insert_into_freelist( thr, b ); |
| |
| #ifdef FreeWipe |
| (void) memset(((char *) b) + sizeof(bfhead_t), 0x55, |
| (size_t) (len - sizeof(bfhead_t))); |
| #endif |
| bn = BH(((char *) b) + len); |
| bn->bb.prevfree = (bufsize) len; |
| /* Definition of ESent assumes two's complement! */ |
| KMP_DEBUG_ASSERT( (~0) == -1 && (bn != 0) ); |
| |
| bn->bb.bsize = ESent; |
| } |
| |
| /* ------------------------------------------------------------------------ */ |
| |
| /* BFREED -- Dump the free lists for this thread. */ |
| |
| static void |
| bfreed( kmp_info_t *th ) |
| { |
| int bin = 0, count = 0; |
| int gtid = __kmp_gtid_from_thread( th ); |
| thr_data_t *thr = get_thr_data( th ); |
| |
| #if BufStats |
| __kmp_printf_no_lock("__kmp_printpool: T#%d total=%" KMP_UINT64_SPEC " get=%" KMP_INT64_SPEC " rel=%" \ |
| KMP_INT64_SPEC " pblk=%" KMP_INT64_SPEC " pget=%" KMP_INT64_SPEC " prel=%" KMP_INT64_SPEC \ |
| " dget=%" KMP_INT64_SPEC " drel=%" KMP_INT64_SPEC "\n", |
| gtid, (kmp_uint64) thr->totalloc, |
| (kmp_int64) thr->numget, (kmp_int64) thr->numrel, |
| (kmp_int64) thr->numpblk, |
| (kmp_int64) thr->numpget, (kmp_int64) thr->numprel, |
| (kmp_int64) thr->numdget, (kmp_int64) thr->numdrel ); |
| #endif |
| |
| for (bin = 0; bin < MAX_BGET_BINS; ++bin) { |
| bfhead_t *b; |
| |
| for (b = thr->freelist[ bin ].ql.flink; b != &thr->freelist[ bin ]; b = b->ql.flink) { |
| bufsize bs = b->bh.bb.bsize; |
| |
| KMP_DEBUG_ASSERT( b->ql.blink->ql.flink == b ); |
| KMP_DEBUG_ASSERT( b->ql.flink->ql.blink == b ); |
| KMP_DEBUG_ASSERT( bs > 0 ); |
| |
| count += 1; |
| |
| __kmp_printf_no_lock("__kmp_printpool: T#%d Free block: 0x%p size %6ld bytes.\n", gtid, b, (long) bs ); |
| #ifdef FreeWipe |
| { |
| char *lerr = ((char *) b) + sizeof(bfhead_t); |
| if ((bs > sizeof(bfhead_t)) && ((*lerr != 0x55) || (memcmp(lerr, lerr + 1, (size_t) (bs - (sizeof(bfhead_t) + 1))) != 0))) { |
| __kmp_printf_no_lock( "__kmp_printpool: T#%d (Contents of above free block have been overstored.)\n", gtid ); |
| } |
| } |
| #endif |
| } |
| } |
| |
| if (count == 0) |
| __kmp_printf_no_lock("__kmp_printpool: T#%d No free blocks\n", gtid ); |
| } |
| |
| /* ------------------------------------------------------------------------ */ |
| |
| #ifdef KMP_DEBUG |
| |
| #if BufStats |
| |
| /* BSTATS -- Return buffer allocation free space statistics. */ |
| |
| static void |
| bstats( kmp_info_t *th, bufsize *curalloc, bufsize *totfree, bufsize *maxfree, long *nget, long *nrel) |
| { |
| int bin = 0; |
| thr_data_t *thr = get_thr_data( th ); |
| |
| *nget = thr->numget; |
| *nrel = thr->numrel; |
| *curalloc = (bufsize) thr->totalloc; |
| *totfree = 0; |
| *maxfree = -1; |
| |
| for (bin = 0; bin < MAX_BGET_BINS; ++bin) { |
| bfhead_t *b = thr->freelist[ bin ].ql.flink; |
| |
| while (b != &thr->freelist[ bin ]) { |
| KMP_DEBUG_ASSERT(b->bh.bb.bsize > 0); |
| *totfree += b->bh.bb.bsize; |
| if (b->bh.bb.bsize > *maxfree) { |
| *maxfree = b->bh.bb.bsize; |
| } |
| b = b->ql.flink; /* Link to next buffer */ |
| } |
| } |
| } |
| |
| /* BSTATSE -- Return extended statistics */ |
| |
| static void |
| bstatse( kmp_info_t *th, bufsize *pool_incr, long *npool, long *npget, long *nprel, long *ndget, long *ndrel) |
| { |
| thr_data_t *thr = get_thr_data( th ); |
| |
| *pool_incr = (thr->pool_len < 0) ? -thr->exp_incr : thr->exp_incr; |
| *npool = thr->numpblk; |
| *npget = thr->numpget; |
| *nprel = thr->numprel; |
| *ndget = thr->numdget; |
| *ndrel = thr->numdrel; |
| } |
| |
| #endif /* BufStats */ |
| |
| /* BUFDUMP -- Dump the data in a buffer. This is called with the user |
| data pointer, and backs up to the buffer header. It will |
| dump either a free block or an allocated one. */ |
| |
| static void |
| bufdump( kmp_info_t *th, void *buf ) |
| { |
| bfhead_t *b; |
| unsigned char *bdump; |
| bufsize bdlen; |
| |
| b = BFH(((char *) buf) - sizeof(bhead_t)); |
| KMP_DEBUG_ASSERT(b->bh.bb.bsize != 0); |
| if (b->bh.bb.bsize < 0) { |
| bdump = (unsigned char *) buf; |
| bdlen = (-b->bh.bb.bsize) - (bufsize) sizeof(bhead_t); |
| } else { |
| bdump = (unsigned char *) (((char *) b) + sizeof(bfhead_t)); |
| bdlen = b->bh.bb.bsize - (bufsize) sizeof(bfhead_t); |
| } |
| |
| while (bdlen > 0) { |
| int i, dupes = 0; |
| bufsize l = bdlen; |
| char bhex[50], bascii[20]; |
| |
| if (l > 16) { |
| l = 16; |
| } |
| |
| for (i = 0; i < l; i++) { |
| (void) KMP_SNPRINTF(bhex + i * 3, sizeof(bhex) - i * 3, "%02X ", bdump[i]); |
| if (bdump[i] > 0x20 && bdump[i] < 0x7F) |
| bascii[ i ] = bdump[ i ]; |
| else |
| bascii[ i ] = ' '; |
| } |
| bascii[i] = 0; |
| (void) __kmp_printf_no_lock("%-48s %s\n", bhex, bascii); |
| bdump += l; |
| bdlen -= l; |
| while ((bdlen > 16) && (memcmp((char *) (bdump - 16), |
| (char *) bdump, 16) == 0)) { |
| dupes++; |
| bdump += 16; |
| bdlen -= 16; |
| } |
| if (dupes > 1) { |
| (void) __kmp_printf_no_lock( |
| " (%d lines [%d bytes] identical to above line skipped)\n", |
| dupes, dupes * 16); |
| } else if (dupes == 1) { |
| bdump -= 16; |
| bdlen += 16; |
| } |
| } |
| } |
| |
| /* BPOOLD -- Dump a buffer pool. The buffer headers are always listed. |
| If DUMPALLOC is nonzero, the contents of allocated buffers |
| are dumped. If DUMPFREE is nonzero, free blocks are |
| dumped as well. If FreeWipe checking is enabled, free |
| blocks which have been clobbered will always be dumped. */ |
| |
| static void |
| bpoold( kmp_info_t *th, void *buf, int dumpalloc, int dumpfree) |
| { |
| bfhead_t *b = BFH( (char*)buf - sizeof(bhead_t)); |
| |
| while (b->bh.bb.bsize != ESent) { |
| bufsize bs = b->bh.bb.bsize; |
| |
| if (bs < 0) { |
| bs = -bs; |
| (void) __kmp_printf_no_lock("Allocated buffer: size %6ld bytes.\n", (long) bs); |
| if (dumpalloc) { |
| bufdump( th, (void *) (((char *) b) + sizeof(bhead_t))); |
| } |
| } else { |
| const char *lerr = ""; |
| |
| KMP_DEBUG_ASSERT(bs > 0); |
| if ((b->ql.blink->ql.flink != b) || (b->ql.flink->ql.blink != b)) { |
| lerr = " (Bad free list links)"; |
| } |
| (void) __kmp_printf_no_lock("Free block: size %6ld bytes.%s\n", |
| (long) bs, lerr); |
| #ifdef FreeWipe |
| lerr = ((char *) b) + sizeof(bfhead_t); |
| if ((bs > sizeof(bfhead_t)) && ((*lerr != 0x55) || |
| (memcmp(lerr, lerr + 1, |
| (size_t) (bs - (sizeof(bfhead_t) + 1))) != 0))) { |
| (void) __kmp_printf_no_lock( |
| "(Contents of above free block have been overstored.)\n"); |
| bufdump( th, (void *) (((char *) b) + sizeof(bhead_t))); |
| } else |
| #endif |
| if (dumpfree) { |
| bufdump( th, (void *) (((char *) b) + sizeof(bhead_t))); |
| } |
| } |
| b = BFH(((char *) b) + bs); |
| } |
| } |
| |
| /* BPOOLV -- Validate a buffer pool. */ |
| |
| static int |
| bpoolv( kmp_info_t *th, void *buf ) |
| { |
| bfhead_t *b = BFH(buf); |
| |
| while (b->bh.bb.bsize != ESent) { |
| bufsize bs = b->bh.bb.bsize; |
| |
| if (bs < 0) { |
| bs = -bs; |
| } else { |
| #ifdef FreeWipe |
| char *lerr = ""; |
| #endif |
| |
| KMP_DEBUG_ASSERT(bs > 0); |
| if (bs <= 0) { |
| return 0; |
| } |
| if ((b->ql.blink->ql.flink != b) || (b->ql.flink->ql.blink != b)) { |
| (void) __kmp_printf_no_lock("Free block: size %6ld bytes. (Bad free list links)\n", |
| (long) bs); |
| KMP_DEBUG_ASSERT(0); |
| return 0; |
| } |
| #ifdef FreeWipe |
| lerr = ((char *) b) + sizeof(bfhead_t); |
| if ((bs > sizeof(bfhead_t)) && ((*lerr != 0x55) || |
| (memcmp(lerr, lerr + 1, |
| (size_t) (bs - (sizeof(bfhead_t) + 1))) != 0))) { |
| (void) __kmp_printf_no_lock( |
| "(Contents of above free block have been overstored.)\n"); |
| bufdump( th, (void *) (((char *) b) + sizeof(bhead_t))); |
| KMP_DEBUG_ASSERT(0); |
| return 0; |
| } |
| #endif /* FreeWipe */ |
| } |
| b = BFH(((char *) b) + bs); |
| } |
| return 1; |
| } |
| |
| #endif /* KMP_DEBUG */ |
| |
| /* ------------------------------------------------------------------------ */ |
| |
| void |
| __kmp_initialize_bget( kmp_info_t *th ) |
| { |
| KMP_DEBUG_ASSERT( SizeQuant >= sizeof( void * ) && (th != 0) ); |
| |
| set_thr_data( th ); |
| |
| bectl( th, (bget_compact_t) 0, (bget_acquire_t) malloc, (bget_release_t) free, |
| (bufsize) __kmp_malloc_pool_incr ); |
| } |
| |
| void |
| __kmp_finalize_bget( kmp_info_t *th ) |
| { |
| thr_data_t *thr; |
| bfhead_t *b; |
| |
| KMP_DEBUG_ASSERT( th != 0 ); |
| |
| #if BufStats |
| thr = (thr_data_t *) th->th.th_local.bget_data; |
| KMP_DEBUG_ASSERT( thr != NULL ); |
| b = thr->last_pool; |
| |
| /* If a block-release function is defined, and this free buffer |
| constitutes the entire block, release it. Note that pool_len |
| is defined in such a way that the test will fail unless all |
| pool blocks are the same size. */ |
| |
| /* Deallocate the last pool if one exists because we no longer do it in brel() */ |
| if (thr->relfcn != 0 && b != 0 && thr->numpblk != 0 && |
| b->bh.bb.bsize == (bufsize)(thr->pool_len - sizeof(bhead_t))) |
| { |
| KMP_DEBUG_ASSERT(b->bh.bb.prevfree == 0); |
| KMP_DEBUG_ASSERT(BH((char *) b + b->bh.bb.bsize)->bb.bsize == ESent); |
| KMP_DEBUG_ASSERT(BH((char *) b + b->bh.bb.bsize)->bb.prevfree == b->bh.bb.bsize); |
| |
| /* Unlink the buffer from the free list */ |
| __kmp_bget_remove_from_freelist( b ); |
| |
| KE_TRACE( 10, ("%%%%%% FREE( %p )\n", (void *) b ) ); |
| |
| (*thr->relfcn)(b); |
| thr->numprel++; /* Nr of expansion block releases */ |
| thr->numpblk--; /* Total number of blocks */ |
| KMP_DEBUG_ASSERT(thr->numpblk == thr->numpget - thr->numprel); |
| } |
| #endif /* BufStats */ |
| |
| /* Deallocate bget_data */ |
| if ( th->th.th_local.bget_data != NULL ) { |
| __kmp_free( th->th.th_local.bget_data ); |
| th->th.th_local.bget_data = NULL; |
| }; // if |
| } |
| |
| void |
| kmpc_set_poolsize( size_t size ) |
| { |
| bectl( __kmp_get_thread(), (bget_compact_t) 0, (bget_acquire_t) malloc, |
| (bget_release_t) free, (bufsize) size ); |
| } |
| |
| size_t |
| kmpc_get_poolsize( void ) |
| { |
| thr_data_t *p; |
| |
| p = get_thr_data( __kmp_get_thread() ); |
| |
| return p->exp_incr; |
| } |
| |
| void |
| kmpc_set_poolmode( int mode ) |
| { |
| thr_data_t *p; |
| |
| if (mode == bget_mode_fifo || mode == bget_mode_lifo || mode == bget_mode_best) { |
| p = get_thr_data( __kmp_get_thread() ); |
| p->mode = (bget_mode_t) mode; |
| } |
| } |
| |
| int |
| kmpc_get_poolmode( void ) |
| { |
| thr_data_t *p; |
| |
| p = get_thr_data( __kmp_get_thread() ); |
| |
| return p->mode; |
| } |
| |
| void |
| kmpc_get_poolstat( size_t *maxmem, size_t *allmem ) |
| { |
| kmp_info_t *th = __kmp_get_thread(); |
| bufsize a, b; |
| |
| __kmp_bget_dequeue( th ); /* Release any queued buffers */ |
| |
| bcheck( th, &a, &b ); |
| |
| *maxmem = a; |
| *allmem = b; |
| } |
| |
| void |
| kmpc_poolprint( void ) |
| { |
| kmp_info_t *th = __kmp_get_thread(); |
| |
| __kmp_bget_dequeue( th ); /* Release any queued buffers */ |
| |
| bfreed( th ); |
| } |
| |
| #endif // #if KMP_USE_BGET |
| |
| /* ------------------------------------------------------------------------ */ |
| |
| void * |
| kmpc_malloc( size_t size ) |
| { |
| void * ptr; |
| ptr = bget( __kmp_entry_thread(), (bufsize)(size + sizeof(ptr)) ); |
| if( ptr != NULL ) { |
| // save allocated pointer just before one returned to user |
| *(void**)ptr = ptr; |
| ptr = (void**)ptr + 1; |
| } |
| return ptr; |
| } |
| |
| #define IS_POWER_OF_TWO(n) (((n)&((n)-1))==0) |
| |
| void * |
| kmpc_aligned_malloc( size_t size, size_t alignment ) |
| { |
| void * ptr; |
| void * ptr_allocated; |
| KMP_DEBUG_ASSERT( alignment < 32 * 1024 ); // Alignment should not be too big |
| if( !IS_POWER_OF_TWO(alignment) ) { |
| // AC: do we need to issue a warning here? |
| errno = EINVAL; |
| return NULL; |
| } |
| size = size + sizeof( void* ) + alignment; |
| ptr_allocated = bget( __kmp_entry_thread(), (bufsize)size ); |
| if( ptr_allocated != NULL ) { |
| // save allocated pointer just before one returned to user |
| ptr = (void*)(((kmp_uintptr_t)ptr_allocated + sizeof( void* ) + alignment) & ~(alignment - 1)); |
| *((void**)ptr - 1) = ptr_allocated; |
| } else { |
| ptr = NULL; |
| } |
| return ptr; |
| } |
| |
| void * |
| kmpc_calloc( size_t nelem, size_t elsize ) |
| { |
| void * ptr; |
| ptr = bgetz( __kmp_entry_thread(), (bufsize) (nelem * elsize + sizeof(ptr)) ); |
| if( ptr != NULL ) { |
| // save allocated pointer just before one returned to user |
| *(void**)ptr = ptr; |
| ptr = (void**)ptr + 1; |
| } |
| return ptr; |
| } |
| |
| void * |
| kmpc_realloc( void * ptr, size_t size ) |
| { |
| void * result = NULL; |
| if ( ptr == NULL ) { |
| // If pointer is NULL, realloc behaves like malloc. |
| result = bget( __kmp_entry_thread(), (bufsize)(size + sizeof(ptr)) ); |
| // save allocated pointer just before one returned to user |
| if( result != NULL ) { |
| *(void**)result = result; |
| result = (void**)result + 1; |
| } |
| } else if ( size == 0 ) { |
| // If size is 0, realloc behaves like free. |
| // The thread must be registered by the call to kmpc_malloc() or kmpc_calloc() before. |
| // So it should be safe to call __kmp_get_thread(), not __kmp_entry_thread(). |
| KMP_ASSERT(*((void**)ptr - 1)); |
| brel( __kmp_get_thread(), *((void**)ptr - 1) ); |
| } else { |
| result = bgetr( __kmp_entry_thread(), *((void**)ptr - 1), (bufsize)(size + sizeof(ptr)) ); |
| if( result != NULL ) { |
| *(void**)result = result; |
| result = (void**)result + 1; |
| } |
| }; // if |
| return result; |
| } |
| |
| /* NOTE: the library must have already been initialized by a previous allocate */ |
| |
| void |
| kmpc_free( void * ptr ) |
| { |
| if ( ! __kmp_init_serial ) { |
| return; |
| }; // if |
| if ( ptr != NULL ) { |
| kmp_info_t *th = __kmp_get_thread(); |
| __kmp_bget_dequeue( th ); /* Release any queued buffers */ |
| // extract allocated pointer and free it |
| KMP_ASSERT(*((void**)ptr - 1)); |
| brel( th, *((void**)ptr - 1) ); |
| }; |
| } |
| |
| |
| /* ------------------------------------------------------------------------ */ |
| |
| void * |
| ___kmp_thread_malloc( kmp_info_t *th, size_t size KMP_SRC_LOC_DECL ) |
| { |
| void * ptr; |
| KE_TRACE( 30, ( |
| "-> __kmp_thread_malloc( %p, %d ) called from %s:%d\n", |
| th, |
| (int) size |
| KMP_SRC_LOC_PARM |
| ) ); |
| ptr = bget( th, (bufsize) size ); |
| KE_TRACE( 30, ( "<- __kmp_thread_malloc() returns %p\n", ptr ) ); |
| return ptr; |
| } |
| |
| void * |
| ___kmp_thread_calloc( kmp_info_t *th, size_t nelem, size_t elsize KMP_SRC_LOC_DECL ) |
| { |
| void * ptr; |
| KE_TRACE( 30, ( |
| "-> __kmp_thread_calloc( %p, %d, %d ) called from %s:%d\n", |
| th, |
| (int) nelem, |
| (int) elsize |
| KMP_SRC_LOC_PARM |
| ) ); |
| ptr = bgetz( th, (bufsize) (nelem * elsize) ); |
| KE_TRACE( 30, ( "<- __kmp_thread_calloc() returns %p\n", ptr ) ); |
| return ptr; |
| } |
| |
| void * |
| ___kmp_thread_realloc( kmp_info_t *th, void *ptr, size_t size KMP_SRC_LOC_DECL ) |
| { |
| KE_TRACE( 30, ( |
| "-> __kmp_thread_realloc( %p, %p, %d ) called from %s:%d\n", |
| th, |
| ptr, |
| (int) size |
| KMP_SRC_LOC_PARM |
| ) ); |
| ptr = bgetr( th, ptr, (bufsize) size ); |
| KE_TRACE( 30, ( "<- __kmp_thread_realloc() returns %p\n", ptr ) ); |
| return ptr; |
| } |
| |
| void |
| ___kmp_thread_free( kmp_info_t *th, void *ptr KMP_SRC_LOC_DECL ) |
| { |
| KE_TRACE( 30, ( |
| "-> __kmp_thread_free( %p, %p ) called from %s:%d\n", |
| th, |
| ptr |
| KMP_SRC_LOC_PARM |
| ) ); |
| if ( ptr != NULL ) { |
| __kmp_bget_dequeue( th ); /* Release any queued buffers */ |
| brel( th, ptr ); |
| } |
| KE_TRACE( 30, ( "<- __kmp_thread_free()\n" ) ); |
| } |
| |
| /* ------------------------------------------------------------------------ */ |
| /* ------------------------------------------------------------------------ */ |
| /* |
| If LEAK_MEMORY is defined, __kmp_free() will *not* free memory. It causes memory leaks, but it |
| may be useful for debugging memory corruptions, used freed pointers, etc. |
| */ |
| /* #define LEAK_MEMORY */ |
| |
| struct kmp_mem_descr { // Memory block descriptor. |
| void * ptr_allocated; // Pointer returned by malloc(), subject for free(). |
| size_t size_allocated; // Size of allocated memory block. |
| void * ptr_aligned; // Pointer to aligned memory, to be used by client code. |
| size_t size_aligned; // Size of aligned memory block. |
| }; |
| typedef struct kmp_mem_descr kmp_mem_descr_t; |
| |
| /* |
| Allocate memory on requested boundary, fill allocated memory with 0x00. |
| NULL is NEVER returned, __kmp_abort() is called in case of memory allocation error. |
| Must use __kmp_free when freeing memory allocated by this routine! |
| */ |
| static |
| void * |
| ___kmp_allocate_align( size_t size, size_t alignment KMP_SRC_LOC_DECL ) |
| { |
| /* |
| __kmp_allocate() allocates (by call to malloc()) bigger memory block than requested to |
| return properly aligned pointer. Original pointer returned by malloc() and size of allocated |
| block is saved in descriptor just before the aligned pointer. This information used by |
| __kmp_free() -- it has to pass to free() original pointer, not aligned one. |
| |
| +---------+------------+-----------------------------------+---------+ |
| | padding | descriptor | aligned block | padding | |
| +---------+------------+-----------------------------------+---------+ |
| ^ ^ |
| | | |
| | +- Aligned pointer returned to caller |
| +- Pointer returned by malloc() |
| |
| Aligned block is filled with zeros, paddings are filled with 0xEF. |
| */ |
| |
| kmp_mem_descr_t descr; |
| kmp_uintptr_t addr_allocated; // Address returned by malloc(). |
| kmp_uintptr_t addr_aligned; // Aligned address to return to caller. |
| kmp_uintptr_t addr_descr; // Address of memory block descriptor. |
| |
| KE_TRACE( 25, ( |
| "-> ___kmp_allocate_align( %d, %d ) called from %s:%d\n", |
| (int) size, |
| (int) alignment |
| KMP_SRC_LOC_PARM |
| ) ); |
| |
| KMP_DEBUG_ASSERT( alignment < 32 * 1024 ); // Alignment should not be too |
| KMP_DEBUG_ASSERT( sizeof( void * ) <= sizeof( kmp_uintptr_t ) ); |
| // Make sure kmp_uintptr_t is enough to store addresses. |
| |
| descr.size_aligned = size; |
| descr.size_allocated = descr.size_aligned + sizeof( kmp_mem_descr_t ) + alignment; |
| |
| #if KMP_DEBUG |
| descr.ptr_allocated = _malloc_src_loc( descr.size_allocated, _file_, _line_ ); |
| #else |
| descr.ptr_allocated = malloc_src_loc( descr.size_allocated KMP_SRC_LOC_PARM ); |
| #endif |
| KE_TRACE( 10, ( |
| " malloc( %d ) returned %p\n", |
| (int) descr.size_allocated, |
| descr.ptr_allocated |
| ) ); |
| if ( descr.ptr_allocated == NULL ) { |
| KMP_FATAL( OutOfHeapMemory ); |
| }; |
| |
| addr_allocated = (kmp_uintptr_t) descr.ptr_allocated; |
| addr_aligned = |
| ( addr_allocated + sizeof( kmp_mem_descr_t ) + alignment ) |
| & ~ ( alignment - 1 ); |
| addr_descr = addr_aligned - sizeof( kmp_mem_descr_t ); |
| |
| descr.ptr_aligned = (void *) addr_aligned; |
| |
| KE_TRACE( 26, ( |
| " ___kmp_allocate_align: " |
| "ptr_allocated=%p, size_allocated=%d, " |
| "ptr_aligned=%p, size_aligned=%d\n", |
| descr.ptr_allocated, |
| (int) descr.size_allocated, |
| descr.ptr_aligned, |
| (int) descr.size_aligned |
| ) ); |
| |
| KMP_DEBUG_ASSERT( addr_allocated <= addr_descr ); |
| KMP_DEBUG_ASSERT( addr_descr + sizeof( kmp_mem_descr_t ) == addr_aligned ); |
| KMP_DEBUG_ASSERT( addr_aligned + descr.size_aligned <= addr_allocated + descr.size_allocated ); |
| KMP_DEBUG_ASSERT( addr_aligned % alignment == 0 ); |
| #ifdef KMP_DEBUG |
| memset( descr.ptr_allocated, 0xEF, descr.size_allocated ); |
| // Fill allocated memory block with 0xEF. |
| #endif |
| memset( descr.ptr_aligned, 0x00, descr.size_aligned ); |
| // Fill the aligned memory block (which is intended for using by caller) with 0x00. Do not |
| // put this filling under KMP_DEBUG condition! Many callers expect zeroed memory. (Padding |
| // bytes remain filled with 0xEF in debugging library.) |
| * ( (kmp_mem_descr_t *) addr_descr ) = descr; |
| |
| KMP_MB(); |
| |
| KE_TRACE( 25, ( "<- ___kmp_allocate_align() returns %p\n", descr.ptr_aligned ) ); |
| return descr.ptr_aligned; |
| } // func ___kmp_allocate_align |
| |
| |
| /* |
| Allocate memory on cache line boundary, fill allocated memory with 0x00. |
| Do not call this func directly! Use __kmp_allocate macro instead. |
| NULL is NEVER returned, __kmp_abort() is called in case of memory allocation error. |
| Must use __kmp_free when freeing memory allocated by this routine! |
| */ |
| void * |
| ___kmp_allocate( size_t size KMP_SRC_LOC_DECL ) |
| { |
| void * ptr; |
| KE_TRACE( 25, ( "-> __kmp_allocate( %d ) called from %s:%d\n", (int) size KMP_SRC_LOC_PARM ) ); |
| ptr = ___kmp_allocate_align( size, __kmp_align_alloc KMP_SRC_LOC_PARM ); |
| KE_TRACE( 25, ( "<- __kmp_allocate() returns %p\n", ptr ) ); |
| return ptr; |
| } // func ___kmp_allocate |
| |
| #if (BUILD_MEMORY==FIRST_TOUCH) |
| void * |
| __kmp_ft_page_allocate(size_t size) |
| { |
| void *adr, *aadr; |
| #if KMP_OS_LINUX |
| /* TODO: Use this function to get page size everywhere */ |
| int page_size = getpagesize(); |
| #else |
| /* TODO: Find windows function to get page size and use it everywhere */ |
| int page_size = PAGE_SIZE; |
| #endif /* KMP_OS_LINUX */ |
| |
| adr = (void *) __kmp_thread_malloc( __kmp_get_thread(), |
| size + page_size + KMP_PTR_SKIP); |
| if ( adr == 0 ) |
| KMP_FATAL( OutOfHeapMemory ); |
| |
| /* check to see if adr is on a page boundary. */ |
| if ( ( (kmp_uintptr_t) adr & (page_size - 1)) == 0) |
| /* nothing to do if adr is already on a page boundary. */ |
| aadr = adr; |
| else |
| /* else set aadr to the first page boundary in the allocated memory. */ |
| aadr = (void *) ( ( (kmp_uintptr_t) adr + page_size) & ~(page_size - 1) ); |
| |
| /* the first touch by the owner thread. */ |
| *((void**)aadr) = adr; |
| |
| /* skip the memory space used for storing adr above. */ |
| return (void*)((char*)aadr + KMP_PTR_SKIP); |
| } |
| #endif |
| |
| /* |
| Allocate memory on page boundary, fill allocated memory with 0x00. |
| Does not call this func directly! Use __kmp_page_allocate macro instead. |
| NULL is NEVER returned, __kmp_abort() is called in case of memory allocation error. |
| Must use __kmp_free when freeing memory allocated by this routine! |
| */ |
| void * |
| ___kmp_page_allocate( size_t size KMP_SRC_LOC_DECL ) |
| { |
| int page_size = 8 * 1024; |
| void * ptr; |
| |
| KE_TRACE( 25, ( |
| "-> __kmp_page_allocate( %d ) called from %s:%d\n", |
| (int) size |
| KMP_SRC_LOC_PARM |
| ) ); |
| ptr = ___kmp_allocate_align( size, page_size KMP_SRC_LOC_PARM ); |
| KE_TRACE( 25, ( "<- __kmp_page_allocate( %d ) returns %p\n", (int) size, ptr ) ); |
| return ptr; |
| } // ___kmp_page_allocate |
| |
| /* |
| Free memory allocated by __kmp_allocate() and __kmp_page_allocate(). |
| In debug mode, fill the memory block with 0xEF before call to free(). |
| */ |
| void |
| ___kmp_free( void * ptr KMP_SRC_LOC_DECL ) |
| { |
| kmp_mem_descr_t descr; |
| kmp_uintptr_t addr_allocated; // Address returned by malloc(). |
| kmp_uintptr_t addr_aligned; // Aligned address passed by caller. |
| |
| KE_TRACE( 25, ( "-> __kmp_free( %p ) called from %s:%d\n", ptr KMP_SRC_LOC_PARM ) ); |
| KMP_ASSERT( ptr != NULL ); |
| |
| descr = * ( kmp_mem_descr_t *) ( (kmp_uintptr_t) ptr - sizeof( kmp_mem_descr_t ) ); |
| |
| KE_TRACE( 26, ( " __kmp_free: " |
| "ptr_allocated=%p, size_allocated=%d, " |
| "ptr_aligned=%p, size_aligned=%d\n", |
| descr.ptr_allocated, (int) descr.size_allocated, |
| descr.ptr_aligned, (int) descr.size_aligned )); |
| |
| addr_allocated = (kmp_uintptr_t) descr.ptr_allocated; |
| addr_aligned = (kmp_uintptr_t) descr.ptr_aligned; |
| |
| KMP_DEBUG_ASSERT( addr_aligned % CACHE_LINE == 0 ); |
| KMP_DEBUG_ASSERT( descr.ptr_aligned == ptr ); |
| KMP_DEBUG_ASSERT( addr_allocated + sizeof( kmp_mem_descr_t ) <= addr_aligned ); |
| KMP_DEBUG_ASSERT( descr.size_aligned < descr.size_allocated ); |
| KMP_DEBUG_ASSERT( addr_aligned + descr.size_aligned <= addr_allocated + descr.size_allocated ); |
| |
| #ifdef KMP_DEBUG |
| memset( descr.ptr_allocated, 0xEF, descr.size_allocated ); |
| // Fill memory block with 0xEF, it helps catch using freed memory. |
| #endif |
| |
| #ifndef LEAK_MEMORY |
| KE_TRACE( 10, ( " free( %p )\n", descr.ptr_allocated ) ); |
| # ifdef KMP_DEBUG |
| _free_src_loc( descr.ptr_allocated, _file_, _line_ ); |
| # else |
| free_src_loc( descr.ptr_allocated KMP_SRC_LOC_PARM ); |
| # endif |
| #endif |
| KMP_MB(); |
| KE_TRACE( 25, ( "<- __kmp_free() returns\n" ) ); |
| } // func ___kmp_free |
| |
| /* ------------------------------------------------------------------------ */ |
| /* ------------------------------------------------------------------------ */ |
| |
| #if USE_FAST_MEMORY == 3 |
| // Allocate fast memory by first scanning the thread's free lists |
| // If a chunk the right size exists, grab it off the free list. |
| // Otherwise allocate normally using kmp_thread_malloc. |
| |
| // AC: How to choose the limit? Just get 16 for now... |
| #define KMP_FREE_LIST_LIMIT 16 |
| |
| // Always use 128 bytes for determining buckets for caching memory blocks |
| #define DCACHE_LINE 128 |
| |
| void * |
| ___kmp_fast_allocate( kmp_info_t *this_thr, size_t size KMP_SRC_LOC_DECL ) |
| { |
| void * ptr; |
| int num_lines; |
| int idx; |
| int index; |
| void * alloc_ptr; |
| size_t alloc_size; |
| kmp_mem_descr_t * descr; |
| |
| KE_TRACE( 25, ( "-> __kmp_fast_allocate( T#%d, %d ) called from %s:%d\n", |
| __kmp_gtid_from_thread(this_thr), (int) size KMP_SRC_LOC_PARM ) ); |
| |
| num_lines = ( size + DCACHE_LINE - 1 ) / DCACHE_LINE; |
| idx = num_lines - 1; |
| KMP_DEBUG_ASSERT( idx >= 0 ); |
| if ( idx < 2 ) { |
| index = 0; // idx is [ 0, 1 ], use first free list |
| num_lines = 2; // 1, 2 cache lines or less than cache line |
| } else if ( ( idx >>= 2 ) == 0 ) { |
| index = 1; // idx is [ 2, 3 ], use second free list |
| num_lines = 4; // 3, 4 cache lines |
| } else if ( ( idx >>= 2 ) == 0 ) { |
| index = 2; // idx is [ 4, 15 ], use third free list |
| num_lines = 16; // 5, 6, ..., 16 cache lines |
| } else if ( ( idx >>= 2 ) == 0 ) { |
| index = 3; // idx is [ 16, 63 ], use fourth free list |
| num_lines = 64; // 17, 18, ..., 64 cache lines |
| } else { |
| goto alloc_call; // 65 or more cache lines ( > 8KB ), don't use free lists |
| } |
| |
| ptr = this_thr->th.th_free_lists[index].th_free_list_self; |
| if ( ptr != NULL ) { |
| // pop the head of no-sync free list |
| this_thr->th.th_free_lists[index].th_free_list_self = *((void **)ptr); |
| KMP_DEBUG_ASSERT( this_thr == |
| ((kmp_mem_descr_t *)( (kmp_uintptr_t)ptr - sizeof(kmp_mem_descr_t) ))->ptr_aligned ); |
| goto end; |
| }; |
| ptr = TCR_SYNC_PTR( this_thr->th.th_free_lists[index].th_free_list_sync ); |
| if ( ptr != NULL ) { |
| // no-sync free list is empty, use sync free list (filled in by other threads only) |
| // pop the head of the sync free list, push NULL instead |
| while ( ! KMP_COMPARE_AND_STORE_PTR( |
| &this_thr->th.th_free_lists[index].th_free_list_sync, ptr, NULL ) ) |
| { |
| KMP_CPU_PAUSE(); |
| ptr = TCR_SYNC_PTR( this_thr->th.th_free_lists[index].th_free_list_sync ); |
| } |
| // push the rest of chain into no-sync free list (can be NULL if there was the only block) |
| this_thr->th.th_free_lists[index].th_free_list_self = *((void **)ptr); |
| KMP_DEBUG_ASSERT( this_thr == |
| ((kmp_mem_descr_t *)( (kmp_uintptr_t)ptr - sizeof(kmp_mem_descr_t) ))->ptr_aligned ); |
| goto end; |
| } |
| |
| alloc_call: |
| // haven't found block in the free lists, thus allocate it |
| size = num_lines * DCACHE_LINE; |
| |
| alloc_size = size + sizeof( kmp_mem_descr_t ) + DCACHE_LINE; |
| KE_TRACE( 25, ( "__kmp_fast_allocate: T#%d Calling __kmp_thread_malloc with alloc_size %d\n", |
| __kmp_gtid_from_thread( this_thr ), alloc_size ) ); |
| alloc_ptr = bget( this_thr, (bufsize) alloc_size ); |
| |
| // align ptr to DCACHE_LINE |
| ptr = (void *)(( ((kmp_uintptr_t)alloc_ptr) + sizeof(kmp_mem_descr_t) + DCACHE_LINE ) & ~( DCACHE_LINE - 1 )); |
| descr = (kmp_mem_descr_t *)( ((kmp_uintptr_t)ptr) - sizeof(kmp_mem_descr_t) ); |
| |
| descr->ptr_allocated = alloc_ptr; // remember allocated pointer |
| // we don't need size_allocated |
| descr->ptr_aligned = (void *)this_thr; // remember allocating thread |
| // (it is already saved in bget buffer, |
| // but we may want to use another allocator in future) |
| descr->size_aligned = size; |
| |
| end: |
| KE_TRACE( 25, ( "<- __kmp_fast_allocate( T#%d ) returns %p\n", |
| __kmp_gtid_from_thread( this_thr ), ptr ) ); |
| return ptr; |
| } // func __kmp_fast_allocate |
| |
| // Free fast memory and place it on the thread's free list if it is of |
| // the correct size. |
| void |
| ___kmp_fast_free( kmp_info_t *this_thr, void * ptr KMP_SRC_LOC_DECL ) |
| { |
| kmp_mem_descr_t * descr; |
| kmp_info_t * alloc_thr; |
| size_t size; |
| size_t idx; |
| int index; |
| |
| KE_TRACE( 25, ( "-> __kmp_fast_free( T#%d, %p ) called from %s:%d\n", |
| __kmp_gtid_from_thread(this_thr), ptr KMP_SRC_LOC_PARM ) ); |
| KMP_ASSERT( ptr != NULL ); |
| |
| descr = (kmp_mem_descr_t *)( ((kmp_uintptr_t)ptr) - sizeof(kmp_mem_descr_t) ); |
| |
| KE_TRACE(26, (" __kmp_fast_free: size_aligned=%d\n", |
| (int) descr->size_aligned ) ); |
| |
| size = descr->size_aligned; // 2, 4, 16, 64, 65, 66, ... cache lines |
| |
| idx = DCACHE_LINE * 2; // 2 cache lines is minimal size of block |
| if ( idx == size ) { |
| index = 0; // 2 cache lines |
| } else if ( ( idx <<= 1 ) == size ) { |
| index = 1; // 4 cache lines |
| } else if ( ( idx <<= 2 ) == size ) { |
| index = 2; // 16 cache lines |
| } else if ( ( idx <<= 2 ) == size ) { |
| index = 3; // 64 cache lines |
| } else { |
| KMP_DEBUG_ASSERT( size > DCACHE_LINE * 64 ); |
| goto free_call; // 65 or more cache lines ( > 8KB ) |
| } |
| |
| alloc_thr = (kmp_info_t *)descr->ptr_aligned; // get thread owning the block |
| if ( alloc_thr == this_thr ) { |
| // push block to self no-sync free list, linking previous head (LIFO) |
| *((void **)ptr) = this_thr->th.th_free_lists[index].th_free_list_self; |
| this_thr->th.th_free_lists[index].th_free_list_self = ptr; |
| } else { |
| void * head = this_thr->th.th_free_lists[index].th_free_list_other; |
| if ( head == NULL ) { |
| // Create new free list |
| this_thr->th.th_free_lists[index].th_free_list_other = ptr; |
| *((void **)ptr) = NULL; // mark the tail of the list |
| descr->size_allocated = (size_t)1; // head of the list keeps its length |
| } else { |
| // need to check existed "other" list's owner thread and size of queue |
| kmp_mem_descr_t * dsc = (kmp_mem_descr_t *)( (char*)head - sizeof(kmp_mem_descr_t) ); |
| kmp_info_t * q_th = (kmp_info_t *)(dsc->ptr_aligned); // allocating thread, same for all queue nodes |
| size_t q_sz = dsc->size_allocated + 1; // new size in case we add current task |
| if ( q_th == alloc_thr && q_sz <= KMP_FREE_LIST_LIMIT ) { |
| // we can add current task to "other" list, no sync needed |
| *((void **)ptr) = head; |
| descr->size_allocated = q_sz; |
| this_thr->th.th_free_lists[index].th_free_list_other = ptr; |
| } else { |
| // either queue blocks owner is changing or size limit exceeded |
| // return old queue to allocating thread (q_th) synchroneously, |
| // and start new list for alloc_thr's tasks |
| void * old_ptr; |
| void * tail = head; |
| void * next = *((void **)head); |
| while ( next != NULL ) { |
| KMP_DEBUG_ASSERT( |
| // queue size should decrease by 1 each step through the list |
| ((kmp_mem_descr_t*)((char*)next - sizeof(kmp_mem_descr_t)))->size_allocated + 1 == |
| ((kmp_mem_descr_t*)((char*)tail - sizeof(kmp_mem_descr_t)))->size_allocated ); |
| tail = next; // remember tail node |
| next = *((void **)next); |
| } |
| KMP_DEBUG_ASSERT( q_th != NULL ); |
| // push block to owner's sync free list |
| old_ptr = TCR_PTR( q_th->th.th_free_lists[index].th_free_list_sync ); |
| /* the next pointer must be set before setting free_list to ptr to avoid |
| exposing a broken list to other threads, even for an instant. */ |
| *((void **)tail) = old_ptr; |
| |
| while ( ! KMP_COMPARE_AND_STORE_PTR( |
| &q_th->th.th_free_lists[index].th_free_list_sync, |
| old_ptr, |
| head ) ) |
| { |
| KMP_CPU_PAUSE(); |
| old_ptr = TCR_PTR( q_th->th.th_free_lists[index].th_free_list_sync ); |
| *((void **)tail) = old_ptr; |
| } |
| |
| // start new list of not-selt tasks |
| this_thr->th.th_free_lists[index].th_free_list_other = ptr; |
| *((void **)ptr) = NULL; |
| descr->size_allocated = (size_t)1; // head of queue keeps its length |
| } |
| } |
| } |
| goto end; |
| |
| free_call: |
| KE_TRACE(25, ( "__kmp_fast_free: T#%d Calling __kmp_thread_free for size %d\n", |
| __kmp_gtid_from_thread( this_thr), size ) ); |
| __kmp_bget_dequeue( this_thr ); /* Release any queued buffers */ |
| brel( this_thr, descr->ptr_allocated ); |
| |
| end: |
| KE_TRACE( 25, ( "<- __kmp_fast_free() returns\n" ) ); |
| |
| } // func __kmp_fast_free |
| |
| |
| // Initialize the thread free lists related to fast memory |
| // Only do this when a thread is initially created. |
| void |
| __kmp_initialize_fast_memory( kmp_info_t *this_thr ) |
| { |
| KE_TRACE(10, ( "__kmp_initialize_fast_memory: Called from th %p\n", this_thr ) ); |
| |
| memset ( this_thr->th.th_free_lists, 0, NUM_LISTS * sizeof( kmp_free_list_t ) ); |
| } |
| |
| // Free the memory in the thread free lists related to fast memory |
| // Only do this when a thread is being reaped (destroyed). |
| void |
| __kmp_free_fast_memory( kmp_info_t *th ) |
| { |
| // Suppose we use BGET underlying allocator, walk through its structures... |
| int bin; |
| thr_data_t * thr = get_thr_data( th ); |
| void ** lst = NULL; |
| |
| KE_TRACE(5, ( "__kmp_free_fast_memory: Called T#%d\n", |
| __kmp_gtid_from_thread( th ) ) ); |
| |
| __kmp_bget_dequeue( th ); // Release any queued buffers |
| |
| // Dig through free lists and extract all allocated blocks |
| for ( bin = 0; bin < MAX_BGET_BINS; ++bin ) { |
| bfhead_t * b = thr->freelist[ bin ].ql.flink; |
| while ( b != &thr->freelist[ bin ] ) { |
| if ( (kmp_uintptr_t)b->bh.bb.bthr & 1 ) { // if the buffer is an allocated address? |
| *((void**)b) = lst; // link the list (override bthr, but keep flink yet) |
| lst = (void**)b; // push b into lst |
| } |
| b = b->ql.flink; // get next buffer |
| } |
| } |
| while ( lst != NULL ) { |
| void * next = *lst; |
| KE_TRACE(10, ( "__kmp_free_fast_memory: freeing %p, next=%p th %p (%d)\n", |
| lst, next, th, __kmp_gtid_from_thread( th ) ) ); |
| (*thr->relfcn)(lst); |
| #if BufStats |
| // count blocks to prevent problems in __kmp_finalize_bget() |
| thr->numprel++; /* Nr of expansion block releases */ |
| thr->numpblk--; /* Total number of blocks */ |
| #endif |
| lst = (void**)next; |
| } |
| |
| KE_TRACE(5, ( "__kmp_free_fast_memory: Freed T#%d\n", |
| __kmp_gtid_from_thread( th ) ) ); |
| } |
| |
| #endif // USE_FAST_MEMORY |