Mercurial > hg > xemacs-beta
annotate src/mc-alloc.c @ 5750:66d2f63df75f
Correct some spelling and formatting in behavior.el.
Mentioned in tracker issue 826, the third thing mentioned there (the file
name at the bottom of the file) had already been fixed.
lisp/ChangeLog addition:
2013-08-05 Aidan Kehoe <kehoea@parhasard.net>
* behavior.el:
(override-behavior):
Correct some spelling and formatting here, thank you Steven
Mitchell in tracker issue 826.
| author | Aidan Kehoe <kehoea@parhasard.net> |
|---|---|
| date | Mon, 05 Aug 2013 10:05:32 +0100 |
| parents | 56144c8593a8 |
| children |
| rev | line source |
|---|---|
| 2720 | 1 /* New size-based allocator for XEmacs. |
| 2 Copyright (C) 2005 Marcus Crestani. | |
|
5042
f395ee7ad844
Fix some compile warnings, make vdb test code conditional on DEBUG_XEMACS
Ben Wing <ben@xemacs.org>
parents:
4125
diff
changeset
|
3 Copyright (C) 2010 Ben Wing. |
| 2720 | 4 |
| 5 This file is part of XEmacs. | |
| 6 | |
|
5402
308d34e9f07d
Changed bulk of GPLv2 or later files identified by script
Mats Lidell <matsl@xemacs.org>
parents:
5238
diff
changeset
|
7 XEmacs is free software: you can redistribute it and/or modify it |
| 2720 | 8 under the terms of the GNU General Public License as published by the |
|
5402
308d34e9f07d
Changed bulk of GPLv2 or later files identified by script
Mats Lidell <matsl@xemacs.org>
parents:
5238
diff
changeset
|
9 Free Software Foundation, either version 3 of the License, or (at your |
|
308d34e9f07d
Changed bulk of GPLv2 or later files identified by script
Mats Lidell <matsl@xemacs.org>
parents:
5238
diff
changeset
|
10 option) any later version. |
| 2720 | 11 |
| 12 XEmacs is distributed in the hope that it will be useful, but WITHOUT | |
| 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 15 for more details. | |
| 16 | |
| 17 You should have received a copy of the GNU General Public License | |
|
5402
308d34e9f07d
Changed bulk of GPLv2 or later files identified by script
Mats Lidell <matsl@xemacs.org>
parents:
5238
diff
changeset
|
18 along with XEmacs. If not, see <http://www.gnu.org/licenses/>. */ |
| 2720 | 19 |
| 20 /* Synched up with: Not in FSF. */ | |
| 21 | |
|
5238
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
22 /* |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
23 The New Allocator |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
24 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
25 The ideas and algorithms are based on the allocator of the |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
26 Boehm-Demers-Weiser conservative garbage collector. See |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
27 http://www.hpl.hp.com/personal/Hans_ Boehm/gc/index.html. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
28 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
29 The new allocator is enabled when the new garbage collector |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
30 is enabled (with `--with-newgc'). The implementation of |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
31 the new garbage collector is in gc.c. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
32 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
33 The new allocator takes care of: |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
34 - allocating objects in a write-barrier-friendly way |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
35 - manage object's mark bits |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
36 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
37 Three-Level Allocation |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
38 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
39 The new allocator efficiently manages the allocation of Lisp |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
40 objects by minimizing the number of times malloc() and free() are |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
41 called. The allocation process has three layers of abstraction: |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
42 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
43 1. It allocates memory in very large chunks called heap sections. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
44 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
45 2. The heap sections are subdivided into pages. The page size is |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
46 determined by the constant PAGE_SIZE. It holds the size of a page |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
47 in bytes. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
48 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
49 3. One page consists of one or more cells. Each cell represents |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
50 a memory location for an object. The cells on one page all have |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
51 the same size, thus every page only contains equal-sized |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
52 objects. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
53 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
54 If an object is bigger than page size, it is allocated on a |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
55 multi-page. Then there is only one cell on a multi-page (the cell |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
56 covers the full multi-page). Is an object smaller than 1/2 PAGE_SIZE, |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
57 a page contains several objects and several cells. There |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
58 is only one cell on a page for object sizes from 1/2 PAGE_SIZE to |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
59 PAGE_SIZE (whereas multi-pages always contain 2 only one |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
60 cell). Only in layer one malloc() and free() are called. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
61 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
62 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
63 Size Classes and Page Lists |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
64 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
65 Meta-information about every page and multi-page is kept in a page |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
66 header. The page header contains some bookkeeping information like |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
67 number of used and free cells, and pointers to other page |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
68 headers. The page headers are linked in a page list. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
69 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
70 Every page list builds a size class. A size class contains all |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
71 pages (linked via page headers) for objects of the same size. The |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
72 new allocator does not group objects based on their type, it groups |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
73 objects based on their sizes. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
74 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
75 Here is an example: A cons contains a lrecord_header, a car and cdr |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
76 field. Altogether it uses 12 bytes of memory (on 32 bits |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
77 machines). All conses are allocated on pages with a cell size of 12 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
78 bytes. All theses pages are kept together in a page list, which |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
79 represents the size class for 12 bytes objects. But this size class |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
80 is not exclusively for conses only. Other objects, which are also |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
81 12 bytes big (e.g. weak-boxes), are allocated in the same size |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
82 class and on the same pages. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
83 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
84 The number of size classes is customizable, so is the size step |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
85 between successive size classes. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
86 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
87 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
88 Used and Unused Heap |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
89 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
90 The memory which is managed by the allocator can be divided in two |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
91 logical parts: |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
92 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
93 The used heap contains pages, on which objects are allocated. These |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
94 pages are com- pletely or partially occupied. In the used heap, it |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
95 is important to quickly find a free spot for a new |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
96 object. Therefore the size classes of the used heap are defined by |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
97 the size of the cells on the pages. The size classes should match |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
98 common object sizes, to avoid wasting memory. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
99 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
100 The unused heap only contains completely empty pages. They have |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
101 never been used or have been freed completely again. In the unused |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
102 heap, the size of consecutive memory tips the scales. A page is the |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
103 smallest entity which is asked for. Therefore, the size classes of |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
104 the unused heap are defined by the number of consecutive pages. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
105 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
106 The parameters for the different size classes can be adjusted |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
107 independently, see `configurable values' below. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
108 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
109 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
110 The Allocator's Data Structures |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
111 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
112 The struct `mc_allocator_globals holds' all the data structures |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
113 that the new allocator uses (lists of used and unused pages, mark |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
114 bits, etc.). |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
115 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
116 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
117 Mapping of Heap Pointers to Page Headers |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
118 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
119 For caching benefits, the page headers and mark bits are stored |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
120 separately from their associated page. During garbage collection |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
121 (i.e. for marking and freeing objects) it is important to identify |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
122 the page header which is responsible for a given Lisp object. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
123 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
124 To do this task quickly, I added a two level search tree: the upper |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
125 10 bits of the heap pointer are the index of the first level. This |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
126 entry of the first level links to the second level, where the next |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
127 10 bits of the heap pointer are used to identify the page |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
128 header. The remaining bits point to the object relative to the |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
129 page. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
130 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
131 On architectures with more than 32 bits pointers, a hash value of |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
132 the upper bits is used to index into the first level. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
133 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
134 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
135 Mark Bits |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
136 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
137 For caching purposes, the mark bits are no longer kept within the |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
138 objects, they are kept in a separate bit field. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
139 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
140 Every page header has a field for the mark bits of the objects on |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
141 the page. If there are less cells on the page than there fit bits |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
142 in the integral data type EMACS_INT, the mark bits are stored |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
143 directly in this EMACS_INT. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
144 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
145 Otherwise, the mark bits are written in a separate space, with the |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
146 page header pointing to this space. This happens to pages with |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
147 rather small objects: many cells fit on a page, thus many mark bits |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
148 are needed. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
149 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
150 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
151 Allocate Memory |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
152 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
153 Use |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
154 void *mc_alloc (size_t size) |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
155 to request memory from the allocator. This returns a pointer to a |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
156 newly allocated block of memory of given size. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
157 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
158 This is how the new allocator allocates memory: |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
159 1. Determine the size class of the object. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
160 2. Is there already a page in this size class and is there a free |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
161 cell on this page? |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
162 * YES |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
163 3. Unlink free cell from free list, return address of free cell. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
164 DONE. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
165 * NO |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
166 3. Is there a page in the unused heap? |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
167 * YES |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
168 4. Move unused page to used heap. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
169 5. Initialize page header, free list, and mark bits. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
170 6. Unlink first cell from free list, return address of cell. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
171 DONE. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
172 * NO |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
173 4. Expand the heap, add new memory to unused heap |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
174 [go back to 3. and proceed with the YES case]. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
175 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
176 The allocator puts partially filled pages to the front of the page |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
177 list, completely filled ones to the end. That guarantees a fast |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
178 terminating search for free cells. Are there two successive full |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
179 pages at the front of the page list, the complete size class is |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
180 full, a new page has to be added. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
181 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
182 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
183 Expand Heap |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
184 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
185 To expand the heap, a big chunk of contiguous memory is allocated |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
186 using malloc(). These pieces are called heap sections. How big a new |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
187 heap section is (and thus the growth of the heap) is adjustable: See |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
188 MIN_HEAP_INCREASE, MAX_HEAP_INCREASE, and HEAP_GROWTH_DIVISOR below. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
189 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
190 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
191 Free Memory |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
192 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
193 One optimization in XEmacs is that locally used Lisp objects are |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
194 freed manually (the memory is not wasted till the next garbage |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
195 collection). Therefore the new allocator provides this function: |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
196 void mc_free (void *ptr) |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
197 That frees the object pointed to by ptr. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
198 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
199 This function is also used internally during sweep phase of the |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
200 garbage collection. This is how it works in detail: |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
201 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
202 1. Use pointer to identify page header |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
203 (use lookup mechanism described above). |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
204 2. Mark cell as free and hook it into free list. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
205 3. Is the page completely empty? |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
206 * YES |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
207 4. Unlink page from page list. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
208 5. Remove page header, free list, and mark bits. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
209 6. Move page to unused heap. |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
210 * NO |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
211 4. Move page to front of size class (to speed up allocation |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
212 of objects). |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
213 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
214 If the last object of a page is freed, the empty page is returned to |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
215 the unused heap. The allocator tries to coalesce adjacent pages, to |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
216 gain a big piece of contiguous memory. The resulting chunk is hooked |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
217 into the according size class of the unused heap. If this created a |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
218 complete heap section, the heap section is returned to the operating |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
219 system by using free(). |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
220 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
221 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
222 Allocator and Garbage Collector |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
223 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
224 The new allocator simplifies the interface to the Garbage Collector: |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
225 * mark live objects: MARK_[WHITE|GREY|BLACK] (ptr) |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
226 * sweep heap: EMACS_INT mc_sweep (void) |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
227 * run finalizers: EMACS_INT mc_finalize (void) |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
228 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
229 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
230 Allocator and Dumper |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
231 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
232 The new allocator provides special finalization for the portable |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
233 dumper (to save disk space): EMACS_INT mc_finalize_for_disksave (void) |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
234 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
235 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
236 More Information |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
237 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
238 More details can be found in |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
239 http://crestani.de/xemacs/pdf/mc-alloc.pdf . |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
240 |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
241 */ |
|
2cc24c69446c
Document the new allocator and the new garbage collector in gc.c and mc-alloc.c.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5216
diff
changeset
|
242 |
| 2720 | 243 #include <config.h> |
| 3092 | 244 |
| 2720 | 245 #include "lisp.h" |
| 246 #include "mc-alloc.h" | |
| 3092 | 247 #include "getpagesize.h" |
| 248 | |
| 249 | |
| 250 #if 0 | |
| 251 # define USE_MARK_BITS_FREE_LIST 1 | |
| 252 #endif | |
| 253 #if 1 | |
| 254 # define BLOCKTYPE_ALLOC_PAGE_HEADER 1 | |
| 255 #endif | |
| 256 | |
| 257 /* Memory protection needs the real system-dependent pagesize. */ | |
| 258 #ifndef WIN32_NATIVE | |
| 259 #include <unistd.h> /* for getpagesize () */ | |
| 260 #endif | |
| 261 #if defined (HAVE_GETPAGESIZE) | |
| 262 # define SYS_PAGE_SIZE getpagesize () | |
| 263 #elif defined (_SC_PAGESIZE) | |
| 264 # define SYS_PAGE_SIZE sysconf (_SC_PAGESIZE) | |
| 265 #elif defined (_SC_PAGE_SIZE) | |
| 266 # define SYS_PAGE_SIZE sysconf (_SC_PAGE_SIZE) | |
| 267 #elif defined(get_page_size) | |
| 268 # define SYS_PAGE_SIZE get_page_size () | |
| 269 #elif defined(PAGESIZE) | |
| 270 # define SYS_PAGE_SIZE PAGESIZE | |
| 271 #elif defined(PAGE_SIZE) | |
| 272 # define SYS_PAGE_SIZE PAGE_SIZE | |
| 273 #else | |
| 274 /* Valid page sizes are powers of 2. */ | |
| 275 # define SYS_PAGE_SIZE 4096 | |
| 276 #endif | |
| 2720 | 277 |
| 278 | |
| 279 /*--- configurable values ----------------------------------------------*/ | |
| 280 | |
| 281 /* Definition of size classes */ | |
| 282 | |
| 283 /* Heap used list constants: In the used heap, it is important to | |
| 284 quickly find a free spot for a new object. Therefore the size | |
| 285 classes of the used heap are defined by the size of the cells on | |
| 286 the pages. The size classes should match common object sizes, to | |
| 287 avoid wasting memory. */ | |
| 288 | |
| 289 /* Minimum object size in bytes. */ | |
| 3092 | 290 #if BITS_PER_EMACS_INT > 32 |
| 291 # define USED_LIST_MIN_OBJECT_SIZE 16 | |
| 292 #else | |
| 293 # define USED_LIST_MIN_OBJECT_SIZE 8 | |
| 294 #endif | |
| 2720 | 295 |
| 296 /* The step size by which the size classes increase (up to upper | |
| 297 threshold). This many bytes are mapped to a single used list: */ | |
| 3092 | 298 #if BITS_PER_EMACS_INT > 32 |
| 299 # define USED_LIST_LIN_STEP 8 | |
| 300 #else | |
| 301 # define USED_LIST_LIN_STEP 4 | |
| 302 #endif | |
| 2720 | 303 |
| 304 /* The upper threshold should always be set to PAGE_SIZE/2, because if | |
| 305 a object is larger than PAGE_SIZE/2 there is no room for any other | |
| 306 object on this page. Objects this big are kept in the page list of | |
| 307 the multiple pages, since a quick search for free spots is not | |
| 308 needed for this kind of pages (because there are no free spots). | |
| 309 PAGE_SIZES_DIV_2 defines maximum size of a used space list. */ | |
| 3092 | 310 #define USED_LIST_UPPER_THRESHOLD PAGE_SIZE_DIV_2 |
| 2720 | 311 |
| 312 | |
| 313 /* Heap free list constants: In the unused heap, the size of | |
| 314 consecutive memory tips the scales. A page is smallest entity which | |
| 315 is asked for. Therefore, the size classes of the unused heap are | |
| 316 defined by the number of consecutive pages. */ | |
| 317 /* Sizes up to this many pages each have their own free list. */ | |
| 318 #define FREE_LIST_LOWER_THRESHOLD 32 | |
| 319 /* The step size by which the size classes increase (up to upper | |
| 320 threshold). FREE_LIST_LIN_STEP number of sizes are mapped to a | |
| 321 single free list for sizes between FREE_LIST_LOWER_THRESHOLD and | |
| 322 FREE_LIST_UPPER_THRESHOLD. */ | |
| 323 #define FREE_LIST_LIN_STEP 8 | |
| 324 /* Sizes of at least this many pages are mapped to a single free | |
| 325 list. Blocks of memory larger than this number are all kept in a | |
| 326 single list, which makes searching this list slow. But objects that | |
| 327 big are really seldom. */ | |
| 328 #define FREE_LIST_UPPER_THRESHOLD 256 | |
| 329 | |
| 330 | |
| 3092 | 331 /* used heap list count */ |
| 332 #define N_USED_PAGE_LISTS (((USED_LIST_UPPER_THRESHOLD \ | |
| 333 - USED_LIST_MIN_OBJECT_SIZE) \ | |
| 334 / USED_LIST_LIN_STEP) + 1 ) + 1 | |
| 335 | |
| 336 /* free heap list count */ | |
| 337 #define N_FREE_PAGE_LISTS (((FREE_LIST_UPPER_THRESHOLD \ | |
| 338 - FREE_LIST_LOWER_THRESHOLD) \ | |
| 339 / FREE_LIST_LIN_STEP) \ | |
| 340 + FREE_LIST_LOWER_THRESHOLD) | |
| 341 | |
| 342 | |
| 2720 | 343 /* Maximum number of separately added heap sections. */ |
| 344 #if BITS_PER_EMACS_INT > 32 | |
| 345 # define MAX_HEAP_SECTS 2048 | |
| 346 #else | |
| 347 # define MAX_HEAP_SECTS 768 | |
| 348 #endif | |
| 349 | |
| 350 | |
| 351 /* Heap growth constants. Heap increases by any number between the | |
| 352 boundaries (unit is PAGE_SIZE). */ | |
| 3092 | 353 #define MIN_HEAP_INCREASE 256 |
| 2720 | 354 #define MAX_HEAP_INCREASE 256 /* not used */ |
| 355 | |
| 356 /* Every heap growth is calculated like this: | |
| 357 needed_pages + ( HEAP_SIZE / ( PAGE_SIZE * HEAP_GROWTH_DIVISOR )). | |
| 358 So the growth of the heap is influenced by the current size of the | |
| 359 heap, but kept between MIN_HEAP_INCREASE and MAX_HEAP_INCREASE | |
| 360 boundaries. | |
| 361 This reduces the number of heap sectors, the larger the heap grows | |
| 362 the larger are the newly allocated chunks. */ | |
| 363 #define HEAP_GROWTH_DIVISOR 3 | |
| 364 | |
| 365 | |
| 366 /* Zero memory before putting on free lists. */ | |
| 367 #define ZERO_MEM 1 | |
| 368 | |
| 369 | |
| 370 #ifndef CHAR_BIT /* should be included by limits.h */ | |
| 371 # define CHAR_BIT BITS_PER_CHAR | |
| 372 #endif | |
| 373 | |
| 374 | |
| 3092 | 375 |
| 376 /*--- values depending on PAGE_SIZE ------------------------------------*/ | |
| 2720 | 377 |
| 3092 | 378 /* initialized in init_mc_allocator () */ |
| 379 static EMACS_INT log_page_size; | |
| 380 static EMACS_INT page_size_div_2; | |
| 2720 | 381 |
| 3092 | 382 #undef PAGE_SIZE |
| 383 #define PAGE_SIZE SYS_PAGE_SIZE | |
| 384 #define LOG_PAGE_SIZE log_page_size | |
| 385 #define PAGE_SIZE_DIV_2 page_size_div_2 | |
| 2720 | 386 |
| 387 | |
| 388 /* Constants for heap address to page header mapping. */ | |
| 389 #define LOG_LEVEL2_SIZE 10 | |
| 390 #define LEVEL2_SIZE (1 << LOG_LEVEL2_SIZE) | |
| 391 #if BITS_PER_EMACS_INT > 32 | |
| 392 # define USE_HASH_TABLE 1 | |
| 393 # define LOG_LEVEL1_SIZE 11 | |
| 394 #else | |
| 395 # define LOG_LEVEL1_SIZE \ | |
| 396 (BITS_PER_EMACS_INT - LOG_LEVEL2_SIZE - LOG_PAGE_SIZE) | |
| 397 #endif | |
| 398 #define LEVEL1_SIZE (1 << LOG_LEVEL1_SIZE) | |
| 399 | |
| 400 #ifdef USE_HASH_TABLE | |
| 401 # define HASH(hi) ((hi) & (LEVEL1_SIZE - 1)) | |
| 4125 | 402 # define L1_INDEX(p) HASH ((EMACS_UINT) p >> (LOG_LEVEL2_SIZE + LOG_PAGE_SIZE)) |
| 2720 | 403 #else |
| 4125 | 404 # define L1_INDEX(p) ((EMACS_UINT) p >> (LOG_LEVEL2_SIZE + LOG_PAGE_SIZE)) |
| 2720 | 405 #endif |
| 4125 | 406 #define L2_INDEX(p) (((EMACS_UINT) p >> LOG_PAGE_SIZE) & (LEVEL2_SIZE - 1)) |
| 2720 | 407 |
| 408 | |
| 409 | |
| 410 | |
| 411 /*--- structs and typedefs ---------------------------------------------*/ | |
| 412 | |
| 3092 | 413 /* Links the free lists (mark_bit_free_list and cell free list). */ |
| 2720 | 414 typedef struct free_link |
| 415 { | |
| 416 struct lrecord_header lheader; | |
| 417 struct free_link *next_free; | |
| 418 } free_link; | |
| 419 | |
| 420 | |
| 3092 | 421 /* Header for pages. They are held in a doubly linked list. */ |
| 2720 | 422 typedef struct page_header |
| 423 { | |
| 424 struct page_header *next; /* next page_header */ | |
| 425 struct page_header *prev; /* previous page_header */ | |
| 426 /* Field plh holds pointer to the according header of the page list.*/ | |
| 427 struct page_list_header *plh; /* page list header */ | |
| 428 free_link *free_list; /* links free cells on page */ | |
| 429 EMACS_INT n_pages; /* number of pages */ | |
| 430 EMACS_INT cell_size; /* size of cells on page */ | |
| 431 EMACS_INT cells_on_page; /* total number of cells on page */ | |
| 432 EMACS_INT cells_used; /* number of used cells on page */ | |
| 433 /* If the number of objects on page is bigger than BITS_PER_EMACS_INT, | |
| 434 the mark bits are put in an extra memory area. Then the field | |
| 435 mark_bits holds the pointer to this area. Is the number of | |
| 436 objects smaller than BITS_PER_EMACS_INT, the mark bits are held in the | |
| 437 mark_bit EMACS_INT directly, without an additional indirection. */ | |
| 3092 | 438 unsigned int black_bit:1; /* objects on page are black */ |
| 439 unsigned int dirty_bit:1; /* page is dirty */ | |
| 440 unsigned int protection_bit:1; /* page is write protected */ | |
| 441 unsigned int array_bit:1; /* page holds arrays */ | |
| 442 Rawbyte *mark_bits; /* pointer to mark bits */ | |
| 2720 | 443 void *heap_space; /* pointer to heap, where objects |
| 444 are stored */ | |
| 445 } page_header; | |
| 446 | |
| 447 | |
| 448 /* Different list types. */ | |
| 449 enum list_type_enum { | |
| 450 USED_LIST, | |
| 451 FREE_LIST | |
| 452 }; | |
| 453 | |
| 454 | |
| 455 /* Header for page lists. Field list_type holds the type of the list. */ | |
| 456 typedef struct page_list_header | |
| 457 { | |
| 458 enum list_type_enum list_type; /* the type of the list */ | |
| 459 /* Size holds the size of one cell (in bytes) in a used heap list, or the | |
| 460 size of the heap sector (in number of pages). */ | |
| 461 size_t size; /* size of one cell / heap sector */ | |
| 462 page_header *first; /* first of page_header list */ | |
| 463 page_header *last; /* last of page_header list */ | |
| 464 /* If the number of objects on page is bigger than | |
| 465 BITS_PER_EMACS_INT, the mark bits are put in an extra memory | |
| 466 area, which is linked in this free list, if not used. Is the | |
| 467 number of objects smaller than BITS_PER_EMACS_INT, the mark bits | |
| 468 are hold in the mark bit EMACS_INT directly, without an | |
| 469 additional indirection. */ | |
| 470 free_link *mark_bit_free_list; | |
| 471 | |
| 472 #ifdef MEMORY_USAGE_STATS | |
| 473 EMACS_INT page_count; /* number if pages in list */ | |
| 474 EMACS_INT used_cells; /* number of objects in list */ | |
| 475 EMACS_INT used_space; /* used space */ | |
| 476 EMACS_INT total_cells; /* number of available cells */ | |
| 477 EMACS_INT total_space; /* available space */ | |
| 478 #endif | |
| 479 } page_list_header; | |
| 480 | |
| 481 | |
| 482 /* The heap sectors are stored with their real start pointer and their | |
| 483 real size. Not aligned to PAGE_SIZE. Needed for freeing heap sectors. */ | |
| 484 typedef struct heap_sect { | |
| 485 void *real_start; /* real start pointer (NOT aligned) */ | |
| 486 size_t real_size; /* NOT multiple of PAGE_SIZE */ | |
| 487 void *start; /* aligned start pointer */ | |
| 488 EMACS_INT n_pages; /* multiple of PAGE_SIZE */ | |
| 489 } heap_sect; | |
| 490 | |
| 491 | |
| 492 /* 2nd tree level for mapping of heap addresses to page headers. */ | |
| 493 typedef struct level_2_lookup_tree { | |
| 494 page_header *index[LEVEL2_SIZE]; /* link to page header */ | |
| 495 EMACS_INT key; /* high order address bits */ | |
| 496 #ifdef USE_HASH_TABLE | |
| 497 struct level_2_lookup_tree *hash_link; /* hash chain link */ | |
| 498 #endif | |
| 499 } level_2_lookup_tree; | |
| 500 | |
| 501 | |
| 502 | |
| 503 /*--- global variable definitions --------------------------------------*/ | |
| 504 | |
| 505 /* All global allocator variables are kept in this struct. */ | |
| 506 typedef struct mc_allocator_globals_type { | |
| 507 | |
| 508 /* heap size */ | |
| 509 EMACS_INT heap_size; | |
| 510 | |
| 511 /* list of all separatly allocated chunks of heap */ | |
| 512 heap_sect heap_sections[MAX_HEAP_SECTS]; | |
| 513 EMACS_INT n_heap_sections; | |
| 514 | |
| 515 /* Holds all allocated pages, each object size class in its separate list, | |
| 516 to guarantee fast allocation on partially filled pages. */ | |
| 3092 | 517 page_list_header *used_heap_pages; |
| 2720 | 518 |
|
5216
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
519 /* Holds all allocated pages that contain array elements. */ |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
520 page_list_header array_heap_pages; |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
521 |
| 2720 | 522 /* Holds all free pages in the heap. N multiples of PAGE_SIZE are |
| 523 kept on the Nth free list. Contiguos pages are coalesced. */ | |
| 524 page_list_header free_heap_pages[N_FREE_PAGE_LISTS]; | |
| 525 | |
| 526 /* ptr lookup table */ | |
| 3092 | 527 level_2_lookup_tree **ptr_lookup_table; |
| 2720 | 528 |
| 3092 | 529 #ifndef BLOCKTYPE_ALLOC_PAGE_HEADER |
| 2720 | 530 /* page header free list */ |
| 531 free_link *page_header_free_list; | |
| 3092 | 532 #endif /* not BLOCKTYPE_ALLOC_PAGE_HEADER */ |
| 2720 | 533 |
| 534 #ifdef MEMORY_USAGE_STATS | |
| 535 EMACS_INT malloced_bytes; | |
| 536 #endif | |
| 537 } mc_allocator_globals_type; | |
| 538 | |
| 539 mc_allocator_globals_type mc_allocator_globals; | |
| 540 | |
| 541 | |
| 542 | |
| 543 | |
| 544 /*--- macro accessors --------------------------------------------------*/ | |
| 545 | |
| 546 #define USED_HEAP_PAGES(i) \ | |
| 547 ((page_list_header*) &mc_allocator_globals.used_heap_pages[i]) | |
| 548 | |
|
5216
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
549 #define ARRAY_HEAP_PAGES \ |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
550 ((page_list_header*) &mc_allocator_globals.array_heap_pages) |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
551 |
| 2720 | 552 #define FREE_HEAP_PAGES(i) \ |
| 553 ((page_list_header*) &mc_allocator_globals.free_heap_pages[i]) | |
| 554 | |
| 555 #define PLH(plh) plh | |
| 556 # define PLH_LIST_TYPE(plh) PLH (plh)->list_type | |
| 557 # define PLH_SIZE(plh) PLH (plh)->size | |
| 558 # define PLH_FIRST(plh) PLH (plh)->first | |
| 559 # define PLH_LAST(plh) PLH (plh)->last | |
| 560 # define PLH_MARK_BIT_FREE_LIST(plh) PLH (plh)->mark_bit_free_list | |
| 561 #ifdef MEMORY_USAGE_STATS | |
| 562 # define PLH_PAGE_COUNT(plh) PLH (plh)->page_count | |
| 563 # define PLH_USED_CELLS(plh) PLH (plh)->used_cells | |
| 564 # define PLH_USED_SPACE(plh) PLH (plh)->used_space | |
| 565 # define PLH_TOTAL_CELLS(plh) PLH (plh)->total_cells | |
| 566 # define PLH_TOTAL_SPACE(plh) PLH (plh)->total_space | |
| 567 #endif | |
| 568 | |
| 569 #define PH(ph) ph | |
| 570 # define PH_NEXT(ph) PH (ph)->next | |
| 571 # define PH_PREV(ph) PH (ph)->prev | |
| 572 # define PH_PLH(ph) PH (ph)->plh | |
| 573 # define PH_FREE_LIST(ph) PH (ph)->free_list | |
| 574 # define PH_N_PAGES(ph) PH (ph)->n_pages | |
| 575 # define PH_CELL_SIZE(ph) PH (ph)->cell_size | |
| 576 # define PH_CELLS_ON_PAGE(ph) PH (ph)->cells_on_page | |
| 577 # define PH_CELLS_USED(ph) PH (ph)->cells_used | |
| 3092 | 578 # define PH_BLACK_BIT(ph) PH (ph)->black_bit |
| 579 # define PH_DIRTY_BIT(ph) PH (ph)->dirty_bit | |
| 580 # define PH_PROTECTION_BIT(ph) PH (ph)->protection_bit | |
| 581 # define PH_ARRAY_BIT(ph) PH (ph)->array_bit | |
| 2720 | 582 # define PH_MARK_BITS(ph) PH (ph)->mark_bits |
| 583 # define PH_HEAP_SPACE(ph) PH (ph)->heap_space | |
| 584 #define PH_LIST_TYPE(ph) PLH_LIST_TYPE (PH_PLH (ph)) | |
| 585 #define PH_MARK_BIT_FREE_LIST(ph) PLH_MARK_BIT_FREE_LIST (PH_PLH (ph)) | |
| 586 | |
| 587 #define HEAP_SIZE mc_allocator_globals.heap_size | |
| 588 | |
| 589 #ifdef MEMORY_USAGE_STATS | |
| 590 # define MC_MALLOCED_BYTES mc_allocator_globals.malloced_bytes | |
| 591 #endif | |
| 592 | |
| 593 #define HEAP_SECTION(index) mc_allocator_globals.heap_sections[index] | |
| 594 #define N_HEAP_SECTIONS mc_allocator_globals.n_heap_sections | |
| 595 | |
| 3092 | 596 #ifndef BLOCKTYPE_ALLOC_PAGE_HEADER |
| 2720 | 597 #define PAGE_HEADER_FREE_LIST mc_allocator_globals.page_header_free_list |
| 3092 | 598 #endif /* not BLOCKTYPE_ALLOC_PAGE_HEADER */ |
| 2720 | 599 |
| 600 #define NEXT_FREE(free_list) ((free_link*) free_list)->next_free | |
| 601 #define FREE_LIST(free_list) (free_link*) (free_list) | |
| 602 | |
| 603 #define PTR_LOOKUP_TABLE(i) mc_allocator_globals.ptr_lookup_table[i] | |
| 604 #define LEVEL2(l2, i) l2->index[i] | |
| 605 # define LEVEL2_KEY(l2) l2->key | |
| 606 #ifdef USE_HASH_TABLE | |
| 607 # define LEVEL2_HASH_LINK(l2) l2->hash_link | |
| 608 #endif | |
| 609 | |
| 610 #if ZERO_MEM | |
| 611 # define ZERO_HEAP_SPACE(ph) \ | |
| 612 memset (PH_HEAP_SPACE (ph), '\0', PH_N_PAGES (ph) * PAGE_SIZE) | |
| 613 # define ZERO_PAGE_HEADER(ph) memset (ph, '\0', sizeof (page_header)) | |
| 614 #endif | |
| 615 | |
| 616 #define div_PAGE_SIZE(x) (x >> LOG_PAGE_SIZE) | |
| 617 #define mult_PAGE_SIZE(x) (x << LOG_PAGE_SIZE) | |
| 618 | |
| 619 #define BYTES_TO_PAGES(bytes) (div_PAGE_SIZE ((bytes + (PAGE_SIZE - 1)))) | |
| 620 | |
| 621 #define PAGE_SIZE_ALIGNMENT(address) \ | |
| 4125 | 622 (void *) ((((EMACS_UINT) (address)) + PAGE_SIZE) & ~(PAGE_SIZE - 1)) |
| 2720 | 623 |
| 624 #define PH_ON_FREE_LIST_P(ph) \ | |
| 625 (ph && PH_PLH (ph) && (PLH_LIST_TYPE (PH_PLH (ph)) == FREE_LIST)) | |
| 626 | |
| 627 #define PH_ON_USED_LIST_P(ph) \ | |
| 628 (ph && PH_PLH (ph) && (PLH_LIST_TYPE (PH_PLH (ph)) == USED_LIST)) | |
| 629 | |
| 630 | |
| 3092 | 631 /* Number of mark bits: minimum 1, maximum 8. */ |
| 632 #define N_MARK_BITS 2 | |
| 2720 | 633 |
| 634 | |
| 635 | |
| 636 /************************************************************************/ | |
| 637 /* MC Allocator */ | |
| 638 /************************************************************************/ | |
| 639 | |
| 3305 | 640 /* Set to 1 if memory becomes short. */ |
| 641 EMACS_INT memory_shortage; | |
| 2720 | 642 |
| 643 /*--- misc functions ---------------------------------------------------*/ | |
| 644 | |
| 645 /* Visits all pages (page_headers) hooked into the used heap pages | |
| 646 list and executes f with the current page header as | |
| 3303 | 647 argument. Needed for sweep. Returns number of processed pages. */ |
| 648 static EMACS_INT | |
| 649 visit_all_used_page_headers (EMACS_INT (*f) (page_header *ph)) | |
| 2720 | 650 { |
| 3303 | 651 EMACS_INT number_of_pages_processed = 0; |
| 3092 | 652 EMACS_INT i; |
| 2720 | 653 for (i = 0; i < N_USED_PAGE_LISTS; i++) |
| 654 if (PLH_FIRST (USED_HEAP_PAGES (i))) | |
| 655 { | |
| 656 page_header *ph = PLH_FIRST (USED_HEAP_PAGES (i)); | |
| 657 while (PH_NEXT (ph)) | |
| 658 { | |
| 659 page_header *next = PH_NEXT (ph); /* in case f removes the page */ | |
| 3303 | 660 number_of_pages_processed += f (ph); |
| 2720 | 661 ph = next; |
| 662 } | |
| 3303 | 663 number_of_pages_processed += f (ph); |
| 2720 | 664 } |
|
5216
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
665 |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
666 if (PLH_FIRST (ARRAY_HEAP_PAGES)) |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
667 { |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
668 page_header *ph = PLH_FIRST (ARRAY_HEAP_PAGES); |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
669 while (PH_NEXT (ph)) |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
670 { |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
671 page_header *next = PH_NEXT (ph); /* in case f removes the page */ |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
672 number_of_pages_processed += f (ph); |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
673 ph = next; |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
674 } |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
675 number_of_pages_processed += f (ph); |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
676 } |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
677 |
| 3303 | 678 return number_of_pages_processed; |
| 2720 | 679 } |
| 680 | |
| 681 | |
| 682 | |
| 683 | |
| 684 /*--- mapping of heap addresses to page headers and mark bits ----------*/ | |
| 685 | |
| 686 /* Sets a heap pointer and page header pair into the lookup table. */ | |
| 687 static void | |
| 688 set_lookup_table (void *ptr, page_header *ph) | |
| 689 { | |
| 3092 | 690 EMACS_INT l1_index = L1_INDEX (ptr); |
| 2720 | 691 level_2_lookup_tree *l2 = PTR_LOOKUP_TABLE (l1_index); |
| 692 #ifdef USE_HASH_TABLE | |
| 693 while ((l2) && (LEVEL2_KEY (l2) != l1_index)) | |
| 694 l2 = LEVEL2_HASH_LINK (l2); | |
| 695 #endif | |
| 696 if (!l2) | |
| 697 { | |
| 698 l2 = (level_2_lookup_tree*) | |
| 699 xmalloc_and_zero (sizeof (level_2_lookup_tree)); | |
| 700 #ifdef MEMORY_USAGE_STATS | |
| 701 MC_MALLOCED_BYTES += | |
| 702 malloced_storage_size (0, sizeof (level_2_lookup_tree), 0); | |
| 703 #endif | |
| 2932 | 704 memset (l2, '\0', sizeof (level_2_lookup_tree)); |
| 2720 | 705 #ifdef USE_HASH_TABLE |
| 706 LEVEL2_HASH_LINK (l2) = PTR_LOOKUP_TABLE (l1_index); | |
| 707 #endif | |
| 708 PTR_LOOKUP_TABLE (l1_index) = l2; | |
| 709 LEVEL2_KEY (l2) = l1_index; | |
| 710 } | |
| 711 LEVEL2 (l2, L2_INDEX (ptr)) = ph; | |
| 712 } | |
| 713 | |
| 714 | |
| 715 #ifdef UNSET_LOOKUP_TABLE | |
| 716 /* Set the lookup table to 0 for given heap address. */ | |
| 717 static void | |
| 718 unset_lookup_table (void *ptr) | |
| 719 { | |
| 3092 | 720 EMACS_INT l1_index = L1_INDEX (ptr); |
| 2720 | 721 level_2_lookup_tree *l2 = PTR_LOOKUP_TABLE (l1_index); |
| 722 #ifdef USE_HASH_TABLE | |
| 723 while ((l2) && (LEVEL2_KEY (l2) != l1_index)) | |
| 724 l2 = LEVEL2_HASH_LINK (l2); | |
| 725 #endif | |
| 726 if (l2) { | |
| 727 LEVEL2 (l2, L2_INDEX (ptr)) = 0; | |
| 728 } | |
| 729 } | |
| 730 #endif | |
| 731 | |
| 732 /* Returns the page header of a given heap address, or 0 if not in table. | |
| 733 For internal use, no error checking. */ | |
| 734 static page_header * | |
| 735 get_page_header_internal (void *ptr) | |
| 736 { | |
| 3092 | 737 EMACS_INT l1_index = L1_INDEX (ptr); |
| 2720 | 738 level_2_lookup_tree *l2 = PTR_LOOKUP_TABLE (l1_index); |
| 739 #ifdef USE_HASH_TABLE | |
| 740 while ((l2) && (LEVEL2_KEY (l2) != l1_index)) | |
| 741 l2 = LEVEL2_HASH_LINK (l2); | |
| 742 #endif | |
| 743 if (!l2) | |
| 744 return 0; | |
| 745 return LEVEL2 (l2, L2_INDEX (ptr)); | |
| 746 } | |
| 747 | |
| 748 /* Returns the page header of a given heap address, or 0 if not in table. */ | |
| 749 static page_header * | |
| 750 get_page_header (void *ptr) | |
| 751 { | |
| 3092 | 752 EMACS_INT l1_index = L1_INDEX (ptr); |
| 2720 | 753 level_2_lookup_tree *l2 = PTR_LOOKUP_TABLE (l1_index); |
| 2723 | 754 assert (l2); |
| 2720 | 755 #ifdef USE_HASH_TABLE |
| 756 while ((l2) && (LEVEL2_KEY (l2) != l1_index)) | |
| 757 l2 = LEVEL2_HASH_LINK (l2); | |
| 758 #endif | |
| 2723 | 759 assert (LEVEL2 (l2, L2_INDEX (ptr))); |
| 2720 | 760 return LEVEL2 (l2, L2_INDEX (ptr)); |
| 761 } | |
| 762 | |
| 763 /* Returns the mark bit index of a given heap address. */ | |
| 764 static EMACS_INT | |
| 765 get_mark_bit_index (void *ptr, page_header *ph) | |
| 766 { | |
| 767 EMACS_INT cell_size = PH_CELL_SIZE (ph); | |
| 768 if (cell_size) | |
| 3092 | 769 return (((EMACS_INT) ptr - (EMACS_INT)(PH_HEAP_SPACE (ph))) / cell_size) |
| 770 * N_MARK_BITS; | |
| 2720 | 771 else /* only one object on page */ |
| 772 return 0; | |
| 773 } | |
| 774 | |
| 775 | |
| 776 /* Adds addresses of pages to lookup table. */ | |
| 777 static void | |
| 778 add_pages_to_lookup_table (page_header *ph, EMACS_INT n_pages) | |
| 779 { | |
| 3092 | 780 Rawbyte *p = (Rawbyte *) PH_HEAP_SPACE (ph); |
| 2720 | 781 EMACS_INT end_of_section = (EMACS_INT) p + (PAGE_SIZE * n_pages); |
| 3092 | 782 for (p = (Rawbyte *) PH_HEAP_SPACE (ph); |
| 2720 | 783 (EMACS_INT) p < end_of_section; p += PAGE_SIZE) |
| 784 set_lookup_table (p, ph); | |
| 785 } | |
| 786 | |
| 787 | |
| 788 /* Initializes lookup table. */ | |
| 789 static void | |
| 790 init_lookup_table (void) | |
| 791 { | |
| 3092 | 792 EMACS_INT i; |
| 2720 | 793 for (i = 0; i < LEVEL1_SIZE; i++) |
| 794 PTR_LOOKUP_TABLE (i) = 0; | |
| 795 } | |
| 796 | |
| 797 | |
| 798 | |
| 799 | |
| 800 /*--- mark bits --------------------------------------------------------*/ | |
| 801 | |
| 802 /*--- bit operations --- */ | |
| 803 | |
| 804 /* Allocates a bit array of length bits. */ | |
| 3092 | 805 static Rawbyte * |
| 2720 | 806 alloc_bit_array(size_t bits) |
| 807 { | |
| 3092 | 808 Rawbyte *bit_array; |
| 809 #ifdef USE_MARK_BITS_FREE_LIST | |
| 810 size_t size = ((bits + CHAR_BIT - 1) / CHAR_BIT) * sizeof (Rawbyte); | |
| 811 #else /* not USE_MARK_BITS_FREE_LIST */ | |
| 812 size_t size = | |
| 813 ALIGN_FOR_TYPE (((bits + CHAR_BIT - 1) / CHAR_BIT) * sizeof (Rawbyte), | |
| 814 Rawbyte *); | |
| 815 #endif /* not USE_MARK_BITS_FREE_LIST */ | |
| 2720 | 816 if (size < sizeof (free_link)) size = sizeof (free_link); |
| 817 #ifdef MEMORY_USAGE_STATS | |
| 818 MC_MALLOCED_BYTES += malloced_storage_size (0, size, 0); | |
| 819 #endif | |
| 3092 | 820 bit_array = (Rawbyte *) xmalloc_and_zero (size); |
| 2720 | 821 return bit_array; |
| 822 } | |
| 823 | |
| 824 | |
| 825 /* Returns the bit value at pos. */ | |
| 826 static EMACS_INT | |
| 3092 | 827 get_bit (Rawbyte *bit_array, EMACS_INT pos) |
| 2720 | 828 { |
| 829 #if N_MARK_BITS > 1 | |
| 830 EMACS_INT result = 0; | |
| 831 EMACS_INT i; | |
| 832 #endif | |
| 833 bit_array += pos / CHAR_BIT; | |
| 834 #if N_MARK_BITS > 1 | |
| 835 for (i = 0; i < N_MARK_BITS; i++) | |
| 3092 | 836 result |= ((*bit_array & (1 << ((pos + i) % CHAR_BIT))) != 0) << i; |
| 837 return result; | |
| 2720 | 838 #else |
| 839 return (*bit_array & (1 << (pos % CHAR_BIT))) != 0; | |
| 840 #endif | |
| 841 } | |
| 842 | |
| 843 | |
| 844 /* Bit_Arrays bit at pos to val. */ | |
| 845 static void | |
| 4125 | 846 set_bit (Rawbyte *bit_array, EMACS_INT pos, EMACS_UINT val) |
| 2720 | 847 { |
| 848 #if N_MARK_BITS > 1 | |
| 849 EMACS_INT i; | |
| 850 #endif | |
| 851 bit_array += pos / CHAR_BIT; | |
| 852 #if N_MARK_BITS > 1 | |
| 853 for (i = 0; i < N_MARK_BITS; i++) | |
| 854 if ((val >> i) & 1) | |
| 855 *bit_array |= 1 << ((pos + i) % CHAR_BIT); | |
| 856 else | |
| 857 *bit_array &= ~(1 << ((pos + i) % CHAR_BIT)); | |
| 858 #else | |
| 859 if (val) | |
| 860 *bit_array |= 1 << (pos % CHAR_BIT); | |
| 861 else | |
| 862 *bit_array &= ~(1 << (pos % CHAR_BIT)); | |
| 863 #endif | |
| 864 } | |
| 865 | |
| 866 | |
| 867 /*--- mark bit functions ---*/ | |
| 3092 | 868 #define USE_PNTR_MARK_BITS(ph) \ |
| 869 ((PH_CELLS_ON_PAGE (ph) * N_MARK_BITS) > BITS_PER_EMACS_INT) | |
| 870 #define USE_WORD_MARK_BITS(ph) \ | |
| 871 ((PH_CELLS_ON_PAGE (ph) * N_MARK_BITS) <= BITS_PER_EMACS_INT) | |
| 2720 | 872 |
| 3092 | 873 #define GET_BIT_WORD(b, p) get_bit ((Rawbyte *) &b, p) |
| 2720 | 874 #define GET_BIT_PNTR(b, p) get_bit (b, p) |
| 875 | |
| 3092 | 876 #define SET_BIT_WORD(b, p, v) set_bit ((Rawbyte *) &b, p, v) |
| 2720 | 877 #define SET_BIT_PNTR(b, p, v) set_bit (b, p, v) |
| 878 | |
| 879 #define ZERO_MARK_BITS_WORD(ph) PH_MARK_BITS (ph) = 0 | |
| 3092 | 880 #define ZERO_MARK_BITS_PNTR(ph) \ |
| 881 do { \ | |
| 882 memset (PH_MARK_BITS (ph), '\0', \ | |
| 883 ((PH_CELLS_ON_PAGE (ph) * N_MARK_BITS) \ | |
| 884 + CHAR_BIT - 1) / CHAR_BIT * sizeof (Rawbyte)); \ | |
| 2720 | 885 } while (0) |
| 886 | |
| 887 #define GET_BIT(bit, ph, p) \ | |
| 888 do { \ | |
| 889 if (USE_PNTR_MARK_BITS (ph)) \ | |
| 890 bit = GET_BIT_PNTR (PH_MARK_BITS (ph), p); \ | |
| 891 else \ | |
| 892 bit = GET_BIT_WORD (PH_MARK_BITS (ph), p); \ | |
| 893 } while (0) | |
| 894 | |
| 895 #define SET_BIT(ph, p, v) \ | |
| 896 do { \ | |
| 897 if (USE_PNTR_MARK_BITS (ph)) \ | |
| 898 SET_BIT_PNTR (PH_MARK_BITS (ph), p, v); \ | |
| 899 else \ | |
| 900 SET_BIT_WORD (PH_MARK_BITS (ph), p, v); \ | |
| 901 } while (0) | |
| 902 | |
| 903 #define ZERO_MARK_BITS(ph) \ | |
| 904 do { \ | |
| 905 if (USE_PNTR_MARK_BITS (ph)) \ | |
| 906 ZERO_MARK_BITS_PNTR (ph); \ | |
| 907 else \ | |
| 908 ZERO_MARK_BITS_WORD (ph); \ | |
| 909 } while (0) | |
| 910 | |
| 911 | |
| 912 /* Allocates mark-bit space either from a free list or from the OS | |
| 913 for the given page header. */ | |
| 3092 | 914 static Rawbyte * |
| 2720 | 915 alloc_mark_bits (page_header *ph) |
| 916 { | |
| 3092 | 917 Rawbyte *result; |
| 918 #ifdef USE_MARK_BITS_FREE_LIST | |
| 2720 | 919 if (PH_MARK_BIT_FREE_LIST (ph) == 0) |
| 3092 | 920 result = (Rawbyte *) alloc_bit_array (PH_CELLS_ON_PAGE (ph) * N_MARK_BITS); |
| 2720 | 921 else |
| 922 { | |
| 3092 | 923 result = (Rawbyte *) PH_MARK_BIT_FREE_LIST (ph); |
| 2720 | 924 PH_MARK_BIT_FREE_LIST (ph) = NEXT_FREE (result); |
| 925 } | |
| 3092 | 926 #else /* not USE_MARK_BITS_FREE_LIST */ |
| 927 result = (Rawbyte *) alloc_bit_array (PH_CELLS_ON_PAGE (ph) * N_MARK_BITS); | |
| 928 #endif /* not USE_MARK_BITS_FREE_LIST */ | |
| 2720 | 929 return result; |
| 930 } | |
| 931 | |
| 932 | |
| 933 /* Frees by maintaining a free list. */ | |
| 934 static void | |
| 935 free_mark_bits (page_header *ph) | |
| 936 { | |
| 3092 | 937 #ifdef USE_MARK_BITS_FREE_LIST |
| 938 NEXT_FREE (PH_MARK_BITS (ph)) = PH_MARK_BIT_FREE_LIST (ph); | |
| 939 PH_MARK_BIT_FREE_LIST (ph) = FREE_LIST (PH_MARK_BITS (ph)); | |
| 940 #else /* not USE_MARK_BITS_FREE_LIST */ | |
| 2720 | 941 if (PH_MARK_BITS (ph)) |
| 3092 | 942 free (PH_MARK_BITS (ph)); |
| 943 #endif /* not USE_MARK_BITS_FREE_LIST */ | |
| 2720 | 944 } |
| 945 | |
| 946 | |
| 947 /* Installs mark bits and zeros bits. */ | |
| 948 static void | |
| 949 install_mark_bits (page_header *ph) | |
| 950 { | |
| 951 if (USE_PNTR_MARK_BITS (ph)) | |
| 952 { | |
| 953 PH_MARK_BITS (ph) = alloc_mark_bits (ph); | |
| 954 ZERO_MARK_BITS_PNTR (ph); | |
| 955 } | |
| 956 else | |
| 957 ZERO_MARK_BITS_WORD (ph); | |
| 958 } | |
| 959 | |
| 960 | |
| 961 /* Cleans and frees the mark bits of the given page_header. */ | |
| 962 static void | |
| 963 remove_mark_bits (page_header *ph) | |
| 964 { | |
| 965 if (USE_PNTR_MARK_BITS (ph)) | |
| 966 free_mark_bits (ph); | |
| 967 } | |
| 968 | |
| 969 | |
| 970 /* Zeros all mark bits in given header. */ | |
| 971 static void | |
| 972 zero_mark_bits (page_header *ph) | |
| 973 { | |
| 974 ZERO_MARK_BITS (ph); | |
| 975 } | |
| 976 | |
| 977 | |
| 978 /* Returns mark bit for given heap pointer. */ | |
| 979 EMACS_INT | |
| 980 get_mark_bit (void *ptr) | |
| 981 { | |
| 982 EMACS_INT bit = 0; | |
| 983 page_header *ph = get_page_header (ptr); | |
| 984 gc_checking_assert (ph && PH_ON_USED_LIST_P (ph)); | |
| 985 if (ph) | |
| 986 { | |
| 987 GET_BIT (bit, ph, get_mark_bit_index (ptr, ph)); | |
| 988 } | |
| 989 return bit; | |
| 990 } | |
| 991 | |
| 992 | |
| 993 /* Sets mark bit for given heap pointer. */ | |
| 994 void | |
| 995 set_mark_bit (void *ptr, EMACS_INT value) | |
| 996 { | |
| 997 page_header *ph = get_page_header (ptr); | |
| 998 assert (ph && PH_ON_USED_LIST_P (ph)); | |
| 999 if (ph) | |
| 1000 { | |
| 3092 | 1001 if (value == BLACK) |
| 1002 if (!PH_BLACK_BIT (ph)) | |
| 1003 PH_BLACK_BIT (ph) = 1; | |
| 2720 | 1004 SET_BIT (ph, get_mark_bit_index (ptr, ph), value); |
| 1005 } | |
| 1006 } | |
| 1007 | |
| 1008 | |
| 1009 | |
| 1010 | |
| 1011 /*--- page header functions --------------------------------------------*/ | |
| 1012 | |
| 3092 | 1013 #ifdef BLOCKTYPE_ALLOC_PAGE_HEADER |
| 1014 #include "blocktype.h" | |
| 1015 | |
| 1016 struct page_header_blocktype | |
| 1017 { | |
| 1018 Blocktype_declare (page_header); | |
| 1019 } *the_page_header_blocktype; | |
| 1020 #endif /* BLOCKTYPE_ALLOC_PAGE_HEADER */ | |
| 1021 | |
| 2720 | 1022 /* Allocates a page header either from a free list or from the OS. */ |
| 1023 static page_header * | |
| 1024 alloc_page_header (void) | |
| 1025 { | |
| 3092 | 1026 #ifdef BLOCKTYPE_ALLOC_PAGE_HEADER |
| 1027 page_header *result; | |
| 1028 #ifdef MEMORY_USAGE_STATS | |
| 1029 MC_MALLOCED_BYTES += malloced_storage_size (0, sizeof (page_header), 0); | |
| 1030 #endif | |
| 1031 result = Blocktype_alloc (the_page_header_blocktype); | |
| 1032 ZERO_PAGE_HEADER (result); | |
| 1033 return result; | |
| 1034 #else /* not BLOCKTYPE_ALLOC_PAGE_HEADER */ | |
| 2720 | 1035 page_header *result; |
| 1036 if (PAGE_HEADER_FREE_LIST == 0) | |
| 1037 { | |
| 1038 result = | |
| 1039 (page_header *) xmalloc_and_zero ((EMACS_INT) (sizeof (page_header))); | |
| 1040 #ifdef MEMORY_USAGE_STATS | |
| 1041 MC_MALLOCED_BYTES += malloced_storage_size (0, sizeof (page_header), 0); | |
| 1042 #endif | |
| 1043 } | |
| 1044 else | |
| 1045 { | |
| 1046 result = (page_header*) PAGE_HEADER_FREE_LIST; | |
| 1047 PAGE_HEADER_FREE_LIST = NEXT_FREE (result); | |
| 1048 } | |
| 1049 return result; | |
| 3092 | 1050 #endif /* not BLOCKTYPE_ALLOC_PAGE_HEADER */ |
| 2720 | 1051 } |
| 1052 | |
| 1053 | |
| 1054 /* Frees given page header by maintaining a free list. */ | |
| 1055 static void | |
| 1056 free_page_header (page_header *ph) | |
| 1057 { | |
| 3092 | 1058 #ifdef BLOCKTYPE_ALLOC_PAGE_HEADER |
| 1059 Blocktype_free (the_page_header_blocktype, ph); | |
| 1060 #else /* not BLOCKTYPE_ALLOC_PAGE_HEADER */ | |
| 2720 | 1061 #if ZERO_MEM |
| 1062 ZERO_PAGE_HEADER (ph); | |
| 1063 #endif | |
| 1064 NEXT_FREE (ph) = PAGE_HEADER_FREE_LIST; | |
| 1065 PAGE_HEADER_FREE_LIST = FREE_LIST (ph); | |
| 3092 | 1066 #endif /* not BLOCKTYPE_ALLOC_PAGE_HEADER */ |
| 2720 | 1067 } |
| 1068 | |
| 1069 | |
| 1070 /* Adds given page header to given page list header's list. */ | |
| 1071 static void | |
| 1072 add_page_header_to_plh (page_header *ph, page_list_header *plh) | |
| 1073 { | |
| 1074 /* insert at the front of the list */ | |
| 1075 PH_PREV (ph) = 0; | |
| 1076 PH_NEXT (ph) = PLH_FIRST (plh); | |
| 1077 PH_PLH (ph) = plh; | |
| 1078 /* if list is not empty, set prev in the first element */ | |
| 1079 if (PLH_FIRST (plh)) | |
| 1080 PH_PREV (PLH_FIRST (plh)) = ph; | |
| 1081 /* one element in list is first and last at the same time */ | |
| 1082 PLH_FIRST (plh) = ph; | |
| 1083 if (!PLH_LAST (plh)) | |
| 1084 PLH_LAST (plh) = ph; | |
| 1085 | |
| 1086 #ifdef MEMORY_USAGE_STATS | |
| 1087 /* bump page count */ | |
| 1088 PLH_PAGE_COUNT (plh)++; | |
| 1089 #endif | |
| 1090 | |
| 1091 } | |
| 1092 | |
| 1093 | |
| 1094 /* Removes given page header from given page list header's list. */ | |
| 1095 static void | |
| 1096 remove_page_header_from_plh (page_header *ph, page_list_header *plh) | |
| 1097 { | |
| 1098 if (PLH_FIRST (plh) == ph) | |
| 1099 PLH_FIRST (plh) = PH_NEXT (ph); | |
| 1100 if (PLH_LAST (plh) == ph) | |
| 1101 PLH_LAST (plh) = PH_PREV (ph); | |
| 1102 if (PH_NEXT (ph)) | |
| 1103 PH_PREV (PH_NEXT (ph)) = PH_PREV (ph); | |
| 1104 if (PH_PREV (ph)) | |
| 1105 PH_NEXT (PH_PREV (ph)) = PH_NEXT (ph); | |
| 1106 | |
| 1107 #ifdef MEMORY_USAGE_STATS | |
| 1108 /* decrease page count */ | |
| 1109 PLH_PAGE_COUNT (plh)--; | |
| 1110 #endif | |
| 1111 } | |
| 1112 | |
| 1113 | |
| 1114 /* Moves a page header to the front of its the page header list. | |
| 1115 This is used during sweep: Pages with some alive objects are moved to | |
| 1116 the front. This makes allocation faster, all pages with free slots | |
| 1117 can be found at the front of the list. */ | |
| 1118 static void | |
| 1119 move_page_header_to_front (page_header *ph) | |
| 1120 { | |
| 1121 page_list_header *plh = PH_PLH (ph); | |
| 1122 /* is page already first? */ | |
| 1123 if (ph == PLH_FIRST (plh)) return; | |
| 1124 /* remove from list */ | |
| 1125 if (PLH_LAST (plh) == ph) | |
| 1126 PLH_LAST (plh) = PH_PREV (ph); | |
| 1127 if (PH_NEXT (ph)) | |
| 1128 PH_PREV (PH_NEXT (ph)) = PH_PREV (ph); | |
| 1129 if (PH_PREV (ph)) | |
| 1130 PH_NEXT (PH_PREV (ph)) = PH_NEXT (ph); | |
| 1131 /* insert at the front */ | |
| 1132 PH_NEXT (ph) = PLH_FIRST (plh); | |
| 1133 PH_PREV (ph) = 0; | |
| 1134 PH_PREV (PH_NEXT (ph)) = ph; | |
| 1135 PLH_FIRST (plh) = ph; | |
| 1136 } | |
| 1137 | |
| 1138 | |
| 1139 | |
| 1140 | |
| 1141 /*--- page list functions ----------------------------------------------*/ | |
| 1142 | |
| 1143 /* Returns the index of the used heap list according to given size. */ | |
| 1144 static int | |
| 1145 get_used_list_index (size_t size) | |
| 1146 { | |
| 1147 if (size <= USED_LIST_MIN_OBJECT_SIZE) | |
| 3092 | 1148 { |
|
5334
b249c479f9e1
Replace some C++ comments with C89-style /* */ comments, mc-alloc.c
Aidan Kehoe <kehoea@parhasard.net>
parents:
5238
diff
changeset
|
1149 /* printf ("size %d -> index %d\n", size, 0); */ |
| 3092 | 1150 return 0; |
| 1151 } | |
| 1152 if (size <= (size_t) USED_LIST_UPPER_THRESHOLD) | |
| 1153 { | |
|
5334
b249c479f9e1
Replace some C++ comments with C89-style /* */ comments, mc-alloc.c
Aidan Kehoe <kehoea@parhasard.net>
parents:
5238
diff
changeset
|
1154 /* printf ("size %d -> index %d\n", size, */ |
|
b249c479f9e1
Replace some C++ comments with C89-style /* */ comments, mc-alloc.c
Aidan Kehoe <kehoea@parhasard.net>
parents:
5238
diff
changeset
|
1155 /* ((size - USED_LIST_MIN_OBJECT_SIZE - 1) */ |
|
b249c479f9e1
Replace some C++ comments with C89-style /* */ comments, mc-alloc.c
Aidan Kehoe <kehoea@parhasard.net>
parents:
5238
diff
changeset
|
1156 /* / USED_LIST_LIN_STEP) + 1); */ |
| 3092 | 1157 return ((size - USED_LIST_MIN_OBJECT_SIZE - 1) |
| 1158 / USED_LIST_LIN_STEP) + 1; | |
| 1159 } | |
|
5334
b249c479f9e1
Replace some C++ comments with C89-style /* */ comments, mc-alloc.c
Aidan Kehoe <kehoea@parhasard.net>
parents:
5238
diff
changeset
|
1160 /* printf ("size %d -> index %d\n", size, N_USED_PAGE_LISTS - 1); */ |
| 2720 | 1161 return N_USED_PAGE_LISTS - 1; |
| 1162 } | |
| 1163 | |
| 1164 /* Returns the size of the used heap list according to given index. */ | |
| 1165 static size_t | |
| 1166 get_used_list_size_value (int used_index) | |
| 1167 { | |
| 1168 if (used_index < N_USED_PAGE_LISTS - 1) | |
| 1169 return (used_index * USED_LIST_LIN_STEP) + USED_LIST_MIN_OBJECT_SIZE; | |
| 1170 return 0; | |
| 1171 } | |
| 1172 | |
| 1173 | |
| 1174 /* Returns the index of the free heap list according to given size. */ | |
| 3092 | 1175 static EMACS_INT |
| 2720 | 1176 get_free_list_index (EMACS_INT n_pages) |
| 1177 { | |
| 1178 if (n_pages == 0) | |
| 1179 return 0; | |
| 1180 if (n_pages <= FREE_LIST_LOWER_THRESHOLD) | |
| 1181 return n_pages - 1; | |
| 1182 if (n_pages >= FREE_LIST_UPPER_THRESHOLD - 1) | |
| 1183 return N_FREE_PAGE_LISTS - 1; | |
| 1184 return ((n_pages - FREE_LIST_LOWER_THRESHOLD - 1) | |
| 1185 / FREE_LIST_LIN_STEP) + FREE_LIST_LOWER_THRESHOLD; | |
| 1186 | |
| 1187 } | |
| 1188 | |
| 1189 | |
| 1190 /* Returns the size in number of pages of the given free list at index. */ | |
| 1191 static size_t | |
| 3092 | 1192 get_free_list_size_value (EMACS_INT free_index) |
| 2720 | 1193 { |
| 1194 if (free_index < FREE_LIST_LOWER_THRESHOLD) | |
| 1195 return free_index + 1; | |
| 1196 if (free_index >= N_FREE_PAGE_LISTS) | |
| 1197 return FREE_LIST_UPPER_THRESHOLD; | |
| 1198 return ((free_index + 1 - FREE_LIST_LOWER_THRESHOLD) | |
| 1199 * FREE_LIST_LIN_STEP) + FREE_LIST_LOWER_THRESHOLD; | |
| 1200 } | |
| 1201 | |
| 1202 | |
| 1203 Bytecount | |
|
5157
1fae11d56ad2
redo memory-usage mechanism, add way of dynamically initializing Lisp objects
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1204 mc_alloced_storage_size (Bytecount claimed_size, struct usage_stats *stats) |
| 2720 | 1205 { |
| 1206 size_t used_size = | |
| 1207 get_used_list_size_value (get_used_list_index (claimed_size)); | |
| 1208 if (used_size == 0) | |
| 1209 used_size = mult_PAGE_SIZE (BYTES_TO_PAGES (claimed_size)); | |
| 1210 | |
| 1211 if (stats) | |
| 1212 { | |
| 1213 stats->was_requested += claimed_size; | |
| 1214 stats->malloc_overhead += used_size - claimed_size; | |
| 1215 } | |
| 1216 | |
| 1217 return used_size; | |
| 1218 } | |
| 1219 | |
| 1220 | |
| 1221 | |
| 1222 /*--- free heap functions ----------------------------------------------*/ | |
| 1223 | |
| 1224 /* Frees a heap section, if the heap_section is completly free */ | |
| 1225 static EMACS_INT | |
| 1226 free_heap_section (page_header *ph) | |
| 1227 { | |
| 3092 | 1228 EMACS_INT i; |
| 1229 EMACS_INT removed = 0; | |
| 2720 | 1230 for (i = 0; i < N_HEAP_SECTIONS; i++) |
| 1231 if (!removed) | |
| 1232 { | |
| 1233 if ((PH_HEAP_SPACE (ph) == HEAP_SECTION(i).start) | |
| 1234 && (PH_N_PAGES (ph) == HEAP_SECTION(i).n_pages)) | |
| 1235 { | |
| 1236 xfree_1 (HEAP_SECTION(i).real_start); | |
| 1237 #ifdef MEMORY_USAGE_STATS | |
| 1238 MC_MALLOCED_BYTES | |
| 1239 -= malloced_storage_size (0, HEAP_SECTION(i).real_size, 0); | |
| 1240 #endif | |
| 1241 | |
| 1242 HEAP_SIZE -= PH_N_PAGES (ph) * PAGE_SIZE; | |
| 1243 | |
| 1244 removed = 1; | |
| 1245 } | |
| 1246 } | |
| 1247 else | |
| 1248 { | |
| 1249 HEAP_SECTION(i-1).real_start = HEAP_SECTION(i).real_start; | |
| 1250 HEAP_SECTION(i-1).real_size = HEAP_SECTION(i).real_size; | |
| 1251 HEAP_SECTION(i-1).start = HEAP_SECTION(i).start; | |
| 1252 HEAP_SECTION(i-1).n_pages = HEAP_SECTION(i).n_pages; | |
| 1253 } | |
| 1254 | |
| 1255 N_HEAP_SECTIONS = N_HEAP_SECTIONS - removed; | |
| 1256 | |
| 1257 return removed; | |
| 1258 } | |
| 1259 | |
| 1260 /* Removes page from free list. */ | |
| 1261 static void | |
| 1262 remove_page_from_free_list (page_header *ph) | |
| 1263 { | |
| 1264 remove_page_header_from_plh (ph, PH_PLH (ph)); | |
| 1265 PH_PLH (ph) = 0; | |
| 1266 } | |
| 1267 | |
| 1268 | |
| 1269 /* Adds page to according free list. */ | |
| 1270 static void | |
| 1271 add_page_to_free_list (page_header *ph) | |
| 1272 { | |
| 1273 PH_PLH (ph) = FREE_HEAP_PAGES (get_free_list_index (PH_N_PAGES (ph))); | |
| 1274 add_page_header_to_plh (ph, PH_PLH (ph)); | |
| 1275 } | |
| 1276 | |
| 1277 | |
| 1278 /* Merges two adjacent pages. */ | |
| 1279 static page_header * | |
| 1280 merge_pages (page_header *first_ph, page_header *second_ph) | |
| 1281 { | |
| 1282 /* merge */ | |
| 1283 PH_N_PAGES (first_ph) += PH_N_PAGES (second_ph); | |
| 1284 /* clean up left over page header */ | |
| 1285 free_page_header (second_ph); | |
| 1286 /* update lookup table */ | |
| 1287 add_pages_to_lookup_table (first_ph, PH_N_PAGES (first_ph)); | |
| 1288 | |
| 1289 return first_ph; | |
| 1290 } | |
| 1291 | |
| 1292 | |
| 1293 /* Checks if pages are adjacent, merges them, and adds merged page to | |
| 1294 free list */ | |
| 1295 static void | |
| 1296 merge_into_free_list (page_header *ph) | |
| 1297 { | |
| 1298 /* check if you can coalesce adjacent pages */ | |
| 1299 page_header *prev_ph = | |
| 1300 get_page_header_internal ((void*) (((EMACS_INT) PH_HEAP_SPACE (ph)) | |
| 1301 - PAGE_SIZE)); | |
| 1302 page_header *succ_ph = | |
| 1303 get_page_header_internal ((void*) (((EMACS_INT) PH_HEAP_SPACE (ph)) | |
| 1304 + (PH_N_PAGES (ph) * PAGE_SIZE))); | |
| 1305 if (PH_ON_FREE_LIST_P (prev_ph)) | |
| 1306 { | |
| 1307 remove_page_from_free_list (prev_ph); | |
| 1308 ph = merge_pages (prev_ph, ph); | |
| 1309 } | |
| 1310 if (PH_ON_FREE_LIST_P (succ_ph)) | |
| 1311 { | |
| 1312 remove_page_from_free_list (succ_ph); | |
| 1313 ph = merge_pages (ph, succ_ph); | |
| 1314 } | |
| 1315 /* try to free heap_section, if the section is complete */ | |
| 1316 if (!free_heap_section (ph)) | |
| 1317 /* else add merged page to free list */ | |
| 1318 add_page_to_free_list (ph); | |
| 1319 } | |
| 1320 | |
| 1321 | |
| 1322 /* Cuts given page header after n_pages, returns the first (cut) part, and | |
| 1323 puts the rest on the free list. */ | |
| 1324 static page_header * | |
| 1325 split_page (page_header *ph, EMACS_INT n_pages) | |
| 1326 { | |
| 1327 page_header *new_ph; | |
| 1328 EMACS_INT rem_pages = PH_N_PAGES (ph) - n_pages; | |
| 1329 | |
| 1330 /* remove the page from the free list if already hooked in */ | |
| 1331 if (PH_PLH (ph)) | |
| 1332 remove_page_from_free_list (ph); | |
| 1333 /* set new number of pages */ | |
| 1334 PH_N_PAGES (ph) = n_pages; | |
| 1335 /* add new page to lookup table */ | |
| 1336 add_pages_to_lookup_table (ph, n_pages); | |
| 1337 | |
| 1338 if (rem_pages) | |
| 1339 { | |
| 1340 /* build new page with reminder */ | |
| 1341 new_ph = alloc_page_header (); | |
| 1342 PH_N_PAGES (new_ph) = rem_pages; | |
| 1343 PH_HEAP_SPACE (new_ph) = | |
| 1344 (void*) ((EMACS_INT) (PH_HEAP_SPACE (ph)) + (n_pages * PAGE_SIZE)); | |
| 1345 /* add new page to lookup table */ | |
| 1346 add_pages_to_lookup_table (new_ph, rem_pages); | |
| 1347 /* hook the rest into free list */ | |
| 1348 add_page_to_free_list (new_ph); | |
| 1349 } | |
| 1350 return ph; | |
| 1351 } | |
| 1352 | |
| 1353 | |
| 1354 /* Expands the heap by given number of pages. */ | |
| 1355 static page_header * | |
| 1356 expand_heap (EMACS_INT needed_pages) | |
| 1357 { | |
| 1358 page_header *ph; | |
| 1359 EMACS_INT n_pages; | |
| 1360 size_t real_size; | |
| 1361 void *real_start; | |
| 1362 | |
| 1363 /* determine number of pages the heap should grow */ | |
| 3305 | 1364 if (memory_shortage) |
| 1365 n_pages = needed_pages; | |
| 1366 else | |
| 1367 n_pages = max (MIN_HEAP_INCREASE, | |
| 1368 needed_pages | |
| 1369 + (HEAP_SIZE / (PAGE_SIZE * HEAP_GROWTH_DIVISOR))); | |
| 2720 | 1370 |
| 1371 /* get the real values */ | |
| 1372 real_size = (n_pages * PAGE_SIZE) + PAGE_SIZE; | |
| 1373 real_start = xmalloc_and_zero (real_size); | |
| 1374 #ifdef MEMORY_USAGE_STATS | |
| 1375 MC_MALLOCED_BYTES += malloced_storage_size (0, real_size, 0); | |
| 1376 #endif | |
| 1377 | |
| 1378 /* maintain heap section count */ | |
| 1379 if (N_HEAP_SECTIONS >= MAX_HEAP_SECTS) | |
| 1380 { | |
| 1381 stderr_out ("Increase number of MAX_HEAP_SECTS"); | |
| 1382 ABORT (); | |
| 1383 } | |
| 1384 HEAP_SECTION(N_HEAP_SECTIONS).real_start = real_start; | |
| 1385 HEAP_SECTION(N_HEAP_SECTIONS).real_size = real_size; | |
| 1386 HEAP_SECTION(N_HEAP_SECTIONS).start = PAGE_SIZE_ALIGNMENT (real_start); | |
| 1387 HEAP_SECTION(N_HEAP_SECTIONS).n_pages = n_pages; | |
| 1388 N_HEAP_SECTIONS ++; | |
| 1389 | |
| 1390 /* get page header */ | |
| 1391 ph = alloc_page_header (); | |
| 1392 | |
| 1393 /* setup page header */ | |
| 1394 PH_N_PAGES (ph) = n_pages; | |
| 1395 PH_HEAP_SPACE (ph) = PAGE_SIZE_ALIGNMENT (real_start); | |
| 1396 assert (((EMACS_INT) (PH_HEAP_SPACE (ph)) % PAGE_SIZE) == 0); | |
| 1397 HEAP_SIZE += n_pages * PAGE_SIZE; | |
| 1398 | |
| 1399 /* this was also done by allocate_lisp_storage */ | |
| 1400 if (need_to_check_c_alloca) | |
| 1401 xemacs_c_alloca (0); | |
| 1402 | |
| 1403 /* return needed size, put rest on free list */ | |
| 1404 return split_page (ph, needed_pages); | |
| 1405 } | |
| 1406 | |
| 1407 | |
| 1408 | |
| 1409 | |
| 1410 /*--- used heap functions ----------------------------------------------*/ | |
| 1411 /* Installs initial free list. */ | |
| 1412 static void | |
|
5216
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1413 install_cell_free_list (page_header *ph) |
| 2720 | 1414 { |
| 3092 | 1415 Rawbyte *p; |
| 1416 EMACS_INT i; | |
| 2720 | 1417 EMACS_INT cell_size = PH_CELL_SIZE (ph); |
| 1418 /* write initial free list if cell_size is < PAGE_SIZE */ | |
| 3092 | 1419 p = (Rawbyte *) PH_HEAP_SPACE (ph); |
| 2720 | 1420 for (i = 0; i < PH_CELLS_ON_PAGE (ph) - 1; i++) |
| 1421 { | |
| 1422 #ifdef ERROR_CHECK_GC | |
| 1423 assert (!LRECORD_FREE_P (p)); | |
| 1424 MARK_LRECORD_AS_FREE (p); | |
| 1425 #endif | |
|
5216
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1426 if (!PH_ARRAY_BIT (ph)) |
| 3092 | 1427 NEXT_FREE (p) = FREE_LIST (p + cell_size); |
| 2720 | 1428 set_lookup_table (p, ph); |
| 3092 | 1429 p += cell_size; |
| 2720 | 1430 } |
| 1431 #ifdef ERROR_CHECK_GC | |
| 1432 assert (!LRECORD_FREE_P (p)); | |
| 1433 MARK_LRECORD_AS_FREE (p); | |
| 1434 #endif | |
| 1435 NEXT_FREE (p) = 0; | |
| 1436 set_lookup_table (p, ph); | |
| 1437 | |
| 1438 /* hook free list into header */ | |
| 1439 PH_FREE_LIST (ph) = FREE_LIST (PH_HEAP_SPACE (ph)); | |
| 1440 } | |
| 1441 | |
| 1442 | |
| 1443 /* Cleans the object space of the given page_header. */ | |
| 1444 static void | |
| 1445 remove_cell_free_list (page_header *ph) | |
| 1446 { | |
| 1447 #if ZERO_MEM | |
| 1448 ZERO_HEAP_SPACE (ph); | |
| 1449 #endif | |
| 1450 PH_FREE_LIST (ph) = 0; | |
| 1451 } | |
| 1452 | |
| 1453 | |
| 1454 /* Installs a new page and hooks it into given page_list_header. */ | |
| 1455 static page_header * | |
| 1456 install_page_in_used_list (page_header *ph, page_list_header *plh, | |
| 3092 | 1457 size_t size, EMACS_INT elemcount) |
| 2720 | 1458 { |
| 1459 /* add to list */ | |
| 1460 add_page_header_to_plh (ph, plh); | |
| 1461 | |
| 1462 /* determine cell size */ | |
| 1463 if (PLH_SIZE (plh)) | |
| 1464 PH_CELL_SIZE (ph) = PLH_SIZE (plh); | |
| 1465 else | |
| 1466 PH_CELL_SIZE (ph) = size; | |
| 3092 | 1467 if (elemcount == 1) |
|
5216
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1468 { |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1469 PH_CELLS_ON_PAGE (ph) = (PAGE_SIZE * PH_N_PAGES (ph)) / PH_CELL_SIZE (ph); |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1470 PH_ARRAY_BIT (ph) = 0; |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1471 } |
| 3092 | 1472 else |
| 1473 { | |
| 1474 PH_CELLS_ON_PAGE (ph) = elemcount; | |
| 1475 PH_ARRAY_BIT (ph) = 1; | |
| 1476 } | |
| 2720 | 1477 |
| 1478 /* init cell count */ | |
| 1479 PH_CELLS_USED (ph) = 0; | |
| 1480 | |
| 1481 /* install mark bits and initialize cell free list */ | |
| 3092 | 1482 install_mark_bits (ph); |
| 2720 | 1483 |
|
5216
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1484 install_cell_free_list (ph); |
| 2720 | 1485 |
| 1486 #ifdef MEMORY_USAGE_STATS | |
| 1487 PLH_TOTAL_CELLS (plh) += PH_CELLS_ON_PAGE (ph); | |
| 1488 PLH_TOTAL_SPACE (plh) += PAGE_SIZE * PH_N_PAGES (ph); | |
| 1489 #endif | |
| 1490 | |
| 1491 return ph; | |
| 1492 } | |
| 1493 | |
| 1494 | |
| 1495 /* Cleans and frees a page, identified by the given page_header. */ | |
| 1496 static void | |
| 1497 remove_page_from_used_list (page_header *ph) | |
| 1498 { | |
| 1499 page_list_header *plh = PH_PLH (ph); | |
| 1500 | |
|
5050
6f2158fa75ed
Fix quick-build, use asserts() in place of ABORT()
Ben Wing <ben@xemacs.org>
parents:
4125
diff
changeset
|
1501 assert (!(gc_in_progress && PH_PROTECTION_BIT (ph))); |
| 3092 | 1502 /* cleanup: remove memory protection, zero page_header bits. */ |
| 1503 | |
| 2720 | 1504 #ifdef MEMORY_USAGE_STATS |
| 1505 PLH_TOTAL_CELLS (plh) -= PH_CELLS_ON_PAGE (ph); | |
| 1506 PLH_TOTAL_SPACE (plh) -= PAGE_SIZE * PH_N_PAGES (ph); | |
| 1507 #endif | |
| 1508 | |
| 1509 /* clean up mark bits and cell free list */ | |
| 1510 remove_cell_free_list (ph); | |
| 1511 if (PH_ON_USED_LIST_P (ph)) | |
| 1512 remove_mark_bits (ph); | |
| 1513 | |
| 1514 /* clean up page header */ | |
| 1515 PH_CELL_SIZE (ph) = 0; | |
| 1516 PH_CELLS_ON_PAGE (ph) = 0; | |
| 1517 PH_CELLS_USED (ph) = 0; | |
| 1518 | |
| 1519 /* remove from used list */ | |
| 1520 remove_page_header_from_plh (ph, plh); | |
| 1521 | |
| 1522 /* move to free list */ | |
| 1523 merge_into_free_list (ph); | |
| 1524 } | |
| 1525 | |
| 1526 | |
| 1527 | |
| 1528 | |
| 1529 /*--- allocation -------------------------------------------------------*/ | |
| 1530 | |
| 1531 /* Allocates from cell free list on already allocated pages. */ | |
| 1532 static page_header * | |
| 1533 allocate_cell (page_list_header *plh) | |
| 1534 { | |
| 1535 page_header *ph = PLH_FIRST (plh); | |
| 1536 if (ph) | |
| 1537 { | |
| 1538 if (PH_FREE_LIST (ph)) | |
| 1539 /* elements free on first page */ | |
| 1540 return ph; | |
| 1541 else if ((PH_NEXT (ph)) | |
| 1542 && (PH_FREE_LIST (PH_NEXT (ph)))) | |
| 1543 /* elements free on second page */ | |
| 1544 { | |
| 1545 page_header *temp = PH_NEXT (ph); | |
| 1546 /* move full page (first page) to end of list */ | |
| 1547 PH_NEXT (PLH_LAST (plh)) = ph; | |
| 1548 PH_PREV (ph) = PLH_LAST (plh); | |
| 1549 PLH_LAST (plh) = ph; | |
| 1550 PH_NEXT (ph) = 0; | |
| 1551 /* install second page as first page */ | |
| 1552 ph = temp; | |
| 1553 PH_PREV (ph) = 0; | |
| 1554 PLH_FIRST (plh) = ph; | |
| 1555 return ph; | |
| 1556 } | |
| 1557 } | |
| 1558 return 0; | |
| 1559 } | |
| 1560 | |
| 1561 | |
| 1562 /* Finds a page which has at least the needed number of pages. | |
| 1563 Algorithm: FIRST FIT. */ | |
| 1564 static page_header * | |
| 1565 find_free_page_first_fit (EMACS_INT needed_pages, page_header *ph) | |
| 1566 { | |
| 1567 while (ph) | |
| 1568 { | |
| 1569 if (PH_N_PAGES (ph) >= needed_pages) | |
| 1570 return ph; | |
| 1571 ph = PH_NEXT (ph); | |
| 1572 } | |
| 1573 return 0; | |
| 1574 } | |
| 1575 | |
| 1576 | |
| 1577 /* Allocates a page from the free list. */ | |
| 1578 static page_header * | |
| 1579 allocate_page_from_free_list (EMACS_INT needed_pages) | |
| 1580 { | |
| 1581 page_header *ph = 0; | |
| 3092 | 1582 EMACS_INT i; |
| 2720 | 1583 for (i = get_free_list_index (needed_pages); i < N_FREE_PAGE_LISTS; i++) |
| 1584 if ((ph = find_free_page_first_fit (needed_pages, | |
| 1585 PLH_FIRST (FREE_HEAP_PAGES (i)))) != 0) | |
| 1586 { | |
| 1587 if (PH_N_PAGES (ph) > needed_pages) | |
| 1588 return split_page (ph, needed_pages); | |
| 1589 else | |
| 1590 { | |
| 1591 remove_page_from_free_list (ph); | |
| 1592 return ph; | |
| 1593 } | |
| 1594 } | |
| 1595 return 0; | |
| 1596 } | |
| 1597 | |
| 1598 | |
| 1599 /* Allocates a new page, either from free list or by expanding the heap. */ | |
| 1600 static page_header * | |
| 3092 | 1601 allocate_new_page (page_list_header *plh, size_t size, EMACS_INT elemcount) |
| 2720 | 1602 { |
| 3092 | 1603 EMACS_INT needed_pages = BYTES_TO_PAGES (size * elemcount); |
| 2720 | 1604 /* first check free list */ |
| 1605 page_header *result = allocate_page_from_free_list (needed_pages); | |
| 1606 if (!result) | |
| 1607 /* expand heap */ | |
| 1608 result = expand_heap (needed_pages); | |
| 3092 | 1609 install_page_in_used_list (result, plh, size, elemcount); |
| 2720 | 1610 return result; |
| 1611 } | |
| 1612 | |
| 1613 | |
| 1614 /* Selects the correct size class, tries to allocate a cell of this size | |
| 1615 from the free list, if this fails, a new page is allocated. */ | |
| 1616 static void * | |
| 3092 | 1617 mc_alloc_1 (size_t size, EMACS_INT elemcount) |
| 2720 | 1618 { |
| 1619 page_list_header *plh = 0; | |
| 2723 | 1620 page_header *ph = 0; |
| 1621 void *result = 0; | |
| 1622 | |
| 2720 | 1623 if (size == 0) |
| 1624 return 0; | |
|
5216
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1625 |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1626 if (elemcount == 1) |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1627 { |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1628 plh = USED_HEAP_PAGES (get_used_list_index (size)); |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1629 if (size < (size_t) USED_LIST_UPPER_THRESHOLD) |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1630 /* first check any free cells */ |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1631 ph = allocate_cell (plh); |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1632 } |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1633 else |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1634 { |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1635 plh = ARRAY_HEAP_PAGES; |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1636 } |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1637 |
| 2720 | 1638 if (!ph) |
| 1639 /* allocate a new page */ | |
| 3092 | 1640 ph = allocate_new_page (plh, size, elemcount); |
| 2720 | 1641 |
| 1642 /* return first element of free list and remove it from the list */ | |
| 1643 result = (void*) PH_FREE_LIST (ph); | |
| 1644 PH_FREE_LIST (ph) = | |
| 1645 NEXT_FREE (PH_FREE_LIST (ph)); | |
| 1646 | |
| 3092 | 1647 memset (result, '\0', (size * elemcount)); |
| 1648 MARK_LRECORD_AS_FREE (result); | |
| 2720 | 1649 |
| 1650 /* bump used cells counter */ | |
| 3092 | 1651 PH_CELLS_USED (ph) += elemcount; |
| 2720 | 1652 |
| 1653 #ifdef MEMORY_USAGE_STATS | |
| 3092 | 1654 PLH_USED_CELLS (plh) += elemcount; |
| 1655 PLH_USED_SPACE (plh) += size * elemcount; | |
| 2720 | 1656 #endif |
| 1657 | |
| 1658 return result; | |
| 1659 } | |
| 1660 | |
| 3092 | 1661 /* Array allocation. */ |
| 1662 void * | |
| 1663 mc_alloc_array (size_t size, EMACS_INT elemcount) | |
| 1664 { | |
| 1665 return mc_alloc_1 (size, elemcount); | |
| 1666 } | |
| 1667 | |
| 2720 | 1668 void * |
| 1669 mc_alloc (size_t size) | |
| 1670 { | |
| 1671 return mc_alloc_1 (size, 1); | |
| 1672 } | |
| 1673 | |
| 1674 | |
| 1675 | |
| 1676 /*--- sweep & free & finalize-------------------------------------------*/ | |
| 1677 | |
| 1678 /* Frees a heap pointer. */ | |
| 1679 static void | |
| 1680 remove_cell (void *ptr, page_header *ph) | |
| 1681 { | |
| 1682 #ifdef MEMORY_USAGE_STATS | |
| 1683 PLH_USED_CELLS (PH_PLH (ph))--; | |
| 1684 if (PH_ON_USED_LIST_P (ph)) | |
| 1685 PLH_USED_SPACE (PH_PLH (ph)) -= | |
| 1686 detagged_lisp_object_size ((const struct lrecord_header *) ptr); | |
| 1687 else | |
| 1688 PLH_USED_SPACE (PH_PLH (ph)) -= PH_CELL_SIZE (ph); | |
| 1689 #endif | |
| 2775 | 1690 if (PH_ON_USED_LIST_P (ph)) |
| 1691 { | |
| 2994 | 1692 #ifdef ALLOC_TYPE_STATS |
| 2775 | 1693 dec_lrecord_stats (PH_CELL_SIZE (ph), |
| 1694 (const struct lrecord_header *) ptr); | |
| 2994 | 1695 #endif /* ALLOC_TYPE_STATS */ |
| 2775 | 1696 #ifdef ERROR_CHECK_GC |
| 1697 assert (!LRECORD_FREE_P (ptr)); | |
| 1698 deadbeef_memory (ptr, PH_CELL_SIZE (ph)); | |
| 1699 MARK_LRECORD_AS_FREE (ptr); | |
| 2720 | 1700 #endif |
| 2775 | 1701 } |
| 2720 | 1702 |
| 1703 /* hooks cell into free list */ | |
| 1704 NEXT_FREE (ptr) = PH_FREE_LIST (ph); | |
| 1705 PH_FREE_LIST (ph) = FREE_LIST (ptr); | |
| 1706 /* decrease cells used */ | |
| 1707 PH_CELLS_USED (ph)--; | |
| 1708 } | |
| 1709 | |
| 1710 | |
| 1711 /* Mark free list marks all free list entries. */ | |
| 1712 static void | |
| 1713 mark_free_list (page_header *ph) | |
| 1714 { | |
| 1715 free_link *fl = PH_FREE_LIST (ph); | |
| 1716 while (fl) | |
| 1717 { | |
| 3092 | 1718 SET_BIT (ph, get_mark_bit_index (fl, ph), BLACK); |
| 2720 | 1719 fl = NEXT_FREE (fl); |
| 1720 } | |
| 1721 } | |
| 1722 | |
| 1723 | |
| 1724 /* Finalize a page for disksave. XEmacs calls this routine before it | |
| 1725 dumps the heap image. You have to tell mc-alloc how to call your | |
| 1726 object's finalizer for disksave. Therefore, you have to define the | |
| 1727 macro MC_ALLOC_CALL_FINALIZER_FOR_DISKSAVE(ptr). This macro should | |
| 1728 do nothing else then test if there is a finalizer and call it on | |
| 3303 | 1729 the given argument, which is the heap address of the object. |
| 1730 Returns number of processed pages. */ | |
| 1731 static EMACS_INT | |
| 2720 | 1732 finalize_page_for_disksave (page_header *ph) |
| 1733 { | |
| 1734 EMACS_INT heap_space = (EMACS_INT) PH_HEAP_SPACE (ph); | |
| 1735 EMACS_INT heap_space_step = PH_CELL_SIZE (ph); | |
| 1736 EMACS_INT mark_bit = 0; | |
| 1737 EMACS_INT mark_bit_max_index = PH_CELLS_ON_PAGE (ph); | |
| 1738 | |
| 1739 for (mark_bit = 0; mark_bit < mark_bit_max_index; mark_bit++) | |
| 1740 { | |
| 1741 EMACS_INT ptr = (heap_space + (heap_space_step * mark_bit)); | |
| 1742 MC_ALLOC_CALL_FINALIZER_FOR_DISKSAVE ((void *) ptr); | |
| 1743 } | |
| 3303 | 1744 return 1; |
| 2720 | 1745 } |
| 1746 | |
| 1747 | |
| 3303 | 1748 /* Finalizes the heap for disksave. Returns number of processed |
| 1749 pages. */ | |
| 1750 EMACS_INT | |
| 2720 | 1751 mc_finalize_for_disksave (void) |
| 1752 { | |
| 3303 | 1753 return visit_all_used_page_headers (finalize_page_for_disksave); |
| 2720 | 1754 } |
| 1755 | |
| 1756 | |
| 3303 | 1757 /* Sweeps a page: all the non-marked cells are freed. If the page is |
| 1758 empty in the end, it is removed. If some cells are free, it is | |
| 1759 moved to the front of its page header list. Full pages stay where | |
| 1760 they are. Returns number of processed pages.*/ | |
| 1761 static EMACS_INT | |
| 2720 | 1762 sweep_page (page_header *ph) |
| 1763 { | |
| 3092 | 1764 Rawbyte *heap_space = (Rawbyte *) PH_HEAP_SPACE (ph); |
| 2720 | 1765 EMACS_INT heap_space_step = PH_CELL_SIZE (ph); |
| 1766 EMACS_INT mark_bit = 0; | |
| 1767 EMACS_INT mark_bit_max_index = PH_CELLS_ON_PAGE (ph); | |
| 3092 | 1768 unsigned int bit = 0; |
| 2720 | 1769 |
| 1770 mark_free_list (ph); | |
| 1771 | |
| 3092 | 1772 /* ARRAY_BIT_HACK */ |
| 1773 if (PH_ARRAY_BIT (ph)) | |
| 1774 for (mark_bit = 0; mark_bit < mark_bit_max_index; mark_bit++) | |
| 1775 { | |
| 1776 GET_BIT (bit, ph, mark_bit * N_MARK_BITS); | |
| 1777 if (bit) | |
| 1778 { | |
| 1779 zero_mark_bits (ph); | |
| 1780 PH_BLACK_BIT (ph) = 0; | |
| 3303 | 1781 return 1; |
| 3092 | 1782 } |
| 1783 } | |
| 1784 | |
| 2720 | 1785 for (mark_bit = 0; mark_bit < mark_bit_max_index; mark_bit++) |
| 1786 { | |
| 3092 | 1787 GET_BIT (bit, ph, mark_bit * N_MARK_BITS); |
| 1788 if (bit == WHITE) | |
| 2720 | 1789 { |
| 3092 | 1790 GC_STAT_FREED; |
| 2720 | 1791 remove_cell (heap_space + (heap_space_step * mark_bit), ph); |
| 1792 } | |
| 1793 } | |
| 1794 zero_mark_bits (ph); | |
| 3092 | 1795 PH_BLACK_BIT (ph) = 0; |
| 2720 | 1796 if (PH_CELLS_USED (ph) == 0) |
| 1797 remove_page_from_used_list (ph); | |
| 1798 else if (PH_CELLS_USED (ph) < PH_CELLS_ON_PAGE (ph)) | |
| 1799 move_page_header_to_front (ph); | |
| 3303 | 1800 |
| 1801 return 1; | |
| 2720 | 1802 } |
| 1803 | |
| 1804 | |
| 3303 | 1805 /* Sweeps the heap. Returns number of processed pages. */ |
| 1806 EMACS_INT | |
| 2720 | 1807 mc_sweep (void) |
| 1808 { | |
| 3303 | 1809 return visit_all_used_page_headers (sweep_page); |
| 2720 | 1810 } |
| 1811 | |
| 1812 | |
| 1813 /* Changes the size of the cell pointed to by ptr. | |
| 1814 Returns the new address of the new cell with new size. */ | |
|
5042
f395ee7ad844
Fix some compile warnings, make vdb test code conditional on DEBUG_XEMACS
Ben Wing <ben@xemacs.org>
parents:
4125
diff
changeset
|
1815 static void * |
| 3092 | 1816 mc_realloc_1 (void *ptr, size_t size, int elemcount) |
| 2720 | 1817 { |
| 1818 if (ptr) | |
| 1819 { | |
| 3092 | 1820 if (size * elemcount) |
| 2720 | 1821 { |
| 3092 | 1822 void *result = mc_alloc_1 (size, elemcount); |
| 2720 | 1823 size_t from_size = PH_CELL_SIZE (get_page_header (ptr)); |
| 3092 | 1824 size_t cpy_size = size * elemcount; |
| 1825 if (cpy_size > from_size) | |
| 2720 | 1826 cpy_size = from_size; |
| 1827 memcpy (result, ptr, cpy_size); | |
| 3092 | 1828 #ifdef ALLOC_TYPE_STATS |
| 1829 inc_lrecord_stats (size, (struct lrecord_header *) result); | |
| 1830 #endif /* not ALLOC_TYPE_STATS */ | |
| 2720 | 1831 return result; |
| 1832 } | |
| 1833 else | |
| 1834 { | |
| 1835 return 0; | |
| 1836 } | |
| 1837 } | |
| 1838 else | |
| 3092 | 1839 return mc_alloc_1 (size, elemcount); |
| 2720 | 1840 } |
| 1841 | |
| 1842 void * | |
| 1843 mc_realloc (void *ptr, size_t size) | |
| 1844 { | |
| 1845 return mc_realloc_1 (ptr, size, 1); | |
| 1846 } | |
| 1847 | |
| 1848 void * | |
| 3092 | 1849 mc_realloc_array (void *ptr, size_t size, EMACS_INT elemcount) |
| 2720 | 1850 { |
| 3092 | 1851 return mc_realloc_1 (ptr, size, elemcount); |
| 2720 | 1852 } |
| 1853 | |
| 1854 | |
| 1855 | |
| 1856 /*--- initialization ---------------------------------------------------*/ | |
| 1857 | |
| 1858 /* Call once at the very beginning. */ | |
| 1859 void | |
| 1860 init_mc_allocator (void) | |
| 1861 { | |
| 3092 | 1862 EMACS_INT i; |
| 1863 | |
| 1864 #ifdef MEMORY_USAGE_STATS | |
| 1865 MC_MALLOCED_BYTES = 0; | |
| 1866 #endif | |
| 2720 | 1867 |
| 3092 | 1868 /* init of pagesize dependent values */ |
| 1869 switch (SYS_PAGE_SIZE) | |
| 1870 { | |
| 1871 case 512: log_page_size = 9; break; | |
| 1872 case 1024: log_page_size = 10; break; | |
| 1873 case 2048: log_page_size = 11; break; | |
| 1874 case 4096: log_page_size = 12; break; | |
| 1875 case 8192: log_page_size = 13; break; | |
| 1876 case 16384: log_page_size = 14; break; | |
| 3212 | 1877 case 32768: log_page_size = 15; break; |
| 1878 case 65536: log_page_size = 16; break; | |
| 1879 default: | |
| 1880 fprintf(stderr, "##### SYS_PAGE_SIZE=%d not supported #####\n", | |
| 1881 SYS_PAGE_SIZE); | |
| 1882 ABORT (); | |
| 3092 | 1883 } |
| 1884 | |
| 4125 | 1885 page_size_div_2 = (EMACS_UINT) SYS_PAGE_SIZE >> 1; |
| 3092 | 1886 |
| 1887 mc_allocator_globals.used_heap_pages = | |
| 1888 (page_list_header *) xmalloc_and_zero ((N_USED_PAGE_LISTS + 1) | |
| 1889 * sizeof (page_list_header)); | |
| 1890 #ifdef MEMORY_USAGE_STATS | |
| 1891 MC_MALLOCED_BYTES += (N_USED_PAGE_LISTS + 1) * sizeof (page_list_header); | |
| 1892 #endif | |
| 1893 | |
| 1894 mc_allocator_globals.ptr_lookup_table = | |
| 1895 (level_2_lookup_tree **) | |
| 1896 xmalloc_and_zero ((LEVEL1_SIZE + 1) * sizeof (level_2_lookup_tree *)); | |
| 1897 #ifdef MEMORY_USAGE_STATS | |
| 1898 MC_MALLOCED_BYTES += (LEVEL1_SIZE + 1) * sizeof (level_2_lookup_tree *); | |
| 1899 #endif | |
| 1900 | |
| 1901 #ifdef BLOCKTYPE_ALLOC_PAGE_HEADER | |
| 1902 the_page_header_blocktype = Blocktype_new (struct page_header_blocktype); | |
| 1903 #endif /* BLOCKTYPE_ALLOC_PAGE_HEADER */ | |
| 2932 | 1904 |
| 2720 | 1905 for (i = 0; i < N_USED_PAGE_LISTS; i++) |
| 1906 { | |
| 1907 page_list_header *plh = USED_HEAP_PAGES (i); | |
| 1908 PLH_LIST_TYPE (plh) = USED_LIST; | |
| 1909 PLH_SIZE (plh) = get_used_list_size_value (i); | |
| 1910 PLH_FIRST (plh) = 0; | |
| 1911 PLH_LAST (plh) = 0; | |
| 1912 PLH_MARK_BIT_FREE_LIST (plh) = 0; | |
| 1913 #ifdef MEMORY_USAGE_STATS | |
| 1914 PLH_PAGE_COUNT (plh) = 0; | |
| 1915 PLH_USED_CELLS (plh) = 0; | |
| 1916 PLH_USED_SPACE (plh) = 0; | |
| 1917 PLH_TOTAL_CELLS (plh) = 0; | |
| 1918 PLH_TOTAL_SPACE (plh) = 0; | |
| 1919 #endif | |
| 1920 } | |
| 1921 | |
|
5216
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1922 { |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1923 page_list_header *plh = ARRAY_HEAP_PAGES; |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1924 PLH_LIST_TYPE (plh) = USED_LIST; |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1925 PLH_SIZE (plh) = 0; |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1926 PLH_FIRST (plh) = 0; |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1927 PLH_LAST (plh) = 0; |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1928 PLH_MARK_BIT_FREE_LIST (plh) = 0; |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1929 #ifdef MEMORY_USAGE_STATS |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1930 PLH_PAGE_COUNT (plh) = 0; |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1931 PLH_USED_CELLS (plh) = 0; |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1932 PLH_USED_SPACE (plh) = 0; |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1933 PLH_TOTAL_CELLS (plh) = 0; |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1934 PLH_TOTAL_SPACE (plh) = 0; |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1935 #endif |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1936 } |
|
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
1937 |
| 2720 | 1938 for (i = 0; i < N_FREE_PAGE_LISTS; i++) |
| 1939 { | |
| 1940 page_list_header *plh = FREE_HEAP_PAGES (i); | |
| 1941 PLH_LIST_TYPE (plh) = FREE_LIST; | |
| 1942 PLH_SIZE (plh) = get_free_list_size_value (i); | |
| 1943 PLH_FIRST (plh) = 0; | |
| 1944 PLH_LAST (plh) = 0; | |
| 1945 PLH_MARK_BIT_FREE_LIST (plh) = 0; | |
| 1946 #ifdef MEMORY_USAGE_STATS | |
| 1947 PLH_PAGE_COUNT (plh) = 0; | |
| 1948 PLH_USED_CELLS (plh) = 0; | |
| 1949 PLH_USED_SPACE (plh) = 0; | |
| 1950 PLH_TOTAL_CELLS (plh) = 0; | |
| 1951 PLH_TOTAL_SPACE (plh) = 0; | |
| 1952 #endif | |
| 1953 } | |
| 1954 | |
| 3092 | 1955 #ifndef BLOCKTYPE_ALLOC_PAGE_HEADER |
| 2720 | 1956 PAGE_HEADER_FREE_LIST = 0; |
| 3092 | 1957 #endif /* not BLOCKTYPE_ALLOC_PAGE_HEADER */ |
| 2720 | 1958 |
| 1959 #ifdef MEMORY_USAGE_STATS | |
| 3092 | 1960 MC_MALLOCED_BYTES += sizeof (mc_allocator_globals); |
| 2720 | 1961 #endif |
| 1962 | |
| 1963 init_lookup_table (); | |
| 1964 } | |
| 1965 | |
| 1966 | |
| 1967 | |
| 1968 | |
| 1969 /*--- lisp function for statistics -------------------------------------*/ | |
| 1970 | |
| 1971 #ifdef MEMORY_USAGE_STATS | |
| 1972 DEFUN ("mc-alloc-memory-usage", Fmc_alloc_memory_usage, 0, 0, 0, /* | |
| 1973 Returns stats about the mc-alloc memory usage. See diagnose.el. | |
| 1974 */ | |
| 1975 ()) | |
| 1976 { | |
| 1977 Lisp_Object free_plhs = Qnil; | |
| 1978 Lisp_Object used_plhs = Qnil; | |
| 1979 Lisp_Object heap_sects = Qnil; | |
| 3092 | 1980 EMACS_INT used_size = 0; |
| 1981 EMACS_INT real_size = 0; | |
| 2720 | 1982 |
| 3092 | 1983 EMACS_INT i; |
| 2720 | 1984 |
| 1985 for (i = 0; i < N_FREE_PAGE_LISTS; i++) | |
| 1986 if (PLH_PAGE_COUNT (FREE_HEAP_PAGES(i)) > 0) | |
| 1987 free_plhs = | |
|
5581
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
1988 Facons (make_fixnum (PLH_SIZE (FREE_HEAP_PAGES(i))), |
|
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
1989 list1 (make_fixnum (PLH_PAGE_COUNT (FREE_HEAP_PAGES(i)))), |
|
5354
22c4e67a2e69
Remove #'acons from cl.el, make the version in alloc.c visible to Lisp
Aidan Kehoe <kehoea@parhasard.net>
parents:
5334
diff
changeset
|
1990 free_plhs); |
| 2720 | 1991 |
| 1992 for (i = 0; i < N_USED_PAGE_LISTS; i++) | |
| 1993 if (PLH_PAGE_COUNT (USED_HEAP_PAGES(i)) > 0) | |
| 1994 used_plhs = | |
|
5581
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
1995 Facons (make_fixnum (PLH_SIZE (USED_HEAP_PAGES(i))), |
|
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
1996 list5 (make_fixnum (PLH_PAGE_COUNT (USED_HEAP_PAGES(i))), |
|
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
1997 make_fixnum (PLH_USED_CELLS (USED_HEAP_PAGES(i))), |
|
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
1998 make_fixnum (PLH_USED_SPACE (USED_HEAP_PAGES(i))), |
|
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
1999 make_fixnum (PLH_TOTAL_CELLS (USED_HEAP_PAGES(i))), |
|
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
2000 make_fixnum (PLH_TOTAL_SPACE (USED_HEAP_PAGES(i)))), |
|
5354
22c4e67a2e69
Remove #'acons from cl.el, make the version in alloc.c visible to Lisp
Aidan Kehoe <kehoea@parhasard.net>
parents:
5334
diff
changeset
|
2001 used_plhs); |
| 2720 | 2002 |
|
5216
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
2003 used_plhs = |
|
5581
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
2004 Facons (make_fixnum (0), |
|
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
2005 list5 (make_fixnum (PLH_PAGE_COUNT(ARRAY_HEAP_PAGES)), |
|
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
2006 make_fixnum (PLH_USED_CELLS (ARRAY_HEAP_PAGES)), |
|
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
2007 make_fixnum (PLH_USED_SPACE (ARRAY_HEAP_PAGES)), |
|
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
2008 make_fixnum (PLH_TOTAL_CELLS (ARRAY_HEAP_PAGES)), |
|
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
2009 make_fixnum (PLH_TOTAL_SPACE (ARRAY_HEAP_PAGES))), |
|
5354
22c4e67a2e69
Remove #'acons from cl.el, make the version in alloc.c visible to Lisp
Aidan Kehoe <kehoea@parhasard.net>
parents:
5334
diff
changeset
|
2010 used_plhs); |
|
5216
9b8c2168d231
Allocate lrecord arrays in own size class.
Marcus Crestani <crestani@informatik.uni-tuebingen.de>
parents:
5167
diff
changeset
|
2011 |
| 2720 | 2012 for (i = 0; i < N_HEAP_SECTIONS; i++) { |
| 2013 used_size += HEAP_SECTION(i).n_pages * PAGE_SIZE; | |
| 2014 real_size += | |
| 2015 malloced_storage_size (0, HEAP_SECTION(i).real_size, 0); | |
| 2016 } | |
| 2017 | |
| 2018 heap_sects = | |
|
5581
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
2019 list3 (make_fixnum (N_HEAP_SECTIONS), |
|
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
2020 make_fixnum (used_size), |
|
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
2021 make_fixnum (real_size)); |
| 2720 | 2022 |
|
5581
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
2023 return Fcons (make_fixnum (PAGE_SIZE), |
| 3092 | 2024 list5 (heap_sects, |
| 2720 | 2025 Fnreverse (used_plhs), |
| 2026 Fnreverse (free_plhs), | |
|
5581
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
2027 make_fixnum (sizeof (mc_allocator_globals)), |
|
56144c8593a8
Mechanically change INT to FIXNUM in our sources.
Aidan Kehoe <kehoea@parhasard.net>
parents:
5471
diff
changeset
|
2028 make_fixnum (MC_MALLOCED_BYTES))); |
| 2720 | 2029 } |
| 2030 #endif /* MEMORY_USAGE_STATS */ | |
| 2031 | |
| 2032 void | |
| 2033 syms_of_mc_alloc (void) | |
| 2034 { | |
| 2035 #ifdef MEMORY_USAGE_STATS | |
| 2036 DEFSUBR (Fmc_alloc_memory_usage); | |
| 2037 #endif /* MEMORY_USAGE_STATS */ | |
| 2038 } | |
| 3092 | 2039 |
| 2040 | |
| 2041 /*--- incremental garbage collector ----------------------------------*/ | |
| 2042 | |
| 5054 | 2043 #if 0 /* currently unused */ |
| 2044 | |
| 3092 | 2045 /* access dirty bit of page header */ |
|
5042
f395ee7ad844
Fix some compile warnings, make vdb test code conditional on DEBUG_XEMACS
Ben Wing <ben@xemacs.org>
parents:
4125
diff
changeset
|
2046 static void |
| 3092 | 2047 set_dirty_bit (page_header *ph, unsigned int value) |
| 2048 { | |
| 2049 PH_DIRTY_BIT (ph) = value; | |
| 2050 } | |
| 2051 | |
|
5042
f395ee7ad844
Fix some compile warnings, make vdb test code conditional on DEBUG_XEMACS
Ben Wing <ben@xemacs.org>
parents:
4125
diff
changeset
|
2052 static void |
| 3092 | 2053 set_dirty_bit_for_address (void *ptr, unsigned int value) |
| 2054 { | |
| 2055 set_dirty_bit (get_page_header (ptr), value); | |
| 2056 } | |
| 2057 | |
|
5042
f395ee7ad844
Fix some compile warnings, make vdb test code conditional on DEBUG_XEMACS
Ben Wing <ben@xemacs.org>
parents:
4125
diff
changeset
|
2058 static unsigned int |
| 3092 | 2059 get_dirty_bit (page_header *ph) |
| 2060 { | |
| 2061 return PH_DIRTY_BIT (ph); | |
| 2062 } | |
| 2063 | |
|
5042
f395ee7ad844
Fix some compile warnings, make vdb test code conditional on DEBUG_XEMACS
Ben Wing <ben@xemacs.org>
parents:
4125
diff
changeset
|
2064 static unsigned int |
| 3092 | 2065 get_dirty_bit_for_address (void *ptr) |
| 2066 { | |
| 2067 return get_dirty_bit (get_page_header (ptr)); | |
| 2068 } | |
| 2069 | |
| 2070 | |
| 2071 /* access protection bit of page header */ | |
|
5042
f395ee7ad844
Fix some compile warnings, make vdb test code conditional on DEBUG_XEMACS
Ben Wing <ben@xemacs.org>
parents:
4125
diff
changeset
|
2072 static void |
| 3092 | 2073 set_protection_bit (page_header *ph, unsigned int value) |
| 2074 { | |
| 2075 PH_PROTECTION_BIT (ph) = value; | |
| 2076 } | |
| 2077 | |
|
5042
f395ee7ad844
Fix some compile warnings, make vdb test code conditional on DEBUG_XEMACS
Ben Wing <ben@xemacs.org>
parents:
4125
diff
changeset
|
2078 static void |
| 3092 | 2079 set_protection_bit_for_address (void *ptr, unsigned int value) |
| 2080 { | |
| 2081 set_protection_bit (get_page_header (ptr), value); | |
| 2082 } | |
| 2083 | |
|
5042
f395ee7ad844
Fix some compile warnings, make vdb test code conditional on DEBUG_XEMACS
Ben Wing <ben@xemacs.org>
parents:
4125
diff
changeset
|
2084 static unsigned int |
| 3092 | 2085 get_protection_bit (page_header *ph) |
| 2086 { | |
| 2087 return PH_PROTECTION_BIT (ph); | |
| 2088 } | |
| 2089 | |
|
5042
f395ee7ad844
Fix some compile warnings, make vdb test code conditional on DEBUG_XEMACS
Ben Wing <ben@xemacs.org>
parents:
4125
diff
changeset
|
2090 static unsigned int |
| 3092 | 2091 get_protection_bit_for_address (void *ptr) |
| 2092 { | |
| 2093 return get_protection_bit (get_page_header (ptr)); | |
| 2094 } | |
| 2095 | |
| 2096 | |
| 2097 /* Returns the start of the page of the object pointed to by ptr. */ | |
|
5042
f395ee7ad844
Fix some compile warnings, make vdb test code conditional on DEBUG_XEMACS
Ben Wing <ben@xemacs.org>
parents:
4125
diff
changeset
|
2098 static void * |
| 3092 | 2099 get_page_start (void *ptr) |
| 2100 { | |
| 2101 return PH_HEAP_SPACE (get_page_header (ptr)); | |
| 2102 } | |
| 2103 | |
| 5054 | 2104 #endif /* 0 */ |
| 2105 | |
| 3092 | 2106 /* Make PAGE_SIZE globally available. */ |
| 2107 EMACS_INT | |
| 2108 mc_get_page_size () | |
| 2109 { | |
| 2110 return PAGE_SIZE; | |
| 2111 } | |
| 2112 | |
| 2113 /* Is the fault at ptr on a protected page? */ | |
| 2114 EMACS_INT | |
| 2115 fault_on_protected_page (void *ptr) | |
| 2116 { | |
| 2117 page_header *ph = get_page_header_internal (ptr); | |
| 2118 return (ph | |
| 2119 && PH_HEAP_SPACE (ph) | |
| 2120 && (PH_HEAP_SPACE (ph) <= ptr) | |
| 2121 && ((void *) ((EMACS_INT) PH_HEAP_SPACE (ph) | |
| 2122 + PH_N_PAGES (ph) * PAGE_SIZE) > ptr) | |
| 2123 && (PH_PROTECTION_BIT (ph) == 1)); | |
| 2124 } | |
| 2125 | |
| 2126 | |
| 2127 /* Protect the heap page of given page header ph if black objects are | |
| 3303 | 2128 on the page. Returns number of processed pages. */ |
| 2129 static EMACS_INT | |
| 3092 | 2130 protect_heap_page (page_header *ph) |
| 2131 { | |
| 2132 if (PH_BLACK_BIT (ph)) | |
| 2133 { | |
| 2134 void *heap_space = PH_HEAP_SPACE (ph); | |
| 2135 EMACS_INT heap_space_size = PH_N_PAGES (ph) * PAGE_SIZE; | |
| 2136 vdb_protect ((void *) heap_space, heap_space_size); | |
| 2137 PH_PROTECTION_BIT (ph) = 1; | |
| 3303 | 2138 return 1; |
| 3092 | 2139 } |
| 3303 | 2140 return 0; |
| 3092 | 2141 } |
| 2142 | |
| 3303 | 2143 /* Protect all heap pages with black objects. Returns number of |
| 2144 processed pages.*/ | |
| 2145 EMACS_INT | |
| 3092 | 2146 protect_heap_pages (void) |
| 2147 { | |
| 3303 | 2148 return visit_all_used_page_headers (protect_heap_page); |
| 3092 | 2149 } |
| 2150 | |
| 2151 | |
| 2152 /* Remove protection (if there) of heap page of given page header | |
| 3303 | 2153 ph. Returns number of processed pages. */ |
| 2154 static EMACS_INT | |
| 3092 | 2155 unprotect_heap_page (page_header *ph) |
| 2156 { | |
| 2157 if (PH_PROTECTION_BIT (ph)) | |
| 2158 { | |
| 2159 void *heap_space = PH_HEAP_SPACE (ph); | |
| 2160 EMACS_INT heap_space_size = PH_N_PAGES (ph) * PAGE_SIZE; | |
| 2161 vdb_unprotect (heap_space, heap_space_size); | |
| 2162 PH_PROTECTION_BIT (ph) = 0; | |
| 3303 | 2163 return 1; |
| 3092 | 2164 } |
| 3303 | 2165 return 0; |
| 3092 | 2166 } |
| 2167 | |
| 3303 | 2168 /* Remove protection for all heap pages which are protected. Returns |
| 2169 number of processed pages. */ | |
| 2170 EMACS_INT | |
| 3092 | 2171 unprotect_heap_pages (void) |
| 2172 { | |
| 3303 | 2173 return visit_all_used_page_headers (unprotect_heap_page); |
| 3092 | 2174 } |
| 2175 | |
| 2176 /* Remove protection and mark page dirty. */ | |
| 2177 void | |
| 2178 unprotect_page_and_mark_dirty (void *ptr) | |
| 2179 { | |
| 2180 page_header *ph = get_page_header (ptr); | |
| 2181 unprotect_heap_page (ph); | |
| 2182 PH_DIRTY_BIT (ph) = 1; | |
| 2183 } | |
| 2184 | |
| 2185 /* Repush all objects on dirty pages onto the mark stack. */ | |
| 2186 int | |
| 2187 repush_all_objects_on_page (void *ptr) | |
| 2188 { | |
| 2189 int repushed_objects = 0; | |
| 2190 page_header *ph = get_page_header (ptr); | |
| 2191 Rawbyte *heap_space = (Rawbyte *) PH_HEAP_SPACE (ph); | |
| 2192 EMACS_INT heap_space_step = PH_CELL_SIZE (ph); | |
| 2193 EMACS_INT mark_bit = 0; | |
| 2194 EMACS_INT mark_bit_max_index = PH_CELLS_ON_PAGE (ph); | |
| 2195 unsigned int bit = 0; | |
| 2196 for (mark_bit = 0; mark_bit < mark_bit_max_index; mark_bit++) | |
| 2197 { | |
| 2198 GET_BIT (bit, ph, mark_bit * N_MARK_BITS); | |
| 2199 if (bit == BLACK) | |
| 2200 { | |
| 2201 repushed_objects++; | |
| 2202 gc_write_barrier | |
| 2203 (wrap_pointer_1 ((heap_space + (heap_space_step * mark_bit)))); | |
| 2204 } | |
| 2205 } | |
| 2206 PH_BLACK_BIT (ph) = 0; | |
| 2207 PH_DIRTY_BIT (ph) = 0; | |
| 2208 return repushed_objects; | |
| 2209 } | |
| 2210 | |
| 2211 /* Mark black if object is currently grey. This first checks, if the | |
| 2212 object is really allocated on the mc-heap. If it is, it can be | |
| 2213 marked black; if it is not, it cannot be marked. */ | |
| 2214 EMACS_INT | |
| 2215 maybe_mark_black (void *ptr) | |
| 2216 { | |
| 2217 page_header *ph = get_page_header_internal (ptr); | |
| 2218 unsigned int bit = 0; | |
| 2219 | |
| 2220 if (ph && PH_PLH (ph) && PH_ON_USED_LIST_P (ph)) | |
| 2221 { | |
| 2222 GET_BIT (bit, ph, get_mark_bit_index (ptr, ph)); | |
| 2223 if (bit == GREY) | |
| 2224 { | |
| 2225 if (!PH_BLACK_BIT (ph)) | |
| 2226 PH_BLACK_BIT (ph) = 1; | |
| 2227 SET_BIT (ph, get_mark_bit_index (ptr, ph), BLACK); | |
| 2228 } | |
| 2229 return 1; | |
| 2230 } | |
| 2231 return 0; | |
| 2232 } | |
| 2233 | |
| 2234 /* Only for debugging --- not used anywhere in the sources. */ | |
| 2235 EMACS_INT | |
| 2236 object_on_heap_p (void *ptr) | |
| 2237 { | |
| 2238 page_header *ph = get_page_header_internal (ptr); | |
| 2239 return (ph && PH_ON_USED_LIST_P (ph)); | |
| 2240 } |