|
0
|
1 /* Block-relocating memory allocator.
|
|
|
2 Copyright (C) 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
|
|
|
3
|
|
|
4 This file is part of XEmacs.
|
|
|
5
|
|
|
6 XEmacs is free software; you can redistribute it and/or modify it
|
|
|
7 under the terms of the GNU General Public License as published by the
|
|
|
8 Free Software Foundation; either version 2, or (at your option) any
|
|
|
9 later version.
|
|
|
10
|
|
|
11 XEmacs is distributed in the hope that it will be useful, but WITHOUT
|
|
|
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
14 for more details.
|
|
|
15
|
|
|
16 You should have received a copy of the GNU General Public License
|
|
|
17 along with GNU Emacs; see the file COPYING. If not, write to
|
|
|
18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
|
|
|
19 Boston, MA 02111-1307, USA. */
|
|
|
20
|
|
|
21 /* NOTES:
|
|
|
22
|
|
|
23 Only relocate the blocs necessary for SIZE in r_alloc_sbrk,
|
|
|
24 rather than all of them. This means allowing for a possible
|
|
|
25 hole between the first bloc and the end of malloc storage. */
|
|
|
26
|
|
|
27 #ifdef emacs
|
|
|
28
|
|
|
29 #include <config.h>
|
|
|
30 #include "lisp.h" /* Needed for VALBITS. */
|
|
|
31
|
|
|
32 #undef NULL
|
|
|
33
|
|
|
34 /* The important properties of this type are that 1) it's a pointer, and
|
|
|
35 2) arithmetic on it should work as if the size of the object pointed
|
|
|
36 to has a size of 1. */
|
|
|
37 #if 0 /* Arithmetic on void* is a GCC extension. */
|
|
|
38 #ifdef __STDC__
|
|
|
39 typedef void *POINTER;
|
|
|
40 #else
|
|
|
41 typedef unsigned char *POINTER;
|
|
|
42 #endif
|
|
|
43 #endif /* 0 */
|
|
|
44
|
|
|
45 /* Unconditionally use unsigned char * for this. */
|
|
|
46 typedef unsigned char *POINTER;
|
|
|
47
|
|
|
48 typedef unsigned long SIZE;
|
|
|
49
|
|
|
50 #include "getpagesize.h"
|
|
|
51
|
|
|
52 #include <string.h>
|
|
|
53
|
|
|
54 #else /* Not emacs. */
|
|
|
55
|
|
|
56 #include <stddef.h>
|
|
|
57
|
|
|
58 typedef size_t SIZE;
|
|
|
59 typedef void *POINTER;
|
|
|
60
|
|
|
61 #include <unistd.h>
|
|
|
62 #include <malloc.h>
|
|
|
63 #include <string.h>
|
|
|
64
|
|
|
65 #endif /* emacs. */
|
|
|
66
|
|
|
67 #define safe_bcopy(x, y, z) memmove (y, x, z)
|
|
|
68
|
|
|
69 #define NIL ((POINTER) 0)
|
|
|
70
|
|
|
71
|
|
|
72 #ifndef HAVE_MMAP
|
|
|
73
|
|
|
74 /* A flag to indicate whether we have initialized ralloc yet. For
|
|
|
75 Emacs's sake, please do not make this local to malloc_init; on some
|
|
|
76 machines, the dumping procedure makes all static variables
|
|
|
77 read-only. On these machines, the word static is #defined to be
|
|
|
78 the empty string, meaning that r_alloc_initialized becomes an
|
|
|
79 automatic variable, and loses its value each time Emacs is started up. */
|
|
|
80 static int r_alloc_initialized = 0;
|
|
|
81
|
|
|
82
|
|
|
83 /* Declarations for working with the malloc, ralloc, and system breaks. */
|
|
|
84
|
|
|
85 /* Function to set the real break value. */
|
|
|
86 static POINTER (*real_morecore) ();
|
|
|
87
|
|
|
88 /* The break value, as seen by malloc (). */
|
|
|
89 static POINTER virtual_break_value;
|
|
|
90
|
|
|
91 /* The break value, viewed by the relocatable blocs. */
|
|
|
92 static POINTER break_value;
|
|
|
93
|
|
|
94 /* The REAL (i.e., page aligned) break value of the process. */
|
|
|
95 static POINTER page_break_value;
|
|
|
96
|
|
|
97 /* This is the size of a page. We round memory requests to this boundary. */
|
|
|
98 static int page_size;
|
|
|
99
|
|
|
100 /* Whenever we get memory from the system, get this many extra bytes. This
|
|
|
101 must be a multiple of page_size. */
|
|
|
102 static int extra_bytes;
|
|
|
103
|
|
|
104 /* Macros for rounding. Note that rounding to any value is possible
|
|
|
105 by changing the definition of PAGE. */
|
|
|
106 #define PAGE (getpagesize ())
|
|
|
107 #define ALIGNED(addr) (((unsigned long int) (addr) & (page_size - 1)) == 0)
|
|
|
108 #define ROUNDUP(size) (((unsigned long int) (size) + page_size - 1) \
|
|
|
109 & ~(page_size - 1))
|
|
|
110 #define ROUND_TO_PAGE(addr) (addr & (~(page_size - 1)))
|
|
|
111
|
|
|
112 /* Functions to get and return memory from the system. */
|
|
|
113
|
|
|
114 /* Obtain SIZE bytes of space. If enough space is not presently available
|
|
|
115 in our process reserve, (i.e., (page_break_value - break_value)),
|
|
|
116 this means getting more page-aligned space from the system.
|
|
|
117
|
|
|
118 Return non-zero if all went well, or zero if we couldn't allocate
|
|
|
119 the memory. */
|
|
|
120 static int
|
|
|
121 obtain (SIZE size)
|
|
|
122 {
|
|
|
123 SIZE already_available = page_break_value - break_value;
|
|
|
124
|
|
|
125 if (already_available < size)
|
|
|
126 {
|
|
|
127 SIZE get = ROUNDUP (size - already_available);
|
|
|
128 /* Get some extra, so we can come here less often. */
|
|
|
129 get += extra_bytes;
|
|
|
130
|
|
|
131 if ((*real_morecore) (get) == 0)
|
|
|
132 return 0;
|
|
|
133
|
|
|
134 page_break_value += get;
|
|
|
135 }
|
|
|
136
|
|
|
137 break_value += size;
|
|
|
138
|
|
|
139 return 1;
|
|
|
140 }
|
|
|
141
|
|
|
142 /* Obtain SIZE bytes of space and return a pointer to the new area.
|
|
|
143 If we could not allocate the space, return zero. */
|
|
|
144
|
|
|
145 static POINTER
|
|
|
146 get_more_space (SIZE size)
|
|
|
147 {
|
|
|
148 POINTER ptr = break_value;
|
|
|
149 if (obtain (size))
|
|
|
150 return ptr;
|
|
|
151 else
|
|
|
152 return 0;
|
|
|
153 }
|
|
|
154
|
|
|
155 /* Note that SIZE bytes of space have been relinquished by the process.
|
|
|
156 If SIZE is more than a page, return the space to the system. */
|
|
|
157
|
|
|
158 static void
|
|
|
159 relinquish (SIZE size)
|
|
|
160 {
|
|
|
161 POINTER new_page_break;
|
|
|
162 int excess;
|
|
|
163
|
|
|
164 break_value -= size;
|
|
|
165 new_page_break = (POINTER) ROUNDUP (break_value);
|
|
|
166 excess = (char *) page_break_value - (char *) new_page_break;
|
|
|
167
|
|
|
168 if (excess > extra_bytes * 2)
|
|
|
169 {
|
|
|
170 /* Keep extra_bytes worth of empty space.
|
|
|
171 And don't free anything unless we can free at least extra_bytes. */
|
|
|
172 if ((*real_morecore) (extra_bytes - excess) == 0)
|
|
|
173 abort ();
|
|
|
174
|
|
|
175 page_break_value += extra_bytes - excess;
|
|
|
176 }
|
|
|
177
|
|
|
178 /* Zero the space from the end of the "official" break to the actual
|
|
|
179 break, so that bugs show up faster. */
|
|
|
180 memset (break_value, 0, ((char *) page_break_value - (char *) break_value));
|
|
|
181 }
|
|
|
182
|
|
|
183 /* The meat - allocating, freeing, and relocating blocs. */
|
|
|
184
|
|
|
185 /* These structures are allocated in the malloc arena.
|
|
|
186 The linked list is kept in order of increasing '.data' members.
|
|
|
187 The data blocks abut each other; if b->next is non-nil, then
|
|
|
188 b->data + b->size == b->next->data. */
|
|
|
189 typedef struct bp
|
|
|
190 {
|
|
|
191 struct bp *next;
|
|
|
192 struct bp *prev;
|
|
|
193 POINTER *variable;
|
|
|
194 POINTER data;
|
|
|
195 SIZE size;
|
|
|
196 } *bloc_ptr;
|
|
|
197
|
|
|
198 #define NIL_BLOC ((bloc_ptr) 0)
|
|
|
199 #define BLOC_PTR_SIZE (sizeof (struct bp))
|
|
|
200
|
|
|
201 /* Head and tail of the list of relocatable blocs. */
|
|
|
202 static bloc_ptr first_bloc, last_bloc;
|
|
|
203
|
|
|
204 /* Find the bloc referenced by the address in PTR. Returns a pointer
|
|
|
205 to that block. */
|
|
|
206
|
|
|
207 static bloc_ptr
|
|
|
208 find_bloc (POINTER *ptr)
|
|
|
209 {
|
|
|
210 bloc_ptr p = first_bloc;
|
|
|
211
|
|
|
212 while (p != NIL_BLOC)
|
|
|
213 {
|
|
|
214 if (p->variable == ptr && p->data == *ptr)
|
|
|
215 return p;
|
|
|
216
|
|
|
217 p = p->next;
|
|
|
218 }
|
|
|
219
|
|
|
220 return p;
|
|
|
221 }
|
|
|
222
|
|
|
223 /* Allocate a bloc of SIZE bytes and append it to the chain of blocs.
|
|
|
224 Returns a pointer to the new bloc, or zero if we couldn't allocate
|
|
|
225 memory for the new block. */
|
|
|
226
|
|
|
227 static bloc_ptr
|
|
|
228 get_bloc (SIZE size)
|
|
|
229 {
|
|
|
230 bloc_ptr new_bloc;
|
|
|
231
|
|
|
232 if (! (new_bloc = (bloc_ptr) malloc (BLOC_PTR_SIZE))
|
|
|
233 || ! (new_bloc->data = get_more_space (size)))
|
|
|
234 {
|
|
|
235 if (new_bloc)
|
|
|
236 free (new_bloc);
|
|
|
237
|
|
|
238 return 0;
|
|
|
239 }
|
|
|
240
|
|
|
241 new_bloc->size = size;
|
|
|
242 new_bloc->next = NIL_BLOC;
|
|
|
243 new_bloc->variable = (POINTER *) NIL;
|
|
|
244
|
|
|
245 if (first_bloc)
|
|
|
246 {
|
|
|
247 new_bloc->prev = last_bloc;
|
|
|
248 last_bloc->next = new_bloc;
|
|
|
249 last_bloc = new_bloc;
|
|
|
250 }
|
|
|
251 else
|
|
|
252 {
|
|
|
253 first_bloc = last_bloc = new_bloc;
|
|
|
254 new_bloc->prev = NIL_BLOC;
|
|
|
255 }
|
|
|
256
|
|
|
257 return new_bloc;
|
|
|
258 }
|
|
|
259
|
|
|
260 /* Relocate all blocs from BLOC on upward in the list to the zone
|
|
|
261 indicated by ADDRESS. Direction of relocation is determined by
|
|
|
262 the position of ADDRESS relative to BLOC->data.
|
|
|
263
|
|
|
264 If BLOC is NIL_BLOC, nothing is done.
|
|
|
265
|
|
|
266 Note that ordering of blocs is not affected by this function. */
|
|
|
267
|
|
|
268 static void
|
|
|
269 relocate_some_blocs (bloc_ptr bloc, POINTER address)
|
|
|
270 {
|
|
|
271 if (bloc != NIL_BLOC)
|
|
|
272 {
|
|
|
273 SIZE offset = address - bloc->data;
|
|
|
274 SIZE data_size = 0;
|
|
|
275 bloc_ptr b;
|
|
|
276
|
|
|
277 for (b = bloc; b != NIL_BLOC; b = b->next)
|
|
|
278 {
|
|
|
279 data_size += b->size;
|
|
|
280 b->data += offset;
|
|
|
281 *b->variable = b->data;
|
|
|
282 }
|
|
|
283
|
|
|
284 memmove (address, address - offset, data_size);
|
|
|
285 }
|
|
|
286 }
|
|
|
287
|
|
|
288 /* Free BLOC from the chain of blocs, relocating any blocs above it
|
|
|
289 and returning BLOC->size bytes to the free area. */
|
|
|
290
|
|
|
291 static void
|
|
|
292 free_bloc (bloc_ptr bloc)
|
|
|
293 {
|
|
|
294 if (bloc == first_bloc && bloc == last_bloc)
|
|
|
295 {
|
|
|
296 first_bloc = last_bloc = NIL_BLOC;
|
|
|
297 }
|
|
|
298 else if (bloc == last_bloc)
|
|
|
299 {
|
|
|
300 last_bloc = bloc->prev;
|
|
|
301 last_bloc->next = NIL_BLOC;
|
|
|
302 }
|
|
|
303 else if (bloc == first_bloc)
|
|
|
304 {
|
|
|
305 first_bloc = bloc->next;
|
|
|
306 first_bloc->prev = NIL_BLOC;
|
|
|
307 }
|
|
|
308 else
|
|
|
309 {
|
|
|
310 bloc->next->prev = bloc->prev;
|
|
|
311 bloc->prev->next = bloc->next;
|
|
|
312 }
|
|
|
313
|
|
|
314 relocate_some_blocs (bloc->next, bloc->data);
|
|
|
315 relinquish (bloc->size);
|
|
|
316 free (bloc);
|
|
|
317 }
|
|
|
318
|
|
|
319 /* Interface routines. */
|
|
|
320
|
|
|
321 static int use_relocatable_buffers;
|
|
|
322
|
|
|
323 /* Obtain SIZE bytes of storage from the free pool, or the system, as
|
|
|
324 necessary. If relocatable blocs are in use, this means relocating
|
|
|
325 them. This function gets plugged into the GNU malloc's __morecore
|
|
|
326 hook.
|
|
|
327
|
|
|
328 We provide hysteresis, never relocating by less than extra_bytes.
|
|
|
329
|
|
|
330 If we're out of memory, we should return zero, to imitate the other
|
|
|
331 __morecore hook values - in particular, __default_morecore in the
|
|
|
332 GNU malloc package. */
|
|
|
333
|
|
|
334 POINTER
|
|
|
335 r_alloc_sbrk (long size)
|
|
|
336 {
|
|
|
337 /* This is the first address not currently available for the heap. */
|
|
|
338 POINTER top;
|
|
|
339 /* Amount of empty space below that. */
|
|
|
340 /* It is not correct to use SIZE here, because that is usually unsigned.
|
|
|
341 ptrdiff_t would be okay, but is not always available.
|
|
|
342 `long' will work in all cases, in practice. */
|
|
|
343 long already_available;
|
|
|
344 POINTER ptr;
|
|
|
345
|
|
|
346 if (! use_relocatable_buffers)
|
|
|
347 return (*real_morecore) (size);
|
|
|
348
|
|
|
349 top = first_bloc ? first_bloc->data : page_break_value;
|
|
|
350 already_available = (char *) top - (char *) virtual_break_value;
|
|
|
351
|
|
|
352 /* Do we not have enough gap already? */
|
|
|
353 if (size > 0 && already_available < size)
|
|
|
354 {
|
|
|
355 /* Get what we need, plus some extra so we can come here less often. */
|
|
|
356 SIZE get = size - already_available + extra_bytes;
|
|
|
357
|
|
|
358 if (! obtain (get))
|
|
|
359 return 0;
|
|
|
360
|
|
|
361 if (first_bloc)
|
|
|
362 relocate_some_blocs (first_bloc, first_bloc->data + get);
|
|
|
363
|
|
|
364 /* Zero out the space we just allocated, to help catch bugs
|
|
|
365 quickly. */
|
|
|
366 memset (virtual_break_value, 0, get);
|
|
|
367 }
|
|
|
368 /* Can we keep extra_bytes of gap while freeing at least extra_bytes? */
|
|
|
369 else if (size < 0 && already_available - size > 2 * extra_bytes)
|
|
|
370 {
|
|
|
371 /* Ok, do so. This is how many to free. */
|
|
|
372 SIZE give_back = already_available - size - extra_bytes;
|
|
|
373
|
|
|
374 if (first_bloc)
|
|
|
375 relocate_some_blocs (first_bloc, first_bloc->data - give_back);
|
|
|
376 relinquish (give_back);
|
|
|
377 }
|
|
|
378
|
|
|
379 ptr = virtual_break_value;
|
|
|
380 virtual_break_value += size;
|
|
|
381
|
|
|
382 return ptr;
|
|
|
383 }
|
|
|
384
|
|
|
385 /* Allocate a relocatable bloc of storage of size SIZE. A pointer to
|
|
|
386 the data is returned in *PTR. PTR is thus the address of some variable
|
|
|
387 which will use the data area.
|
|
|
388
|
|
|
389 If we can't allocate the necessary memory, set *PTR to zero, and
|
|
|
390 return zero. */
|
|
|
391
|
|
|
392 POINTER
|
|
|
393 r_alloc (POINTER *ptr, SIZE size)
|
|
|
394 {
|
|
|
395 bloc_ptr new_bloc;
|
|
|
396
|
|
|
397 if (! r_alloc_initialized)
|
|
|
398 init_ralloc ();
|
|
|
399
|
|
|
400 new_bloc = get_bloc (size);
|
|
|
401 if (new_bloc)
|
|
|
402 {
|
|
|
403 new_bloc->variable = ptr;
|
|
|
404 *ptr = new_bloc->data;
|
|
|
405 }
|
|
|
406 else
|
|
|
407 *ptr = 0;
|
|
|
408
|
|
|
409 return *ptr;
|
|
|
410 }
|
|
|
411
|
|
|
412 /* Free a bloc of relocatable storage whose data is pointed to by PTR.
|
|
|
413 Store 0 in *PTR to show there's no block allocated. */
|
|
|
414
|
|
|
415 void
|
|
|
416 r_alloc_free (POINTER *ptr)
|
|
|
417 {
|
|
|
418 bloc_ptr dead_bloc;
|
|
|
419
|
|
|
420 dead_bloc = find_bloc (ptr);
|
|
|
421 if (dead_bloc == NIL_BLOC)
|
|
|
422 abort ();
|
|
|
423
|
|
|
424 free_bloc (dead_bloc);
|
|
|
425 *ptr = 0;
|
|
|
426 }
|
|
|
427
|
|
|
428 /* Given a pointer at address PTR to relocatable data, resize it to SIZE.
|
|
|
429 Do this by shifting all blocks above this one up in memory, unless
|
|
|
430 SIZE is less than or equal to the current bloc size, in which case
|
|
|
431 do nothing.
|
|
|
432
|
|
|
433 Change *PTR to reflect the new bloc, and return this value.
|
|
|
434
|
|
|
435 If more memory cannot be allocated, then leave *PTR unchanged, and
|
|
|
436 return zero. */
|
|
|
437
|
|
|
438 POINTER
|
|
|
439 r_re_alloc (POINTER *ptr, SIZE size)
|
|
|
440 {
|
|
|
441 bloc_ptr bloc;
|
|
|
442
|
|
|
443 bloc = find_bloc (ptr);
|
|
|
444 if (bloc == NIL_BLOC)
|
|
|
445 abort ();
|
|
|
446
|
|
|
447 if (size <= bloc->size)
|
|
|
448 /* Wouldn't it be useful to actually resize the bloc here? */
|
|
|
449 return *ptr;
|
|
|
450
|
|
|
451 if (! obtain (size - bloc->size))
|
|
|
452 return 0;
|
|
|
453
|
|
|
454 relocate_some_blocs (bloc->next, bloc->data + size);
|
|
|
455
|
|
|
456 /* Zero out the new space in the bloc, to help catch bugs faster. */
|
|
|
457 memset (bloc->data + bloc->size, 0, size - bloc->size);
|
|
|
458
|
|
|
459 /* Indicate that this block has a new size. */
|
|
|
460 bloc->size = size;
|
|
|
461
|
|
|
462 return *ptr;
|
|
|
463 }
|
|
|
464
|
|
|
465 /* The hook `malloc' uses for the function which gets more space
|
|
|
466 from the system. */
|
|
|
467 extern POINTER (*__morecore) ();
|
|
|
468
|
|
|
469 /* Initialize various things for memory allocation. */
|
|
|
470
|
|
|
471 void
|
|
|
472 init_ralloc (void)
|
|
|
473 {
|
|
|
474 if (r_alloc_initialized)
|
|
|
475 return;
|
|
|
476
|
|
|
477 r_alloc_initialized = 1;
|
|
|
478 real_morecore = __morecore;
|
|
|
479 __morecore = r_alloc_sbrk;
|
|
|
480
|
|
|
481 virtual_break_value = break_value = (*real_morecore) (0);
|
|
|
482 if (break_value == NIL)
|
|
|
483 abort ();
|
|
|
484
|
|
|
485 page_size = PAGE;
|
|
|
486 extra_bytes = ROUNDUP (50000);
|
|
|
487
|
|
|
488 page_break_value = (POINTER) ROUNDUP (break_value);
|
|
|
489
|
|
|
490 /* From eirik@elf.IThaca.ny.US (Eirik Fuller):
|
|
|
491 The extra call to real_morecore guarantees that the end of the
|
|
|
492 address space is a multiple of page_size, even if page_size is
|
|
|
493 not really the page size of the system running the binary in
|
|
|
494 which page_size is stored. This allows a binary to be built on a
|
|
|
495 system with one page size and run on a system with a smaller page
|
|
|
496 size. (Such as compiling on a Sun 4/260 4.1.3 and running on a
|
|
|
497 Sun 4/65 4.1.3: 8k pages at compile time, 4k pages at run time.)
|
|
|
498 */
|
|
|
499 (*real_morecore) (page_break_value - break_value);
|
|
|
500
|
|
|
501 /* Clear the rest of the last page; this memory is in our address space
|
|
|
502 even though it is after the sbrk value. */
|
|
|
503
|
|
|
504 /* Doubly true, with the additional call that explicitly adds the
|
|
|
505 rest of that page to the address space. */
|
|
|
506 memset (break_value, 0, (page_break_value - break_value));
|
|
|
507 /* Also from eirik@elf.IThaca.ny.US */
|
|
|
508 virtual_break_value = break_value = page_break_value;
|
|
|
509 use_relocatable_buffers = 1;
|
|
|
510 }
|
|
|
511 #else /* HAVE_MMAP */
|
|
|
512
|
|
|
513 /*
|
|
|
514 A relocating allocator built using the mmap(2) facility available
|
|
|
515 in some OSes. Based on another version written by Paul Flinders,
|
|
|
516 from which code (and comments) are snarfed.
|
|
|
517
|
|
|
518 The OS should support mmap() with MAP_ANONYMOUS attribute, or have
|
|
|
519 /dev/zero. It should support private memory mapping.
|
|
|
520
|
|
|
521 Paul Flinders wrote a version which works well for systems that
|
|
|
522 allow callers to specify (virtual) addresses to mmap().
|
|
|
523 Unfortunately, such a scheme doesn't work for certain systems like
|
|
|
524 HP-UX that have a system-wide virtual->real address map, and
|
|
|
525 consequently impose restrictions on the virtual address values
|
|
|
526 permitted.
|
|
|
527
|
|
|
528 NB: The mapping scheme in HP-UX is motivated by the inverted page
|
|
|
529 table design in some HP processors.
|
|
|
530
|
|
|
531 This alternate implementation allows for the addresses to be
|
|
|
532 optionally chosen by the system. Fortunately, buffer allocation
|
|
|
533 doesn't insist upon contiguous memory which Flinders' scheme
|
|
|
534 provides, and this one doesn't.
|
|
|
535
|
|
|
536 We don't really provide for hysteresis here, but add some metering
|
|
|
537 to monitor how poorly the allocator actually works. See the
|
|
|
538 documentation for `mmap-hysteresis'.
|
|
|
539
|
|
|
540 This implementation actually cycles through the blocks allocated
|
|
|
541 via mmap() and only sends it to free() if it wasn't one of them.
|
|
|
542 Unfortunately, this is O(n) in the number of mmapped blocks. (Not
|
|
|
543 really, as we have a hash table which tries to reduce the cost.)
|
|
|
544 Also, this dereferences the pointer passed, so it would cause a
|
|
|
545 segfault if garbage was passed to it. */
|
|
|
546
|
|
|
547 #include <fcntl.h>
|
|
|
548 #include <sys/mman.h>
|
|
|
549 #include <stdio.h>
|
|
|
550
|
|
|
551 typedef void *VM_ADDR; /* VM addresses */
|
|
|
552 static CONST VM_ADDR VM_FAILURE_ADDR = (VM_ADDR) -1; /* mmap returns this when it fails. */
|
|
|
553
|
|
|
554 /* Configuration for relocating allocator. */
|
|
|
555
|
|
|
556 /* #define MMAP_GENERATE_ADDRESSES */
|
|
|
557 /* Define this if you want Emacs to manage the address table.
|
|
|
558 It is not recommended unless you have major problems with the
|
|
|
559 default scheme, which allows the OS to pick addresses. */
|
|
|
560
|
|
|
561 /* USELESS_LOWER_ADDRESS_BITS defines the number of bits which can be
|
|
|
562 discarded while computing the hash, as they're always zero. The
|
|
|
563 default is appropriate for a page size of 4096 bytes. */
|
|
|
564
|
|
|
565 #define USELESS_LOWER_ADDRESS_BITS 12
|
|
|
566
|
|
|
567
|
|
|
568 /* Size of hash table for inverted VM_ADDR->MMAP_HANDLE lookup */
|
|
|
569
|
|
|
570 #define MHASH_PRIME 89
|
|
|
571
|
|
|
572
|
|
|
573 /* Whether we want to enable metering of some ralloc performance.
|
|
|
574 This incurs a constant penalty for each mmap operation. */
|
|
|
575
|
|
|
576 #define MMAP_METERING
|
|
|
577
|
|
|
578
|
|
|
579 /* Rename the following to protect against a some smartness elsewhere.
|
|
|
580 We need access to the allocator used for non-mmap allocation
|
|
|
581 elsewhere, in case we get passed a handle that we didn't allocate
|
|
|
582 ourselves. Currently, this default allocator is also used to
|
|
|
583 maintain local structures for relocatable blocks. */
|
|
|
584
|
|
|
585 #define UNDERLYING_MALLOC malloc
|
|
|
586 #define UNDERLYING_FREE free
|
|
|
587 #define UNDERLYING_REALLOC realloc
|
|
|
588
|
|
|
589 /* MAP_ADDRCHOICE_FLAG is set to MAP_FIXED if MMAP_GENERATE_ADDRESSES
|
|
|
590 is defined, and MAP_VARIABLE otherwise. Some losing systems don't
|
|
|
591 define the _FIXED/_VARIABLE flags, in which case it is set to 0 */
|
|
|
592
|
|
|
593 #ifdef MMAP_GENERATE_ADDRESSES
|
|
|
594 # ifdef MAP_FIXED
|
|
|
595 # define MAP_ADDRCHOICE_FLAG MAP_FIXED
|
|
|
596 # endif
|
|
|
597 #else /* !MMAP_GENERATE_ADDRESSES */
|
|
|
598 # ifdef MAP_VARIABLE
|
|
|
599 # define MAP_ADDRCHOICE_FLAG MAP_VARIABLE
|
|
|
600 # endif
|
|
|
601 #endif /* MMAP_GENERATE_ADDRESSES */
|
|
|
602
|
|
|
603 /* Default case. */
|
|
|
604 #ifndef MAP_ADDRCHOICE_FLAG
|
|
|
605 # define MAP_ADDRCHOICE_FLAG 0
|
|
|
606 #endif /* MAP_ADDRCHOICE_FLAG */
|
|
|
607
|
|
|
608 #ifdef MAP_ANONYMOUS
|
|
|
609 # define MAP_FLAGS (MAP_PRIVATE | MAP_ADDRCHOICE_FLAG | MAP_ANONYMOUS)
|
|
|
610 #else
|
|
|
611 # define MAP_FLAGS (MAP_PRIVATE | MAP_ADDRCHOICE_FLAG)
|
|
|
612 #endif /* MAP_ANONYMOUS */
|
|
|
613
|
|
|
614
|
|
|
615 /* (ptf): A flag to indicate whether we have initialized ralloc yet. For
|
|
|
616 Emacs's sake, please do not make this local to malloc_init; on some
|
|
|
617 machines, the dumping procedure makes all static variables
|
|
|
618 read-only. On these machines, the word static is #defined to be
|
|
|
619 the empty string, meaning that r_alloc_initialized becomes an
|
|
|
620 automatic variable, and loses its value each time Emacs is started up.
|
|
|
621
|
|
|
622 If we're using mmap this flag has three possible values
|
|
|
623 0 - initial value
|
|
|
624 1 - Normal value when running temacs. In this case buffers
|
|
|
625 are allocated using malloc so that any data that they
|
|
|
626 contain becomes part of the undumped executable.
|
|
|
627 2 - Normal value when running emacs */
|
|
|
628 static int r_alloc_initialized = 0;
|
|
|
629
|
|
|
630 /* (ptf): Macros for rounding. Note that rounding to any value is possible
|
|
|
631 by changing the definition of PAGE. */
|
|
|
632 #define PAGE (getpagesize ())
|
|
|
633 #define PAGES_FOR(size) (((unsigned long int) (size) + page_size - 1)/page_size)
|
|
|
634 #define ROUNDUP(size) ((unsigned long int)PAGES_FOR(size)*page_size)
|
|
|
635
|
|
|
636
|
|
|
637 /* DEV_ZERO_FD is -1 normally, but for systems without MAP_ANONYMOUS
|
|
|
638 points to a file descriptor opened on /dev/zero */
|
|
|
639
|
|
|
640 static int DEV_ZERO_FD = -1;
|
|
|
641
|
|
|
642
|
|
|
643 /* We actually need a datastructure that can be usefully structured
|
|
|
644 based on the VM address, and allows an ~O(1) lookup on an arbitrary
|
|
|
645 address, ie a hash-table. Maybe the XEmacs hash table can be
|
|
|
646 coaxed enough. At the moment, we use lookup on a hash-table to
|
|
|
647 decide whether to do an O(n) search on the malloced block list.
|
|
|
648 Addresses are hashed to a bucket modulo MHASH_PRIME */
|
|
|
649
|
|
|
650
|
|
|
651 /* We settle for a standard doubly-linked-list. The dynarr type isn't
|
|
|
652 very amenable to deletion of items in the middle, so we conjure up
|
|
|
653 yet another stupid datastructure. The structure is maintained as a
|
|
|
654 ring, and the singleton ring has the sole element as it's left and
|
|
|
655 right neighbours. */
|
|
|
656
|
|
|
657 static void init_MHASH_table (void); /* Forward reference */
|
|
|
658
|
|
|
659 typedef struct alloc_dll
|
|
|
660 {
|
|
|
661 size_t size; /* #bytes currently in use */
|
|
|
662 size_t space_for; /* #bytes we really have */
|
|
|
663 POINTER* aliased_address; /* Address of aliased variable, to tweak if relocating */
|
|
|
664 VM_ADDR vm_addr; /* VM address returned by mmap */
|
|
|
665 struct alloc_dll *left; /* Left link in circular doubly linked list */
|
|
|
666 struct alloc_dll *right;
|
|
|
667 } *MMAP_HANDLE;
|
|
|
668
|
|
|
669 static MMAP_HANDLE mmap_start = 0; /* Head of linked list */
|
|
|
670 static size_t page_size = 0; /* Size of VM pages */
|
|
|
671 static int mmap_hysteresis; /* Should be size_t, really. */
|
|
|
672
|
|
|
673 /* Get a new handle for a fresh block. */
|
|
|
674 static MMAP_HANDLE
|
|
|
675 new_mmap_handle (size_t nsiz)
|
|
|
676 {
|
|
|
677 MMAP_HANDLE h = UNDERLYING_MALLOC( sizeof( struct alloc_dll ) );
|
|
|
678 if ( h == 0) return 0;
|
|
|
679 h->size = nsiz;
|
|
|
680 if (mmap_start == 0)
|
|
|
681 {
|
|
|
682 init_MHASH_table ();
|
|
|
683 mmap_start = h; mmap_start->left = h; mmap_start->right = h;
|
|
|
684 }
|
|
|
685 {
|
|
|
686 MMAP_HANDLE prev = mmap_start->left;
|
|
|
687 MMAP_HANDLE nex = mmap_start;
|
|
|
688
|
|
|
689 /* Four pointers need fixing. */
|
|
|
690 h->right = nex;
|
|
|
691 h->left = prev;
|
|
|
692 prev->right = h;
|
|
|
693 nex->left = h;
|
|
|
694 }
|
|
|
695 return h;
|
|
|
696 }
|
|
|
697
|
|
|
698 /* Find a handle given the aliased address using linear search. */
|
|
|
699 static MMAP_HANDLE
|
|
|
700 find_mmap_handle_lsearch (POINTER *alias)
|
|
|
701 {
|
|
|
702 MMAP_HANDLE h = mmap_start;
|
|
|
703 if (h == 0) return 0;
|
|
|
704 do {
|
|
|
705 if (h->aliased_address == alias && *alias == h->vm_addr)
|
|
|
706 return h;
|
|
|
707 h = h->right;
|
|
|
708 } while( h != mmap_start );
|
|
|
709 return 0; /* Bogus alias passed. */
|
|
|
710 }
|
|
|
711
|
|
|
712 /* Free a handle. */
|
|
|
713 static void
|
|
|
714 free_mmap_handle (MMAP_HANDLE h)
|
|
|
715 {
|
|
|
716 MMAP_HANDLE prev = h->left;
|
|
|
717 MMAP_HANDLE nex = h->right;
|
|
|
718 if (prev == h || nex == h) /* In fact, this should be && */
|
|
|
719 { /* We're the singleton dll */
|
|
|
720 UNDERLYING_FREE( h ); /* Free the sole item */
|
|
|
721 mmap_start = 0; return;
|
|
|
722 }
|
|
|
723 else if (h == mmap_start)
|
|
|
724 {
|
|
|
725 mmap_start = nex; /* Make sure mmap_start isn't bogus. */
|
|
|
726 }
|
|
|
727 prev->right = nex;
|
|
|
728 nex->left = prev;
|
|
|
729 UNDERLYING_FREE( h );
|
|
|
730 }
|
|
|
731
|
|
|
732 /* A simple hash table to speed up the inverted lookup of
|
|
|
733 VM_ADDR->MMAP_HANDLE. We maintain the number of hits for a
|
|
|
734 particular bucket. We invalidate a hash table entry during block
|
|
|
735 deletion if the hash has cached the deleted block's address. */
|
|
|
736
|
|
|
737 /* Simple hash check. */
|
|
|
738 struct {
|
|
|
739 int n_hits; /* How many addresses map to this? */
|
|
|
740 MMAP_HANDLE handle; /* What is the current handle? */
|
|
|
741 VM_ADDR addr; /* What is it's VM address? */
|
|
|
742 } MHASH_HITS[ MHASH_PRIME ];
|
|
|
743
|
|
|
744 static void
|
|
|
745 init_MHASH_table (void)
|
|
|
746 {
|
|
|
747 int i = 0;
|
|
|
748 for (; i < MHASH_PRIME; i++)
|
|
|
749 {
|
|
|
750 MHASH_HITS[i].n_hits = 0;
|
|
|
751 MHASH_HITS[i].addr = 0;
|
|
|
752 MHASH_HITS[i].handle = 0;
|
|
|
753 }
|
|
|
754 }
|
|
|
755
|
|
|
756 /* Compute the hash value for an address. */
|
|
|
757 static int
|
|
|
758 MHASH (VM_ADDR addr)
|
|
|
759 {
|
|
|
760 unsigned int addr_shift = (unsigned int)(addr) >> USELESS_LOWER_ADDRESS_BITS;
|
|
|
761 int hval = addr_shift % MHASH_PRIME; /* We could have addresses which are -ve
|
|
|
762 when converted to signed ints */
|
|
|
763 return ((hval >= 0) ? hval : MHASH_PRIME + hval);
|
|
|
764 }
|
|
|
765
|
|
|
766 /* Add a VM address with it's corresponding handle to the table. */
|
|
|
767 static void
|
|
|
768 MHASH_ADD (VM_ADDR addr, MMAP_HANDLE h)
|
|
|
769 {
|
|
|
770 int kVal = MHASH( addr );
|
|
|
771 if (MHASH_HITS[kVal].n_hits++ == 0)
|
|
|
772 { /* Only overwrite the table if there were no hits so far. */
|
|
|
773 MHASH_HITS[kVal].addr = addr;
|
|
|
774 MHASH_HITS[kVal].handle = h;
|
|
|
775 }
|
|
|
776 }
|
|
|
777
|
|
|
778 /* Delete a VM address entry from the hash table. */
|
|
|
779 static void
|
|
|
780 MHASH_DEL (VM_ADDR addr)
|
|
|
781 {
|
|
|
782 int kVal = MHASH( addr );
|
|
|
783 MHASH_HITS[kVal].n_hits--;
|
|
|
784 if (addr == MHASH_HITS[kVal].addr)
|
|
|
785 {
|
|
|
786 MHASH_HITS[kVal].addr = 0; /* Invalidate cache. */
|
|
|
787 MHASH_HITS[kVal].handle = 0;
|
|
|
788 }
|
|
|
789 }
|
|
|
790
|
|
|
791 /* End of hash buckets */
|
|
|
792
|
|
|
793 /* Metering malloc performance. */
|
|
|
794 #ifdef MMAP_METERING
|
|
|
795 /* If we're metering, we introduce some extra symbols to aid the noble
|
|
|
796 cause of bloating XEmacs core size. */
|
|
|
797
|
|
|
798 Lisp_Object Qmm_times_mapped;
|
|
|
799 Lisp_Object Qmm_pages_mapped;
|
|
|
800 Lisp_Object Qmm_times_unmapped;
|
|
|
801 Lisp_Object Qmm_times_remapped;
|
|
|
802 Lisp_Object Qmm_didnt_copy;
|
|
|
803 Lisp_Object Qmm_pages_copied;
|
|
|
804 Lisp_Object Qmm_average_bumpval;
|
|
|
805 Lisp_Object Qmm_wastage;
|
|
|
806 Lisp_Object Qmm_live_pages;
|
|
|
807 Lisp_Object Qmm_addr_looked_up;
|
|
|
808 Lisp_Object Qmm_hash_worked;
|
|
|
809 Lisp_Object Qmm_addrlist_size;
|
|
|
810
|
|
|
811 #define M_Map 0 /* How many times allocated? */
|
|
|
812 #define M_Pages_Map 1 /* How many pages allocated? */
|
|
|
813 #define M_Unmap 2 /* How many times freed? */
|
|
|
814 #define M_Remap 3 /* How many times increased in size? */
|
|
|
815 #define M_Didnt_Copy 4 /* How many times didn't need to copy? */
|
|
|
816 #define M_Copy_Pages 5 /* Total # pages copied */
|
|
|
817 #define M_Average_Bumpval 6 /* Average bump value */
|
|
|
818 #define M_Wastage 7 /* Remaining (unused space) */
|
|
|
819 #define M_Live_Pages 8 /* #live pages */
|
|
|
820 #define M_Address_Lookup 9 /* How many times did we need to check if an addr is in the block? */
|
|
|
821 #define M_Hash_Worked 10 /* How many times did the simple hash check work? */
|
|
|
822 #define M_Addrlist_Size 11 /* What is the size of the XEmacs memory map? */
|
|
|
823
|
|
|
824 #define N_Meterables 12 /* Total number of meterables */
|
|
|
825 #define MEMMETER(x) {x;}
|
|
|
826 #define MVAL(x) (meter[x])
|
|
|
827 #define MLVAL(x) (make_int (meter[x]))
|
|
|
828 static int meter[N_Meterables];
|
|
|
829
|
|
20
|
830 DEFUN ("mmap-allocator-status", Fmmap_allocator_status, 0, 0, 0, /*
|
|
0
|
831 Return some information about mmap-based allocator.
|
|
|
832
|
|
|
833 mmap-addrlist-size: number of entries in address picking list.
|
|
|
834 mmap-times-mapped: number of times r_alloc was called.
|
|
|
835 mmap-pages-mapped: number of pages mapped by r_alloc calls only.
|
|
|
836 mmap-times-unmapped: number of times r_free was called.
|
|
|
837 mmap-times-remapped: number of times r_re_alloc was called.
|
|
|
838 mmap-didnt-copy: number of times re-alloc didn\'t have to move the block.
|
|
|
839 mmap-pages-copied: total number of pages copied.
|
|
|
840 mmap-average-bumpval: average increase in size demanded to re-alloc.
|
|
|
841 mmap-wastage: total number of bytes allocated, but not currently in use.
|
|
|
842 mmap-live-pages: total number of pages live.
|
|
20
|
843 */
|
|
|
844 ())
|
|
0
|
845 {
|
|
|
846 Lisp_Object result;
|
|
|
847
|
|
|
848 result = Fcons (Fcons (Qmm_addrlist_size, MLVAL (M_Addrlist_Size)), Qnil);
|
|
|
849 result = Fcons (Fcons (Qmm_hash_worked, MLVAL (M_Hash_Worked)), result);
|
|
|
850 result = Fcons (Fcons (Qmm_addr_looked_up, MLVAL (M_Address_Lookup)), result);
|
|
|
851 result = Fcons (Fcons (Qmm_live_pages, MLVAL (M_Live_Pages)), result);
|
|
|
852 result = Fcons (Fcons (Qmm_wastage, MLVAL (M_Wastage)), result);
|
|
|
853 result = Fcons (Fcons (Qmm_average_bumpval, MLVAL (M_Average_Bumpval)),
|
|
|
854 result);
|
|
|
855 result = Fcons (Fcons (Qmm_pages_copied, MLVAL (M_Copy_Pages)), result);
|
|
|
856 result = Fcons (Fcons (Qmm_didnt_copy, MLVAL (M_Didnt_Copy)), result);
|
|
|
857 result = Fcons (Fcons (Qmm_times_remapped, MLVAL (M_Remap)), result);
|
|
|
858 result = Fcons (Fcons (Qmm_times_unmapped, MLVAL (M_Unmap)), result);
|
|
|
859 result = Fcons (Fcons (Qmm_pages_mapped, MLVAL (M_Pages_Map)), result);
|
|
|
860 result = Fcons (Fcons (Qmm_times_mapped, MLVAL (M_Map)), result);
|
|
|
861
|
|
|
862 return result;
|
|
|
863 }
|
|
|
864
|
|
|
865 #else /* !MMAP_METERING */
|
|
|
866
|
|
|
867 #define MEMMETER(x)
|
|
|
868 #define MVAL(x)
|
|
|
869
|
|
|
870 #endif /* MMAP_METERING */
|
|
|
871
|
|
|
872 static MMAP_HANDLE
|
|
|
873 find_mmap_handle (POINTER *alias)
|
|
|
874 {
|
|
|
875 int kval = MHASH( *alias );
|
|
|
876 MEMMETER( MVAL(M_Address_Lookup)++ )
|
|
|
877 switch( MHASH_HITS[kval].n_hits)
|
|
|
878 {
|
|
|
879 case 0:
|
|
|
880 MEMMETER( MVAL( M_Hash_Worked )++ )
|
|
|
881 return 0;
|
|
|
882
|
|
|
883 case 1:
|
|
|
884 if (*alias == MHASH_HITS[kval].addr)
|
|
|
885 {
|
|
|
886 MEMMETER( MVAL( M_Hash_Worked) ++ );
|
|
|
887 return MHASH_HITS[kval].handle;
|
|
|
888 }
|
|
|
889 /* FALL THROUGH */
|
|
|
890 default:
|
|
|
891 return find_mmap_handle_lsearch( alias );
|
|
|
892 } /* switch */
|
|
|
893 }
|
|
|
894
|
|
|
895 /*
|
|
|
896 Some kernels don't like being asked to pick addresses for mapping
|
|
|
897 themselves---IRIX is known to become extremely slow if mmap is
|
|
|
898 passed a ZERO as the first argument. In such cases, we use an
|
|
|
899 address map which is managed local to the XEmacs process. The
|
|
|
900 address map maintains an ordered linked list of (address, size,
|
|
|
901 occupancy) triples ordered by the absolute address. Initially, a
|
|
|
902 large address area is marked as being empty. The address picking
|
|
|
903 scheme takes bites off the first block which is still empty and
|
|
|
904 large enough. If mmap with the specified address fails, it is
|
|
|
905 marked unavailable and not attempted thereafter. The scheme will
|
|
|
906 keep fragmenting the large empty block until it finds an address
|
|
|
907 which can be successfully mmapped, or until there are no free
|
|
|
908 blocks of the given size left.
|
|
|
909
|
|
|
910 Note that this scheme, given it's first-fit strategy, is prone to
|
|
2
|
911 fragmentation of the first part of memory earmarked for this
|
|
0
|
912 purpose. [ACP Vol I]. We can't use the workaround of using a
|
|
|
913 randomized first fit because we don't want to presume too much
|
|
|
914 about the memory map. Instead, we try to coalesce empty or
|
|
|
915 unavailable blocks at any available opportunity. */
|
|
|
916
|
|
70
|
917 static void Addr_Block_initialize(); /* Initialization procedure for address picking scheme */
|
|
|
918 static VM_ADDR New_Addr_Block( SIZE sz ); /* Get a suitable VM_ADDR via mmap */
|
|
|
919 static void Free_Addr_Block( VM_ADDR addr, SIZE sz ); /* Free a VM_ADDR allocated via New_Addr_Block */
|
|
0
|
920
|
|
|
921 #ifdef MMAP_GENERATE_ADDRESSES
|
|
|
922 /* Implementation of the three calls for address picking when XEmacs is incharge */
|
|
|
923
|
|
|
924 /* The enum denotes the status of the following block. */
|
|
|
925 typedef enum { empty = 0, occupied, unavailable } addr_status;
|
|
|
926
|
|
|
927 typedef struct addr_chain
|
|
|
928 {
|
|
|
929 POINTER addr;
|
|
|
930 SIZE sz;
|
|
|
931 addr_status flag;
|
|
|
932 struct addr_chain *next;
|
|
|
933 } ADDRESS_BLOCK, *ADDRESS_CHAIN;
|
|
|
934 /* NB: empty and unavailable blocks are concatenated. */
|
|
|
935
|
|
|
936 static ADDRESS_CHAIN addr_chain = 0;
|
|
|
937 /* Start off the address block chain with a humongous address block
|
|
|
938 which is empty to start with. Note that addr_chain is invariant
|
|
|
939 WRT the addition/deletion of address blocks because of the assert
|
|
|
940 in Coalesce() and the strict ordering of blocks by their address
|
|
|
941 */
|
|
|
942 static void Addr_Block_initialize()
|
|
|
943 {
|
|
|
944 MEMMETER( MVAL( M_Addrlist_Size )++)
|
|
|
945 addr_chain = (ADDRESS_CHAIN) UNDERLYING_MALLOC( sizeof( ADDRESS_BLOCK ));
|
|
|
946 addr_chain->next = 0; /* Last block in chain */
|
|
|
947 addr_chain->sz = 0x0c000000; /* Size */
|
|
|
948 addr_chain->addr = (POINTER) (0x04000000 | DATA_SEG_BITS);
|
|
|
949 addr_chain->flag = empty;
|
|
|
950 }
|
|
|
951
|
|
|
952 /* Coalesce address blocks if they are contiguous. Only empty and
|
|
|
953 unavailable slots are coalesced. */
|
|
|
954 static void Coalesce_Addr_Blocks()
|
|
|
955 {
|
|
|
956 ADDRESS_CHAIN p;
|
|
|
957 for (p = addr_chain; p; p = p->next)
|
|
|
958 {
|
|
|
959 while (p->next && p->flag == p->next->flag)
|
|
|
960 {
|
|
|
961 ADDRESS_CHAIN np;
|
|
|
962 np = p->next;
|
|
|
963
|
|
|
964 if (p->flag == occupied) break; /* No cigar */
|
|
|
965
|
|
|
966 /* Check if the addresses are contiguous. */
|
|
|
967 if (p->addr + p->sz != np->addr) break;
|
|
|
968
|
|
|
969 MEMMETER( MVAL( M_Addrlist_Size )--)
|
|
|
970 /* We can coalesce these two. */
|
|
|
971 p->sz += np->sz;
|
|
|
972 p->next = np->next;
|
|
|
973 assert( np != addr_chain ); /* We're not freeing the head of the list. */
|
|
|
974 UNDERLYING_FREE( np );
|
|
|
975 }
|
|
|
976 } /* for all p */
|
|
|
977 }
|
|
|
978
|
|
|
979 /* Get an empty address block of specified size. */
|
|
|
980 static VM_ADDR New_Addr_Block( SIZE sz )
|
|
|
981 {
|
|
|
982 ADDRESS_CHAIN p = addr_chain;
|
|
|
983 VM_ADDR new_addr = VM_FAILURE_ADDR;
|
|
|
984 for (; p; p = p->next)
|
|
|
985 {
|
|
|
986 if (p->flag == empty && p->sz > sz)
|
|
|
987 {
|
|
|
988 /* Create a new entry following p which is empty. */
|
|
|
989 ADDRESS_CHAIN remainder = (ADDRESS_CHAIN) UNDERLYING_MALLOC( sizeof( ADDRESS_BLOCK ) );
|
|
|
990 remainder->next = p->next;
|
|
|
991 remainder->flag = empty;
|
|
|
992 remainder->addr = p->addr + sz;
|
|
|
993 remainder->sz = p->sz - sz;
|
|
|
994
|
|
|
995 MEMMETER( MVAL( M_Addrlist_Size )++)
|
|
|
996
|
|
|
997 /* Now make p become an occupied block with the appropriate size */
|
|
|
998 p->next = remainder;
|
|
|
999 p->sz = sz;
|
|
|
1000 new_addr = mmap( (VM_ADDR) p->addr, p->sz, PROT_READ|PROT_WRITE,
|
|
|
1001 MAP_FLAGS, DEV_ZERO_FD, 0 );
|
|
|
1002 if (new_addr == VM_FAILURE_ADDR)
|
|
|
1003 {
|
|
|
1004 p->flag = unavailable;
|
|
|
1005 continue;
|
|
|
1006 }
|
|
|
1007 p->flag = occupied;
|
|
|
1008 break;
|
|
|
1009 }
|
|
|
1010 }
|
|
|
1011 Coalesce_Addr_Blocks();
|
|
|
1012 return new_addr;
|
|
|
1013 }
|
|
|
1014
|
|
|
1015 /* Free an address block. We mark the block as being empty, and attempt to
|
|
|
1016 do any coalescing that may have resulted from this. */
|
|
|
1017 static void Free_Addr_Block( VM_ADDR addr, SIZE sz )
|
|
|
1018 {
|
|
|
1019 ADDRESS_CHAIN p = addr_chain;
|
|
|
1020 for (; p; p = p->next )
|
|
|
1021 {
|
|
|
1022 if (p->addr == addr)
|
|
|
1023 {
|
|
|
1024 if (p->sz != sz) abort(); /* ACK! Shouldn't happen at all. */
|
|
|
1025 munmap( (VM_ADDR) p->addr, p->sz );
|
|
|
1026 p->flag = empty;
|
|
|
1027 break;
|
|
|
1028 }
|
|
|
1029 }
|
|
|
1030 if (!p) abort(); /* Can't happen... we've got a block to free which is not in
|
|
|
1031 the address list. */
|
|
|
1032 Coalesce_Addr_Blocks();
|
|
|
1033 }
|
|
|
1034 #else /* !MMAP_GENERATE_ADDRESSES */
|
|
|
1035 /* This is an alternate (simpler) implementation in cases where the
|
|
|
1036 address is picked by the kernel. */
|
|
|
1037
|
|
70
|
1038 static void Addr_Block_initialize()
|
|
|
1039 {} /* Nothing. */
|
|
0
|
1040
|
|
|
1041 static VM_ADDR New_Addr_Block( SIZE sz )
|
|
|
1042 {
|
|
|
1043 return mmap( 0, sz, PROT_READ|PROT_WRITE, MAP_FLAGS,
|
|
|
1044 DEV_ZERO_FD, 0 );
|
|
|
1045 }
|
|
|
1046
|
|
|
1047 static void Free_Addr_Block( VM_ADDR addr, SIZE sz )
|
|
|
1048 {
|
|
|
1049 munmap( addr, sz );
|
|
|
1050 }
|
|
|
1051
|
|
|
1052 #endif /* MMAP_GENERATE_ADDRESSES */
|
|
|
1053
|
|
|
1054
|
|
|
1055 /* IMPLEMENTATION OF EXPORTED RELOCATOR INTERFACE */
|
|
|
1056
|
|
|
1057 /*
|
|
|
1058 r_alloc( POINTER, SIZE ): Allocate a relocatable area with the start
|
|
|
1059 address aliased to the first parameter.
|
|
|
1060 */
|
|
|
1061
|
|
|
1062 POINTER r_alloc (POINTER *ptr, SIZE size);
|
|
|
1063 POINTER
|
|
|
1064 r_alloc (POINTER *ptr, SIZE size)
|
|
|
1065 {
|
|
|
1066 MMAP_HANDLE mh;
|
|
|
1067
|
|
|
1068 switch(r_alloc_initialized)
|
|
|
1069 {
|
|
|
1070 case 0:
|
|
|
1071 abort();
|
|
|
1072 case 1:
|
|
|
1073 *ptr = UNDERLYING_MALLOC(size);
|
|
|
1074 break;
|
|
|
1075 default:
|
|
|
1076 mh = new_mmap_handle( size );
|
|
|
1077 if (mh)
|
|
|
1078 {
|
|
|
1079 SIZE hysteresis = (mmap_hysteresis > 0 ? mmap_hysteresis : 0);
|
|
|
1080 SIZE mmapped_size = ROUNDUP( size + hysteresis );
|
|
|
1081 MEMMETER( MVAL(M_Map)++ )
|
|
|
1082 MEMMETER( MVAL(M_Pages_Map) += (mmapped_size/page_size) )
|
|
|
1083 MEMMETER( MVAL(M_Wastage) += mmapped_size - size )
|
|
|
1084 MEMMETER( MVAL(M_Live_Pages) += (mmapped_size/page_size) )
|
|
|
1085 mh->vm_addr = New_Addr_Block( mmapped_size );
|
|
|
1086 if (mh->vm_addr == VM_FAILURE_ADDR) {
|
|
|
1087 free_mmap_handle( mh ); /* Free the loser */
|
|
|
1088 *ptr = 0;
|
|
|
1089 return 0; /* ralloc failed due to mmap() failure. */
|
|
|
1090 }
|
|
|
1091 MHASH_ADD( mh->vm_addr, mh );
|
|
|
1092 mh->space_for = mmapped_size;
|
|
|
1093 mh->aliased_address = ptr;
|
|
|
1094 *ptr = mh->vm_addr;
|
|
|
1095 }
|
|
|
1096 else
|
|
|
1097 *ptr = 0; /* Malloc of block failed */
|
|
|
1098 break;
|
|
|
1099 }
|
|
|
1100 return *ptr;
|
|
|
1101 }
|
|
|
1102
|
|
|
1103 /* Free a bloc of relocatable storage whose data is pointed to by PTR.
|
|
|
1104 Store 0 in *PTR to show there's no block allocated. */
|
|
|
1105
|
|
|
1106 void r_alloc_free (POINTER *ptr);
|
|
|
1107 void
|
|
|
1108 r_alloc_free (POINTER *ptr)
|
|
|
1109 {
|
|
|
1110 switch( r_alloc_initialized) {
|
|
|
1111 case 0:
|
|
|
1112 abort();
|
|
|
1113
|
|
|
1114 case 1:
|
|
|
1115 UNDERLYING_FREE( *ptr ); /* Certain this is from the heap. */
|
|
|
1116 break;
|
|
|
1117
|
|
|
1118 default:
|
|
|
1119 {
|
|
|
1120 MMAP_HANDLE dead_handle = find_mmap_handle( ptr );
|
|
|
1121 /* Check if we've got it. */
|
|
|
1122 if (dead_handle == 0) /* Didn't find it in the list of mmap handles */
|
|
|
1123 {
|
|
|
1124 UNDERLYING_FREE( *ptr );
|
|
|
1125 }
|
|
|
1126 else
|
|
|
1127 {
|
|
|
1128 MEMMETER( MVAL( M_Wastage ) -= (dead_handle->space_for - dead_handle->size) )
|
|
|
1129 MEMMETER( MVAL( M_Live_Pages ) -= (dead_handle->space_for / page_size ))
|
|
|
1130 MEMMETER(MVAL(M_Unmap)++)
|
|
|
1131 MHASH_DEL( dead_handle->vm_addr );
|
|
|
1132 Free_Addr_Block( dead_handle->vm_addr, dead_handle->space_for );
|
|
|
1133 free_mmap_handle (dead_handle);
|
|
|
1134 }
|
|
|
1135 }
|
|
|
1136 break;
|
|
|
1137 } /* r_alloc_initialized */
|
|
|
1138 *ptr = 0; /* Zap the pointer's contents. */
|
|
|
1139 }
|
|
|
1140
|
|
|
1141 /* Given a pointer at address PTR to relocatable data, resize it to SIZE.
|
|
|
1142
|
|
|
1143 Change *PTR to reflect the new bloc, and return this value.
|
|
|
1144
|
|
|
1145 If more memory cannot be allocated, then leave *PTR unchanged, and
|
|
|
1146 return zero. */
|
|
|
1147
|
|
|
1148 POINTER r_re_alloc (POINTER *ptr, SIZE sz);
|
|
|
1149 POINTER
|
|
|
1150 r_re_alloc (POINTER *ptr, SIZE sz)
|
|
|
1151 {
|
|
|
1152 if (r_alloc_initialized == 0)
|
|
|
1153 {
|
|
|
1154 abort ();
|
|
|
1155 return 0; /* suppress compiler warning */
|
|
|
1156 }
|
|
|
1157 else if (r_alloc_initialized == 1)
|
|
|
1158 {
|
|
|
1159 POINTER tmp = realloc(*ptr, sz);
|
|
|
1160 if (tmp)
|
|
|
1161 *ptr = tmp;
|
|
|
1162 return tmp;
|
|
|
1163 }
|
|
|
1164 else
|
|
|
1165 {
|
|
|
1166 SIZE hysteresis = (mmap_hysteresis > 0 ? mmap_hysteresis : 0);
|
|
|
1167 SIZE actual_sz = ROUNDUP( sz + hysteresis );
|
|
|
1168 MMAP_HANDLE h = find_mmap_handle( ptr );
|
|
|
1169 VM_ADDR new_vm_addr;
|
|
|
1170
|
|
|
1171 if ( h == 0 ) /* Was allocated using malloc. */
|
|
|
1172 {
|
|
|
1173 POINTER tmp = UNDERLYING_REALLOC(*ptr, sz);
|
|
|
1174 if (tmp)
|
|
|
1175 *ptr = tmp;
|
|
|
1176 return tmp;
|
|
|
1177 }
|
|
|
1178
|
|
|
1179 MEMMETER(
|
|
|
1180 MVAL(M_Average_Bumpval) =
|
|
|
1181 (((double) MVAL(M_Remap) * MVAL(M_Average_Bumpval)) + (sz - h->size))
|
|
|
1182 / (double) (MVAL(M_Remap) + 1))
|
|
|
1183 MEMMETER(MVAL(M_Remap)++)
|
|
|
1184 if (h->space_for > sz) /* We've got some more room */
|
|
|
1185 { /* Also, if a shrinkage was asked for. */
|
|
|
1186 MEMMETER( MVAL(M_Didnt_Copy)++ )
|
|
|
1187 MEMMETER( MVAL(M_Wastage) -= (sz - h->size))
|
|
|
1188 /* We're pretty dumb at handling shrinkage. We should check for
|
|
|
1189 a larger gap than the standard hysteresis allowable, and if so,
|
|
|
1190 shrink the number of pages. Right now, we simply reset the size
|
|
|
1191 component and return. */
|
|
|
1192 h->size = sz;
|
|
|
1193 return *ptr;
|
|
|
1194 }
|
|
|
1195
|
|
|
1196 new_vm_addr = New_Addr_Block( actual_sz );
|
|
|
1197 if (new_vm_addr == VM_FAILURE_ADDR)
|
|
|
1198 {/* Failed to realloc. */
|
|
|
1199 /* *ptr = 0; */
|
|
|
1200 return 0;
|
|
|
1201 }
|
|
|
1202
|
|
|
1203 MHASH_ADD( new_vm_addr, h );
|
|
|
1204 /* We got a block OK: now we should move the old contents to the
|
|
|
1205 new address. We use the old size of this block. */
|
|
|
1206 memmove(new_vm_addr, h->vm_addr, h->size);
|
|
|
1207 MHASH_DEL( h->vm_addr );
|
|
|
1208 Free_Addr_Block( h->vm_addr, h->space_for ); /* Unmap old area. */
|
|
|
1209
|
|
|
1210 MEMMETER( MVAL( M_Copy_Pages ) += (h->space_for/page_size) )
|
|
|
1211 MEMMETER( MVAL( M_Live_Pages ) -= (h->space_for / page_size))
|
|
|
1212 MEMMETER( MVAL( M_Live_Pages ) += (actual_sz / page_size))
|
|
|
1213 MEMMETER( MVAL( M_Wastage ) -= (h->space_for - h->size))
|
|
|
1214 MEMMETER( MVAL( M_Wastage ) += (actual_sz - sz) )
|
|
|
1215
|
|
|
1216 /* Update block datastructure. */
|
|
|
1217 h->space_for = actual_sz; /* New total space */
|
|
|
1218 h->size = sz; /* New (requested) size */
|
|
|
1219 h->vm_addr = new_vm_addr; /* New VM start address */
|
|
|
1220 h->aliased_address = ptr; /* Change alias to reflect block relocation. */
|
|
|
1221 *ptr = h->vm_addr;
|
|
|
1222 return *ptr;
|
|
|
1223 }
|
|
|
1224 }
|
|
|
1225
|
|
|
1226
|
|
|
1227 /* Initialize various things for memory allocation.
|
|
|
1228 */
|
|
|
1229 void
|
|
|
1230 init_ralloc (void)
|
|
|
1231 {
|
|
|
1232 int i = 0;
|
|
|
1233 if (r_alloc_initialized > 1)
|
|
|
1234 return; /* used to return 1 */
|
|
|
1235
|
|
|
1236 if (++r_alloc_initialized == 1)
|
|
|
1237 return; /* used to return 1 */
|
|
|
1238
|
|
|
1239 Addr_Block_initialize(); /* Initialize the address picker, if required. */
|
|
|
1240 page_size = PAGE;
|
|
|
1241 assert( page_size > 0 ); /* getpagesize() bogosity check. */
|
|
|
1242
|
|
|
1243 #ifndef MAP_ANONYMOUS
|
|
|
1244 DEV_ZERO_FD = open( "/dev/zero", O_RDWR );
|
|
|
1245 if (DEV_ZERO_FD < 0)
|
|
|
1246 /* Failed. Perhaps we should abort here? */
|
|
|
1247 return; /* used to return 0 */
|
|
|
1248 #endif
|
|
|
1249
|
|
|
1250 #ifdef MMAP_METERING
|
|
|
1251 for(i = 0; i < N_Meterables; i++ )
|
|
|
1252 {
|
|
|
1253 meter[i] = 0;
|
|
|
1254 }
|
|
|
1255 #endif /* MMAP_METERING */
|
|
|
1256 }
|
|
|
1257
|
|
|
1258 void
|
|
|
1259 syms_of_ralloc (void)
|
|
|
1260 {
|
|
|
1261 #ifdef MMAP_METERING
|
|
70
|
1262 defsymbol (&Qmm_times_mapped, "mmap-times-mapped" );
|
|
|
1263 defsymbol (&Qmm_pages_mapped, "mmap-pages-mapped" );
|
|
|
1264 defsymbol (&Qmm_times_unmapped, "mmap-times-unmapped" );
|
|
|
1265 defsymbol (&Qmm_times_remapped, "mmap-times-remapped" );
|
|
|
1266 defsymbol (&Qmm_didnt_copy, "mmap-didnt-copy" );
|
|
|
1267 defsymbol (&Qmm_pages_copied, "mmap-pages-copied" );
|
|
|
1268 defsymbol (&Qmm_average_bumpval, "mmap-average-bumpval" );
|
|
|
1269 defsymbol (&Qmm_wastage, "mmap-wastage" );
|
|
|
1270 defsymbol (&Qmm_live_pages, "mmap-live-pages" );
|
|
|
1271 defsymbol (&Qmm_addr_looked_up, "mmap-had-to-look-up-address" );
|
|
|
1272 defsymbol (&Qmm_hash_worked, "mmap-hash-table-worked" );
|
|
|
1273 defsymbol (&Qmm_addrlist_size, "mmap-addrlist-size" );
|
|
20
|
1274 DEFSUBR (Fmmap_allocator_status);
|
|
0
|
1275 #endif /* MMAP_METERING */
|
|
|
1276 }
|
|
|
1277
|
|
|
1278 void
|
|
|
1279 vars_of_ralloc (void)
|
|
|
1280 {
|
|
|
1281 DEFVAR_INT ("mmap-hysteresis", &mmap_hysteresis /*
|
|
|
1282 Extra room left at the end of an allocated arena,
|
|
|
1283 so that a re-alloc requesting extra space smaller than this
|
|
|
1284 does not actually cause a new arena to be allocated.
|
|
|
1285
|
|
|
1286 A negative value is considered equal to zero. This is the
|
|
|
1287 minimum amount of space guaranteed to be left at the end of
|
|
|
1288 the arena. Because allocation happens in multiples of the OS
|
|
|
1289 page size, it is possible for more space to be left unused.
|
|
|
1290 */ );
|
|
|
1291 mmap_hysteresis = 0;
|
|
|
1292 }
|
|
|
1293
|
|
|
1294 #endif /* HAVE_MMAP */
|
