src/allocator_internal.h

/*
 * Copyright (c) 2012-2013 Apple Inc. All rights reserved.
 *
 * @APPLE_APACHE_LICENSE_HEADER_START@
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * @APPLE_APACHE_LICENSE_HEADER_END@
 */

/*
 * IMPORTANT: This header file describes INTERNAL interfaces to libdispatch
 * which are subject to change in future releases of Mac OS X. Any applications
 * relying on these interfaces WILL break.
 */

#ifndef __DISPATCH_ALLOCATOR_INTERNAL__
#define __DISPATCH_ALLOCATOR_INTERNAL__

#ifndef DISPATCH_ALLOCATOR
#if TARGET_OS_MAC && (defined(__LP64__) || TARGET_OS_EMBEDDED)
#define DISPATCH_ALLOCATOR 1
#endif
#endif

#ifndef DISPATCH_USE_NANOZONE
#if TARGET_OS_MAC && defined(__LP64__)
#define DISPATCH_USE_NANOZONE 1
#endif
#endif

#ifndef DISPATCH_USE_MALLOCZONE
#if (TARGET_OS_MAC && !DISPATCH_USE_NANOZONE) || \
		(!TARGET_OS_MAC && HAVE_MALLOC_CREATE_ZONE)
#define DISPATCH_USE_MALLOCZONE 1
#endif
#endif

#ifndef DISPATCH_CONTINUATION_MALLOC
#if DISPATCH_USE_NANOZONE || !DISPATCH_ALLOCATOR
#define DISPATCH_CONTINUATION_MALLOC 1
#endif
#endif

#if !DISPATCH_ALLOCATOR && !DISPATCH_CONTINUATION_MALLOC
#error Invalid allocator configuration
#endif

#if DISPATCH_ALLOCATOR && DISPATCH_CONTINUATION_MALLOC
#define DISPATCH_ALLOC_NOINLINE DISPATCH_NOINLINE
#else
#define DISPATCH_ALLOC_NOINLINE
#endif

#pragma mark -
#pragma mark DISPATCH_ALLOCATOR

#if DISPATCH_ALLOCATOR

// Configuration here!
#define NUM_CPU dispatch_hw_config(logical_cpus)
#define MAGAZINES_PER_HEAP (NUM_CPU)

// Do you care about compaction or performance?
#if TARGET_OS_EMBEDDED
#define PACK_FIRST_PAGE_WITH_CONTINUATIONS 1
#else
#define PACK_FIRST_PAGE_WITH_CONTINUATIONS 0
#endif

#ifndef PAGE_MAX_SIZE
#define PAGE_MAX_SIZE PAGE_SIZE
#endif
#ifndef PAGE_MAX_MASK
#define PAGE_MAX_MASK PAGE_MASK
#endif
#define DISPATCH_ALLOCATOR_PAGE_SIZE PAGE_MAX_SIZE
#define DISPATCH_ALLOCATOR_PAGE_MASK PAGE_MAX_MASK


#if TARGET_OS_EMBEDDED
#define PAGES_PER_MAGAZINE 64
#else
#define PAGES_PER_MAGAZINE 512
#endif

// Use the largest type your platform is comfortable doing atomic ops with.
// TODO: rdar://11477843
typedef unsigned long bitmap_t;
#if defined(__LP64__)
#define BYTES_PER_BITMAP 8
#else
#define BYTES_PER_BITMAP 4
#endif

#define BITMAP_C(v) ((bitmap_t)(v))
#define BITMAP_ALL_ONES (~BITMAP_C(0))

// Stop configuring.

#define CONTINUATIONS_PER_BITMAP (BYTES_PER_BITMAP * 8)
#define BITMAPS_PER_SUPERMAP (BYTES_PER_SUPERMAP * 8)

#define BYTES_PER_MAGAZINE (PAGES_PER_MAGAZINE * DISPATCH_ALLOCATOR_PAGE_SIZE)
#define CONSUMED_BYTES_PER_BITMAP (BYTES_PER_BITMAP + \
		(DISPATCH_CONTINUATION_SIZE * CONTINUATIONS_PER_BITMAP))

#define BYTES_PER_SUPERMAP BYTES_PER_BITMAP
#define CONSUMED_BYTES_PER_SUPERMAP (BYTES_PER_SUPERMAP + \
		(BITMAPS_PER_SUPERMAP * CONSUMED_BYTES_PER_BITMAP))

#define BYTES_PER_HEAP (BYTES_PER_MAGAZINE * MAGAZINES_PER_HEAP)

#define BYTES_PER_PAGE DISPATCH_ALLOCATOR_PAGE_SIZE
#define CONTINUATIONS_PER_PAGE (BYTES_PER_PAGE / DISPATCH_CONTINUATION_SIZE)
#define BITMAPS_PER_PAGE (CONTINUATIONS_PER_PAGE / CONTINUATIONS_PER_BITMAP)

// Assumption: metadata will be only in the first page.
#define SUPERMAPS_PER_MAGAZINE ((BYTES_PER_MAGAZINE - BYTES_PER_PAGE) / \
		CONSUMED_BYTES_PER_SUPERMAP)
#define BITMAPS_PER_MAGAZINE (SUPERMAPS_PER_MAGAZINE * BITMAPS_PER_SUPERMAP)
#define CONTINUATIONS_PER_MAGAZINE \
		(BITMAPS_PER_MAGAZINE * CONTINUATIONS_PER_BITMAP)

#define HEAP_MASK (~(uintptr_t)(BYTES_PER_HEAP - 1))
#define MAGAZINE_MASK (~(uintptr_t)(BYTES_PER_MAGAZINE - 1))

// this will round up such that first_bitmap_in_same_page() can mask the address
// of a bitmap_t in the maps to obtain the first bitmap for that same page
#define ROUND_UP_TO_BITMAP_ALIGNMENT(x) \
		(((x) + ((BITMAPS_PER_PAGE * BYTES_PER_BITMAP) - 1u)) & \
		~((BITMAPS_PER_PAGE * BYTES_PER_BITMAP) - 1u))
// Since these are both powers of two, we end up with not only the max alignment,
// but happily the least common multiple, which will be the greater of the two.
#define ROUND_UP_TO_BITMAP_ALIGNMENT_AND_CONTINUATION_SIZE(x) (ROUND_UP_TO_CONTINUATION_SIZE(ROUND_UP_TO_BITMAP_ALIGNMENT(x)))
#define PADDING_TO_BITMAP_ALIGNMENT_AND_CONTINUATION_SIZE(x) (ROUND_UP_TO_BITMAP_ALIGNMENT_AND_CONTINUATION_SIZE(x) - (x))

#define PADDING_TO_CONTINUATION_SIZE(x) (ROUND_UP_TO_CONTINUATION_SIZE(x) - (x))

#if defined(__LP64__)
#define SIZEOF_HEADER 16
#else
#define SIZEOF_HEADER 8
#endif

#define SIZEOF_SUPERMAPS (BYTES_PER_SUPERMAP * SUPERMAPS_PER_MAGAZINE)
#define SIZEOF_MAPS (BYTES_PER_BITMAP * BITMAPS_PER_SUPERMAP * \
		SUPERMAPS_PER_MAGAZINE)

// header is expected to end on supermap's required alignment
#define HEADER_TO_SUPERMAPS_PADDING 0
// we want to align the maps to a continuation size, but we must also have proper padding
// so that we can perform first_bitmap_in_same_page()
#define SUPERMAPS_TO_MAPS_PADDING (PADDING_TO_BITMAP_ALIGNMENT_AND_CONTINUATION_SIZE( \
		SIZEOF_SUPERMAPS + HEADER_TO_SUPERMAPS_PADDING + SIZEOF_HEADER))

#define MAPS_TO_FPMAPS_PADDING (PADDING_TO_CONTINUATION_SIZE(SIZEOF_MAPS))

#define BYTES_LEFT_IN_FIRST_PAGE (BYTES_PER_PAGE - \
		(SIZEOF_HEADER + HEADER_TO_SUPERMAPS_PADDING + SIZEOF_SUPERMAPS + \
		SUPERMAPS_TO_MAPS_PADDING + SIZEOF_MAPS + MAPS_TO_FPMAPS_PADDING))

#if PACK_FIRST_PAGE_WITH_CONTINUATIONS

#define FULL_BITMAPS_IN_FIRST_PAGE \
		(BYTES_LEFT_IN_FIRST_PAGE / CONSUMED_BYTES_PER_BITMAP)
#define REMAINDER_IN_FIRST_PAGE (BYTES_LEFT_IN_FIRST_PAGE - \
		(FULL_BITMAPS_IN_FIRST_PAGE * CONSUMED_BYTES_PER_BITMAP) - \
		(FULL_BITMAPS_IN_FIRST_PAGE ? 0 : \
		ROUND_UP_TO_CONTINUATION_SIZE(BYTES_PER_BITMAP)))

#define REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE \
		(REMAINDER_IN_FIRST_PAGE / DISPATCH_CONTINUATION_SIZE)
#define CONTINUATIONS_IN_FIRST_PAGE (FULL_BITMAPS_IN_FIRST_PAGE * \
		CONTINUATIONS_PER_BITMAP) + REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE
#define BITMAPS_IN_FIRST_PAGE (FULL_BITMAPS_IN_FIRST_PAGE + \
		(REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE == 0 ? 0 : 1))

#define FPMAPS_TO_FPCONTS_PADDING (PADDING_TO_CONTINUATION_SIZE(\
		BYTES_PER_BITMAP * BITMAPS_IN_FIRST_PAGE))

#else // PACK_FIRST_PAGE_WITH_CONTINUATIONS

#define MAPS_TO_CONTS_PADDING BYTES_LEFT_IN_FIRST_PAGE

#endif // PACK_FIRST_PAGE_WITH_CONTINUATIONS

#define AFTER_CONTS_PADDING (BYTES_PER_MAGAZINE - (BYTES_PER_PAGE + \
		(DISPATCH_CONTINUATION_SIZE * CONTINUATIONS_PER_MAGAZINE)))

// This is the object our allocator allocates: a chunk of memory rounded up
// from sizeof(struct dispatch_continuation_s) to the cacheline size, so
// unrelated continuations don't share cachelines. It'd be nice if
// dispatch_continuation_s included this rounding/padding, but it doesn't.
typedef char padded_continuation[DISPATCH_CONTINUATION_SIZE];

// A dispatch_heap_t is the base address of an array of dispatch_magazine_s,
// one magazine per CPU.
typedef struct dispatch_magazine_s * dispatch_heap_t;

struct dispatch_magazine_header_s {
	// Link to the next heap in the chain. Only used in magazine 0's header
	dispatch_heap_t dh_next;

	// Points to the first bitmap in the page where this CPU successfully
	// allocated a continuation last time. Only used in the first heap.
	bitmap_t *last_found_page;
};

// A magazine is a complex data structure. It must be exactly
// PAGES_PER_MAGAZINE * PAGE_SIZE bytes long, and that value must be a
// power of 2. (See magazine_for_continuation()).
struct dispatch_magazine_s {
	// See above.
	struct dispatch_magazine_header_s header;

	// Align supermaps as needed.
#if HEADER_TO_SUPERMAPS_PADDING > 0
	char _pad0[HEADER_TO_SUPERMAPS_PADDING];
#endif

	// Second-level bitmap; each set bit means a bitmap_t in maps[][]
	// is completely full (and can be skipped while searching).
	bitmap_t supermaps[SUPERMAPS_PER_MAGAZINE];

	// Align maps to a cacheline.
#if SUPERMAPS_TO_MAPS_PADDING > 0
	char _pad1[SUPERMAPS_TO_MAPS_PADDING];
#endif

	// Each bit in maps[][] is the free/used state of a member of conts[][][].
	bitmap_t maps[SUPERMAPS_PER_MAGAZINE][BITMAPS_PER_SUPERMAP];

	// Align fp_maps to a cacheline.
#if MAPS_TO_FPMAPS_PADDING > 0
	char _pad2[MAPS_TO_FPMAPS_PADDING];
#endif

#if PACK_FIRST_PAGE_WITH_CONTINUATIONS
	// Bitmaps for the continuations that live in the first page, which
	// are treated specially (they have faster search code).
	bitmap_t fp_maps[BITMAPS_IN_FIRST_PAGE];

	// Align fp_conts to cacheline.
#if FPMAPS_TO_FPCONTS_PADDING > 0
	char _pad3[FPMAPS_TO_FPCONTS_PADDING];
#endif

	// Continuations that live in the first page.
	padded_continuation fp_conts[CONTINUATIONS_IN_FIRST_PAGE];

#else // PACK_FIRST_PAGE_WITH_CONTINUATIONS

#if MAPS_TO_CONTS_PADDING > 0
	char _pad4[MAPS_TO_CONTS_PADDING];
#endif
#endif // PACK_FIRST_PAGE_WITH_CONTINUATIONS

	// This is the big array of continuations.
	// This must start on a page boundary.
	padded_continuation conts[SUPERMAPS_PER_MAGAZINE][BITMAPS_PER_SUPERMAP]
			[CONTINUATIONS_PER_BITMAP];

	// Fill the unused space to exactly BYTES_PER_MAGAZINE
#if AFTER_CONTS_PADDING > 0
	char _pad5[AFTER_CONTS_PADDING];
#endif
};

#if DISPATCH_DEBUG
#define DISPATCH_ALLOCATOR_SCRIBBLE ((uintptr_t)0xAFAFAFAFAFAFAFAF)
#endif

#endif // DISPATCH_ALLOCATOR

#endif // __DISPATCH_ALLOCATOR_INTERNAL__