1 /*
2 * Part of Scheme 48 1.9. See file COPYING for notices and license.
3 *
4 * Authors: David Frese, Marcus Crestani
5 */
6
7 #ifndef __S48_MEMORY_MAP_H
8 #define __S48_MEMORY_MAP_H
9
10 #include "scheme48arch.h"
11
12 #ifdef HAVE_STDINT_H
13 #include <stdint.h>
14 #endif
15
16 #include "memory.h"
17 #include "areas.h"
18 #include "page_constants.h"
19
20 /* When a new page is allocated: */
21 extern void s48_memory_map_setB(s48_address address, Area* value);
22
23 /* When the Area structure of a page is needed: */
24 /* extern Area* s48_memory_map_ref(s48_address address);
25 - defined inline below */
26
27 /* The following is only defined here to allow the inlining of
28 s48_memory_map_ref, and not used elsewhere: */
29
30 #include <assert.h>
31
32 /* We need an integer type of the same size as pointers, and the bit
33 length of addresses: */
34 #ifdef _WIN32
35 #define ADDRESS_LENGTH 32
36 #elif _WIN64
37 #define ADDRESS_LENGTH 64
38 #else
39 #include <limits.h>
40 #define ADDRESS_LENGTH WORDSIZE
41
42 #endif
43
44 /*** CONFIGURATION ***/
45
46 /* The memory_map provides a way to store and find an Area structure
47 for every memory page we have allocated for the heap. It must be
48 very fast, without consuming too much memory at the same time.
49
50 For 32bit systems, this is quite easy, but to achieve this for
51 64bit systems, a sort of hashing is implemented. It is
52 automatically activated if the defined page size and a given size
53 for a statically allocated array are too small to cover all
54 potential addresses.
55
56 The first relevant size is defined in page_constants.h:
57
58 LOG_BYTES_PER_PAGE
59
60 The next one defines the size of a statically allocated global
61 array, which stores pointers to Metapage structures; it's
62 logarithmic size is:
63 */
64
65 #define LOG_TABLE_SIZE 10
66
67 /* Metapage structures are allocated by need, and each consists of
68 another array of pointers to Area structures. It's logarithmic size
69 is:
70 */
71
72 #define LOG_PAGES_PER_METAPAGE 10
73
74 /*** END OF CONFIGURATION ***/
75
76 /* Now with the usual sizes on a 32bit system these sizes sum up to 32
77 bits and we don't need the hashing algorithm. Let's see if we do
78 need it:
79 */
80
81 #define USED_ADDRESS_BITS \
82 (LOG_BYTES_PER_PAGE + LOG_TABLE_SIZE + LOG_PAGES_PER_METAPAGE)
83
84 #define REMAINING_ADDRESS_BITS \
85 (ADDRESS_LENGTH - USED_ADDRESS_BITS)
86
87 #if REMAINING_ADDRESS_BITS > 0
88 #define NEED_METAPAGE_HASHING
89 #elif REMAINING_ADDRESS_BITS == 0
90 #undef NEED_METAPAGE_HASHING
91 #else
92 #error "Misconfigured memory map."##REMAINING_ADDRESS_BITS
93 #endif
94
95 /* For both direct access and hashed access, we split an address into
96 the following fields:
97
98 high low
99 | Rest | Metapage in Table | Page in Metapage | Byte in Page |
100
101 If the Rest has 0-length we don't need hashing.
102
103 */
104
105 /* Some sizes: */
106 #define METAPAGES (((uintptr_t)1) << LOG_TABLE_SIZE)
107 #define PAGES_PER_METAPAGE (((uintptr_t)1) << LOG_PAGES_PER_METAPAGE)
108
109 /* Some accessors for the fields : */
110
111 #define ADDR_METAPAGE_INDEX(address) \
112 ( ( ((uintptr_t)address) >> (LOG_BYTES_PER_PAGE + LOG_PAGES_PER_METAPAGE) ) \
113 & (METAPAGES - 1) )
114
115 #define ADDR_PAGE_INDEX(address) \
116 ( ( ((uintptr_t)address) >> LOG_BYTES_PER_PAGE ) \
117 & (PAGES_PER_METAPAGE - 1) )
118
119 #ifdef NEED_METAPAGE_HASHING
120
121 #define ADDR_REST(address) \
122 ( ((uintptr_t)address) >> USED_ADDRESS_BITS )
123
124 /* To identify the correct hash bucket, we need store the start
125 address of all pages of a metapage. We use this macro to compare
126 them: */
127 #define ADDR_REST_MASK \
128 ( ((uintptr_t)-1) << USED_ADDRESS_BITS )
129 #define ADDR_REST_MASKED(address) ((void*)(ADDR_REST_MASK & ((uintptr_t)address)))
130 #define IS_CORRECT_METAPAGE(metapage, address) \
131 ( ADDR_REST_MASKED(metapage->start_address) == ADDR_REST_MASKED(address) )
132
133 #endif
134
135 /* And now the structure we use; for hashing, we use a linked list of
136 Metapages for pages which have the same ADDR_METAPAGE_INDEX, but
137 different ADDR_REST parts:
138 */
139
140 typedef struct _Metapage {
141 #ifdef NEED_METAPAGE_HASHING
142 s48_address start_address;
143 struct _Metapage* next;
144 #endif
145 Area* contents[PAGES_PER_METAPAGE];
146 } Metapage;
147
148 #define TABLE_SIZE (1L << LOG_TABLE_SIZE)
149
150 S48_EXTERN Metapage* s48_memory_table[];
151
152 #ifdef NEED_METAPAGE_HASHING
153
154 /* returns the place of the found pointer to the metapage, resp. the
155 place where a newly allocated metepage should be stored: */
find_metapagep(s48_address address)156 inline static Metapage** find_metapagep(s48_address address) {
157 Metapage** bucketp = &s48_memory_table[ADDR_METAPAGE_INDEX(address)];
158 while ((*bucketp != NULL) && (!IS_CORRECT_METAPAGE((*bucketp), address))) {
159 bucketp = &(*bucketp)->next;
160 }
161 assert(bucketp != NULL);
162 return bucketp;
163 }
164
165 #else
166
167 #define find_metapagep(address) (&s48_memory_table[ADDR_METAPAGE_INDEX(address)])
168
169 #endif
170
s48_memory_map_ref(s48_address address)171 inline static Area* s48_memory_map_ref(s48_address address) {
172 Metapage* metapage = *find_metapagep(address);
173 if (metapage == NULL)
174 return NULL;
175 else
176 return metapage->contents[ADDR_PAGE_INDEX(address)];
177 };
178
179 #endif
180