3
A brief file description
5
@section license License
7
Licensed to the Apache Software Foundation (ASF) under one
8
or more contributor license agreements. See the NOTICE file
9
distributed with this work for additional information
10
regarding copyright ownership. The ASF licenses this file
11
to you under the Apache License, Version 2.0 (the
12
"License"); you may not use this file except in compliance
13
with the License. You may obtain a copy of the License at
15
http://www.apache.org/licenses/LICENSE-2.0
17
Unless required by applicable law or agreed to in writing, software
18
distributed under the License is distributed on an "AS IS" BASIS,
19
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
20
See the License for the specific language governing permissions and
21
limitations under the License.
24
/*****************************************************************************
25
ink_queue.cc (This used to be ink_queue.c)
27
This implements an atomic push/pop queue, and the freelist memory
28
pools that are built from it.
30
The change from ink_queue.cc to ink_queue.c resulted in some changes
31
in access and store of 64 bit values. This is standardized by using
32
the INK_QUEUE_LD64 macro which loads the version before the pointer
33
(independent of endianness of native architecture) on 32 bit platforms
34
or loads the 64 bit quantity directory on the DECs.
37
****************************************************************************/
39
#include "ink_config.h"
43
#include <sys/types.h>
45
#include "ink_atomic.h"
46
#include "ink_queue.h"
47
#include "ink_memory.h"
48
#include "ink_error.h"
49
#include "ink_assert.h"
50
#include "ink_resource.h"
54
#define INK_QUEUE_LD64(dst,src) *((uint64_t*)&(dst)) = *((uint64_t*)&(src))
56
#define INK_QUEUE_LD64(dst,src) (ink_queue_load_64((void *)&(dst), (void *)&(src)))
59
typedef struct _ink_freelist_list
62
struct _ink_freelist_list *next;
66
inkcoreapi volatile int64_t fastalloc_mem_in_use = 0;
67
inkcoreapi volatile int64_t fastalloc_mem_total = 0;
70
* SANITY and DEADBEEF are compute-intensive memory debugging to
71
* help in diagnosing freelist corruption. We turn them off in
80
// #define MEMPROTECT 1
82
#define MEMPROTECT_SIZE 0x200
85
static const int page_size = 8192; /* sysconf (_SC_PAGESIZE); */
88
static ink_freelist_list *freelists = NULL;
90
inkcoreapi volatile int64_t freelist_allocated_mem = 0;
92
#define fl_memadd(_x_) \
93
ink_atomic_increment64(&freelist_allocated_mem, (int64_t) (_x_));
95
//static void ink_queue_load_64(void *dst, void *src)
97
// int32_t src_version = (*(head_p *) src).s.version;
98
// void *src_pointer = (*(head_p *) src).s.pointer;
100
// (*(head_p *) dst).s.version = src_version;
101
// (*(head_p *) dst).s.pointer = src_pointer;
106
ink_freelist_init(InkFreeList * f,
107
const char *name, uint32_t type_size, uint32_t chunk_size, uint32_t offset, uint32_t alignment)
109
ink_freelist_list *fll;
111
/* its safe to add to this global list because ink_freelist_init()
112
is only called from single-threaded initialization code. */
113
if ((fll = (ink_freelist_list *) ink_malloc(sizeof(ink_freelist_list))) != 0) {
115
fll->next = freelists;
118
ink_assert(fll != NULL);
122
/* quick test for power of 2 */
123
ink_assert(!(alignment & (alignment - 1)));
124
f->alignment = alignment;
125
f->chunk_size = chunk_size;
126
f->type_size = type_size;
127
#if defined(INK_USE_MUTEX_FOR_FREELISTS)
128
ink_mutex_init(&(f->inkfreelist_mutex), name);
130
#if (defined(USE_SPINLOCK_FOR_FREELIST) || defined(CHECK_FOR_DOUBLE_FREE))
131
ink_mutex_init(&(f->freelist_mutex), name);
133
#ifdef CHECK_FOR_DOUBLE_FREE
137
SET_FREELIST_POINTER_VERSION(f->head, FROM_PTR(0), 0);
142
f->allocated_base = 0;
147
ink_freelist_create(const char *name, uint32_t type_size, uint32_t chunk_size, uint32_t offset, uint32_t alignment)
149
InkFreeList *f = ink_type_malloc(InkFreeList);
150
ink_freelist_init(f, name, type_size, chunk_size, offset, alignment);
154
#define ADDRESS_OF_NEXT(x, offset) ((void **)((char *)x + offset))
157
int fake_global_for_ink_queue = 0;
160
int fastmemtotal = 0;
162
#if defined(INK_USE_MUTEX_FOR_FREELISTS)
164
ink_freelist_new_wrap(InkFreeList * f)
165
#else /* !INK_USE_MUTEX_FOR_FREELISTS */
167
ink_freelist_new(InkFreeList * f)
168
#endif /* !INK_USE_MUTEX_FOR_FREELISTS */
169
{ //static uint32_t cntf = 0;
171
#if (defined(USE_SPINLOCK_FOR_FREELIST) || defined(CHECK_FOR_DOUBLE_FREE))
173
uint32_t type_size = f->type_size;
175
ink_mutex_acquire(&(f->freelist_mutex));
176
ink_assert(f->type_size != 0);
178
//printf("ink_freelist_new %d - %d - %u\n",f ->type_size,(f->head != NULL) ? 1 : 0,cntf++);
181
if (f->head != NULL) {
183
* We have something on the free list..
185
void_p *h = (void_p *) f->head;
186
#ifdef CHECK_FOR_DOUBLE_FREE
187
if (f->head == f->tail)
189
#endif /* CHECK_FOR_DOUBLE_FREE */
192
f->head = (volatile void_p *) *h;
194
ink_mutex_release(&(f->freelist_mutex));
198
* Might as well unlock the freelist mutex, since
199
* we're just going to do a malloc now..
204
if (type_size >= MEMPROTECT_SIZE) {
205
if (f->alignment < page_size)
206
f->alignment = page_size;
207
type_size = ((type_size + page_size - 1) / page_size) * page_size * 2;
209
#endif /* MEMPROTECT */
211
alignment = f->alignment;
212
ink_mutex_release(&(f->freelist_mutex));
215
foo = ink_memalign(alignment, type_size);
217
foo = ink_malloc(type_size);
220
fl_memadd(type_size);
224
if (type_size >= MEMPROTECT_SIZE) {
225
if (mprotect((char *) foo + type_size - page_size, page_size, PROT_NONE) < 0)
228
#endif /* MEMPROTECT */
232
#else /* #if (defined(USE_SPINLOCK_FOR_FREELIST) || defined(CHECK_FOR_DOUBLE_FREE)) */
237
//printf("ink_freelist_new %d - %d - %u\n",f ->type_size,(f->head != NULL) ? 1 : 0,cntf++);
241
INK_QUEUE_LD64(item, f->head);
242
if (TO_PTR(FREELIST_POINTER(item)) == NULL) {
243
uint32_t type_size = f->type_size;
247
if (type_size >= MEMPROTECT_SIZE) {
248
if (f->alignment < page_size)
249
f->alignment = page_size;
250
type_size = ((type_size + page_size - 1) / page_size) * page_size * 2;
252
#endif /* MEMPROTECT */
257
char *oldsbrk = (char *) sbrk(0), *newsbrk = NULL;
260
newp = ink_memalign(f->alignment, f->chunk_size * type_size);
262
newp = ink_malloc(f->chunk_size * type_size);
264
fl_memadd(f->chunk_size * type_size);
266
newsbrk = (char *) sbrk(0);
267
ink_atomic_increment(&fastmemtotal, newsbrk - oldsbrk);
268
/* printf("fastmem %d, %d, %d\n", f->chunk_size * type_size,
269
newsbrk - oldsbrk, fastmemtotal); */
271
SET_FREELIST_POINTER_VERSION(item, newp, 0);
276
add = f->alignment - 1;
277
mask = ~(uintptr_t) add;
282
newp = ink_malloc(f->chunk_size * type_size + add);
284
fl_memadd(f->chunk_size * type_size + add);
285
newp = (void *) ((((uintptr_t) newp) + add) & mask);
286
SET_FREELIST_POINTER_VERSION(item, newp, 0);
289
#if !defined(INK_USE_MUTEX_FOR_FREELISTS)
290
ink_atomic_increment((int *) &f->allocated, f->chunk_size);
291
ink_atomic_increment64(&fastalloc_mem_total, (int64_t) f->chunk_size * f->type_size);
293
f->allocated += f->chunk_size;
294
fastalloc_mem_total += f->chunk_size * f->type_size;
297
/* free each of the new elements */
298
for (i = 0; i < f->chunk_size; i++) {
299
char *a = ((char *) FREELIST_POINTER(item)) + i * type_size;
301
memset(a, 0xDEADCAFE, type_size);
303
ink_freelist_free(f, a);
305
if (f->type_size >= MEMPROTECT_SIZE) {
306
a += type_size - page_size;
307
if (mprotect(a, page_size, PROT_NONE) < 0)
310
#endif /* MEMPROTECT */
313
#if !defined(INK_USE_MUTEX_FOR_FREELISTS)
314
ink_atomic_increment((int *) &f->count, f->chunk_size);
315
ink_atomic_increment64(&fastalloc_mem_in_use, (int64_t) f->chunk_size * f->type_size);
317
f->count += f->chunk_size;
318
fastalloc_mem_in_use += f->chunk_size * f->type_size;
322
SET_FREELIST_POINTER_VERSION(next, *ADDRESS_OF_NEXT(TO_PTR(FREELIST_POINTER(item)), f->offset),
323
FREELIST_VERSION(item) + 1);
324
#if !defined(INK_USE_MUTEX_FOR_FREELISTS)
325
result = ink_atomic_cas64((int64_t *) & f->head.data, item.data, next.data);
327
f->head.data = next.data;
333
if (FREELIST_POINTER(item) == TO_PTR(FREELIST_POINTER(next)))
334
ink_fatal(1, "ink_freelist_new: loop detected");
335
if (((uintptr_t) (TO_PTR(FREELIST_POINTER(next)))) & 3)
336
ink_fatal(1, "ink_freelist_new: bad list");
337
if (TO_PTR(FREELIST_POINTER(next)))
338
fake_global_for_ink_queue = *(int *) TO_PTR(FREELIST_POINTER(next));
345
ink_assert(!((uintptr_t)TO_PTR(FREELIST_POINTER(item))&(((uintptr_t)f->alignment)-1)));
347
ink_atomic_increment((int *) &f->count, 1);
348
ink_atomic_increment64(&fastalloc_mem_in_use, (int64_t) f->type_size);
350
return TO_PTR(FREELIST_POINTER(item));
351
#endif /* #if (defined(USE_SPINLOCK_FOR_FREELIST) || defined(CHECK_FOR_DOUBLE_FREE)) */
353
typedef volatile void *volatile_void_p;
355
#if defined(INK_USE_MUTEX_FOR_FREELISTS)
357
ink_freelist_free_wrap(InkFreeList * f, void *item)
358
#else /* !INK_USE_MUTEX_FOR_FREELISTS */
360
ink_freelist_free(InkFreeList * f, void *item)
361
#endif /* !INK_USE_MUTEX_FOR_FREELISTS */
363
#if (defined(USE_SPINLOCK_FOR_FREELIST) || defined(CHECK_FOR_DOUBLE_FREE))
366
//printf("ink_freelist_free\n");
367
ink_mutex_acquire(&(f->freelist_mutex));
369
foo = (void_p *) item;
370
#ifdef CHECK_FOR_DOUBLE_FREE
371
void_p *p = (void_p *) f->head;
373
if (p == (void_p *) item)
374
ink_release_assert(!"ink_freelist_free: Double free");
380
*foo = (void_p) NULL;
386
*foo = (void_p) f->head;
391
ink_mutex_release(&(f->freelist_mutex));
394
volatile_void_p *adr_of_next = (volatile_void_p *) ADDRESS_OF_NEXT(item, f->offset);
399
// ink_assert(!((long)item&(f->alignment-1))); XXX - why is this no longer working? -bcall
403
// set string to DEADBEEF
404
const char str[4] = { (char) 0xde, (char) 0xad, (char) 0xbe, (char) 0xef };
406
// search for DEADBEEF anywhere after a pointer offset in the item
407
char *position = (char *) item + sizeof(void *); // start
408
char *end = (char *) item + f->type_size; // end
411
for (i = sizeof(void *) & 0x3, j = 0; position < end; ++position) {
413
if (*position == str[i]) {
415
ink_fatal(1, "ink_freelist_free: trying to free item twice");
424
// set the entire item to DEADBEEF
425
memset(item, 0xDEADBEEF, f->type_size);
427
#endif /* DEADBEEF */
431
INK_QUEUE_LD64(h, f->head);
433
if (TO_PTR(FREELIST_POINTER(h)) == item)
434
ink_fatal(1, "ink_freelist_free: trying to free item twice");
435
if (((uintptr_t) (TO_PTR(FREELIST_POINTER(h)))) & 3)
436
ink_fatal(1, "ink_freelist_free: bad list");
437
if (TO_PTR(FREELIST_POINTER(h)))
438
fake_global_for_ink_queue = *(int *) TO_PTR(FREELIST_POINTER(h));
440
*adr_of_next = FREELIST_POINTER(h);
441
SET_FREELIST_POINTER_VERSION(item_pair, FROM_PTR(item), FREELIST_VERSION(h));
443
#if !defined(INK_USE_MUTEX_FOR_FREELISTS)
444
result = ink_atomic_cas64((int64_t *) & f->head, h.data, item_pair.data);
446
f->head.data = item_pair.data;
453
ink_atomic_increment((int *) &f->count, -1);
454
ink_atomic_increment64(&fastalloc_mem_in_use, -(int64_t) f->type_size);
459
ink_freelists_snap_baseline()
461
ink_freelist_list *fll;
464
fll->fl->allocated_base = fll->fl->allocated;
465
fll->fl->count_base = fll->fl->count;
471
ink_freelists_dump_baselinerel(FILE * f)
473
ink_freelist_list *fll;
477
fprintf(f, " allocated | in-use | count | type size | free list name\n");
478
fprintf(f, "rel. to base|rel. to base| | | \n");
479
fprintf(f, "------------|------------|---------|------------|----------------------------------\n");
483
int a = fll->fl->allocated - fll->fl->allocated_base;
485
fprintf(f, " %10u | %10u | %7u | %10u | memory/%s\n",
486
(fll->fl->allocated - fll->fl->allocated_base) * fll->fl->type_size,
487
(fll->fl->count - fll->fl->count_base) * fll->fl->type_size,
488
fll->fl->count - fll->fl->count_base, fll->fl->type_size, fll->fl->name ? fll->fl->name : "<unknown>");
495
ink_freelists_dump(FILE * f)
497
ink_freelist_list *fll;
501
fprintf(f, " allocated | in-use | type size | free list name\n");
502
fprintf(f, "------------|------------|------------|----------------------------------\n");
506
fprintf(f, " %10u | %10u | %10u | memory/%s\n",
507
fll->fl->allocated * fll->fl->type_size,
508
fll->fl->count * fll->fl->type_size, fll->fl->type_size, fll->fl->name ? fll->fl->name : "<unknown>");
514
#define INK_FREELIST_CREATE(T, n) \
515
ink_freelist_create("<unknown>", sizeof(T), n, (uintptr_t)&((T *)0)->next, 4)
518
ink_atomiclist_init(InkAtomicList * l, const char *name, uint32_t offset_to_next)
520
#if defined(INK_USE_MUTEX_FOR_ATOMICLISTS)
521
ink_mutex_init(&(l->inkatomiclist_mutex), name);
524
l->offset = offset_to_next;
525
SET_FREELIST_POINTER_VERSION(l->head, FROM_PTR(0), 0);
528
#if defined(INK_USE_MUTEX_FOR_ATOMICLISTS)
530
ink_atomiclist_pop_wrap(InkAtomicList * l)
531
#else /* !INK_USE_MUTEX_FOR_ATOMICLISTS */
533
ink_atomiclist_pop(InkAtomicList * l)
534
#endif /* !INK_USE_MUTEX_FOR_ATOMICLISTS */
540
INK_QUEUE_LD64(item, l->head);
541
if (TO_PTR(FREELIST_POINTER(item)) == NULL)
543
SET_FREELIST_POINTER_VERSION(next, *ADDRESS_OF_NEXT(TO_PTR(FREELIST_POINTER(item)), l->offset),
544
FREELIST_VERSION(item) + 1);
545
#if !defined(INK_USE_MUTEX_FOR_ATOMICLISTS)
546
result = ink_atomic_cas64((int64_t *) & l->head.data, item.data, next.data);
548
l->head.data = next.data;
555
void *ret = TO_PTR(FREELIST_POINTER(item));
556
*ADDRESS_OF_NEXT(ret, l->offset) = NULL;
561
#if defined(INK_USE_MUTEX_FOR_ATOMICLISTS)
563
ink_atomiclist_popall_wrap(InkAtomicList * l)
564
#else /* !INK_USE_MUTEX_FOR_ATOMICLISTS */
566
ink_atomiclist_popall(InkAtomicList * l)
567
#endif /* !INK_USE_MUTEX_FOR_ATOMICLISTS */
573
INK_QUEUE_LD64(item, l->head);
574
if (TO_PTR(FREELIST_POINTER(item)) == NULL)
576
SET_FREELIST_POINTER_VERSION(next, FROM_PTR(NULL), FREELIST_VERSION(item) + 1);
577
#if !defined(INK_USE_MUTEX_FOR_ATOMICLISTS)
578
result = ink_atomic_cas64((int64_t *) & l->head.data, item.data, next.data);
580
l->head.data = next.data;
587
void *ret = TO_PTR(FREELIST_POINTER(item));
589
/* fixup forward pointers */
591
void *n = TO_PTR(*ADDRESS_OF_NEXT(e, l->offset));
592
*ADDRESS_OF_NEXT(e, l->offset) = n;
599
#if defined(INK_USE_MUTEX_FOR_ATOMICLISTS)
601
ink_atomiclist_push_wrap(InkAtomicList * l, void *item)
602
#else /* !INK_USE_MUTEX_FOR_ATOMICLISTS */
604
ink_atomiclist_push(InkAtomicList * l, void *item)
605
#endif /* !INK_USE_MUTEX_FOR_ATOMICLISTS */
607
volatile_void_p *adr_of_next = (volatile_void_p *) ADDRESS_OF_NEXT(item, l->offset);
612
ink_assert(*adr_of_next == NULL);
614
INK_QUEUE_LD64(head, l->head);
615
h = FREELIST_POINTER(head);
617
ink_assert(item != TO_PTR(h));
618
SET_FREELIST_POINTER_VERSION(item_pair, FROM_PTR(item), FREELIST_VERSION(head));
620
#if !defined(INK_USE_MUTEX_FOR_ATOMICLISTS)
621
result = ink_atomic_cas64((int64_t *) & l->head, head.data, item_pair.data);
623
l->head.data = item_pair.data;
633
#if defined(INK_USE_MUTEX_FOR_ATOMICLISTS)
635
ink_atomiclist_remove_wrap(InkAtomicList * l, void *item)
636
#else /* !INK_USE_MUTEX_FOR_ATOMICLISTS */
638
ink_atomiclist_remove(InkAtomicList * l, void *item)
639
#endif /* !INK_USE_MUTEX_FOR_ATOMICLISTS */
643
void **addr_next = ADDRESS_OF_NEXT(item, l->offset);
644
void *item_next = *addr_next;
648
* first, try to pop it if it is first
650
INK_QUEUE_LD64(head, l->head);
651
while (TO_PTR(FREELIST_POINTER(head)) == item) {
653
SET_FREELIST_POINTER_VERSION(next, item_next, FREELIST_VERSION(head) + 1);
654
#if !defined(INK_USE_MUTEX_FOR_ATOMICLISTS)
655
result = ink_atomic_cas64((int64_t *) & l->head.data, head.data, next.data);
657
l->head.data = next.data;
664
INK_QUEUE_LD64(head, l->head);
668
* then, go down the list, trying to remove it
670
prev = TO_PTR(FREELIST_POINTER(head));
672
void **prev_adr_of_next = ADDRESS_OF_NEXT(prev, l->offset);
673
void *prev_prev = prev;
674
prev = TO_PTR(*prev_adr_of_next);
676
ink_assert(prev_prev != item_next);
677
*prev_adr_of_next = item_next;
added
removed
lib/ts/ink_queue.cc
