1#pragma once
2
3#include <limits.h>
4
5#ifdef __cplusplus
6extern "C" {
7#endif
8
9// minimum allocation size
10#define UNIT_PWR2 4
11#define UNIT_SIZE (1 << UNIT_PWR2)
12
13#define MAX_CHUNK_DATA_SIZE_32 (512UL * 1024UL * 1024UL)
14/*
15 * Maximum size of data on 32-bit architectures.
16 *
17 * With 3GB/1GB split, 16 byte unit size, and 4K page
18 * this results in 16 chunks only:
19 *
20 * chunk index bitmap size data size
21 * 0 4096 512K
22 * 1 8192 1M
23 * 2 16384 2M
24 * 3 32768 4M
25 * . . .
26 * 10 4M 512M
27 * . . .
28 * 15 4M 512M
29 */
30
31#define MAX_CHUNK_DATA_SIZE_64 (4ULL * 1024ULL * 1024ULL * 1024ULL)
32/*
33 * Maximum size of data on 64-bit architectures.
34 */
35
36#if (PTRDIFF_WIDTH == 32) && (UINT_WIDTH >= 32)
37
38 static unsigned max_chunk_data_size = MAX_CHUNK_DATA_SIZE_32;
39# define MAX_CHUNKS 16
40
41#elif PTRDIFF_WIDTH == 64
42
43 static uint64_t max_chunk_data_size = MAX_CHUNK_DATA_SIZE_64;
44# define MAX_CHUNKS 32
45
46#else
47# error Cannot define max_chunk_data_size and MAX_CHUNKS, please revise.
48#endif
49
50
51typedef struct {
52 // Range of virtual address space reserved for chunk bitmap and data.
53 // Using combined range to reduce the number of comparisons in segv handler.
54 void* reserved_start; // null if not reserved yet
55 void* reserved_end; // initialized to chunk data size when reserved_start is null
56
57 // The number of first pages in the reserved address space used for bitmap.
58 unsigned num_bitmap_pages;
59
60 // Pointer to array containing the number of units allocated on each bitmap page.
61 uint16_t* num_bits_set;
62} Chunk;
63
64
65extern unsigned bitmap_page_units; // sys_page_size * 8
66extern unsigned bitmap_page_units_pwr2; // power of two
67extern unsigned bitmap_page_units_bitmask; // bitmap_page_units - 1
68extern unsigned bitmap_page_bytes; // bitmap_page_units * UNIT_SIZE
69extern unsigned bitmap_page_bytes_pwr2; // power of two
70
71
72/* Superblock
73 *
74 * Chunks in the array start from single bitmap page up to `max_bitmap_pages`
75 * which depends on target architecture.
76 *
77 * On 32-bit machines `max_bitmap_pages`
78 */
79extern Chunk chunks[MAX_CHUNKS];
80
81// Range of virtual address space reserved for num_bits_set arrays.
82extern uint16_t* num_bits_set_start;
83extern uint16_t* num_bits_set_end;
84
85#define ERR(...) print_msg(__func__, __VA_ARGS__)
86
87#define SAY(...) do { if (bitmap_allocator.verbose) { print_msg(__func__, __VA_ARGS__); } } while(false)
88
89#ifdef DEBUG
90# define TRACE(...) do { if (bitmap_allocator.trace) { print_msg(__func__, __VA_ARGS__); } } while(false)
91#else
92# define TRACE(...)
93#endif
94
95// Bitmaps are always stored as little-endian, here's conversion functions to read them
96// in chunks bigger than byte:
97
98#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
99 // XXX
100#else
101# error XXX
102#endif
103
104static inline unsigned bytes_to_units(unsigned nbytes)
105{
106 return align_unsigned(nbytes, UNIT_SIZE) >> UNIT_PWR2;
107}
108
109static inline unsigned units_to_bytes(unsigned units)
110{
111 return units << UNIT_PWR2;
112}
113
114static inline void* bitmap_page_by_index(Chunk* chunk, unsigned bitmap_page_index)
115{
116 return ((uint8_t*) chunk->reserved_start) + (bitmap_page_index << sys_page_pwr2);
117}
118
119static inline unsigned bitmap_page_index_to_unit_index(unsigned bitmap_page_index)
120{
121 return bitmap_page_index << bitmap_page_units_pwr2;
122}
123
124static inline unsigned unit_index_to_bitmap_page_index(unsigned unit_index)
125{
126 return unit_index >> bitmap_page_units_pwr2;
127}
128
129static inline void* unit_index_to_address(Chunk* chunk, unsigned unit_index)
130{
131 uint8_t* data_start = bitmap_page_by_index(chunk, chunk->num_bitmap_pages);
132 return data_start + units_to_bytes(unit_index);
133}
134
135static inline void* chunk_data_start(Chunk* chunk)
136{
137 return bitmap_page_by_index(chunk, chunk->num_bitmap_pages);
138}
139
140#ifdef DEBUG
141 void print_chunks();
142 void dump_chunk(Chunk* chunk);
143#endif
144
145
146#ifdef __cplusplus
147}
148#endif