Rev 81 | Rev 83 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 81 | Rev 82 | ||
---|---|---|---|
1 | <?xml version="1.0" encoding="UTF-8"?> |
1 | <?xml version="1.0" encoding="UTF-8"?> |
2 | <chapter id="mm"> |
2 | <chapter id="mm"> |
3 | <?dbhtml filename="mm.html"?> |
3 | <?dbhtml filename="mm.html"?> |
4 | 4 | ||
5 | <title>Memory management</title> |
5 | <title>Memory management</title> |
6 | 6 | ||
7 | <para>In previous chapters, this book described the scheduling subsystem as |
7 | <para>In previous chapters, this book described the scheduling subsystem as |
8 | the creator of the impression that threads execute in parallel. The memory |
8 | the creator of the impression that threads execute in parallel. The memory |
9 | management subsystem, on the other hand, creates the impression that there |
9 | management subsystem, on the other hand, creates the impression that there |
10 | is enough physical memory for the kernel and that userspace tasks have the |
10 | is enough physical memory for the kernel and that userspace tasks have the |
11 | entire address space only for themselves.</para> |
11 | entire address space only for themselves.</para> |
12 | 12 | ||
13 | <section> |
13 | <section> |
14 | <title>Physical memory management</title> |
14 | <title>Physical memory management</title> |
15 | 15 | ||
16 | <section id="zones_and_frames"> |
16 | <section id="zones_and_frames"> |
17 | <title>Zones and frames</title> |
17 | <title>Zones and frames</title> |
18 | 18 | ||
19 | <para>HelenOS represents continuous areas of physical memory in |
19 | <para>HelenOS represents continuous areas of physical memory in |
20 | structures called frame zones (abbreviated as zones). Each zone contains |
20 | structures called frame zones (abbreviated as zones). Each zone contains |
21 | information about the number of allocated and unallocated physical |
21 | information about the number of allocated and unallocated physical |
22 | memory frames as well as the physical base address of the zone and |
22 | memory frames as well as the physical base address of the zone and |
23 | number of frames contained in it. A zone also contains an array of frame |
23 | number of frames contained in it. A zone also contains an array of frame |
24 | structures describing each frame of the zone and, in the last, but not |
24 | structures describing each frame of the zone and, in the last, but not |
25 | the least important, front, each zone is equipped with a buddy system |
25 | the least important, front, each zone is equipped with a buddy system |
26 | that faciliates effective allocation of power-of-two sized block of |
26 | that faciliates effective allocation of power-of-two sized block of |
27 | frames.</para> |
27 | frames.</para> |
28 | 28 | ||
29 | <para>This organization of physical memory provides good preconditions |
29 | <para>This organization of physical memory provides good preconditions |
30 | for hot-plugging of more zones. There is also one currently unused zone |
30 | for hot-plugging of more zones. There is also one currently unused zone |
31 | attribute: <code>flags</code>. The attribute could be used to give a |
31 | attribute: <code>flags</code>. The attribute could be used to give a |
32 | special meaning to some zones in the future.</para> |
32 | special meaning to some zones in the future.</para> |
33 | 33 | ||
34 | <para>The zones are linked in a doubly-linked list. This might seem a |
34 | <para>The zones are linked in a doubly-linked list. This might seem a |
35 | bit ineffective because the zone list is walked everytime a frame is |
35 | bit ineffective because the zone list is walked everytime a frame is |
36 | allocated or deallocated. However, this does not represent a significant |
36 | allocated or deallocated. However, this does not represent a significant |
37 | performance problem as it is expected that the number of zones will be |
37 | performance problem as it is expected that the number of zones will be |
38 | rather low. Moreover, most architectures merge all zones into |
38 | rather low. Moreover, most architectures merge all zones into |
39 | one.</para> |
39 | one.</para> |
40 | 40 | ||
41 | <para>Every physical memory frame in a zone, is described by a structure |
41 | <para>Every physical memory frame in a zone, is described by a structure |
42 | that contains number of references and other data used by buddy |
42 | that contains number of references and other data used by buddy |
43 | system.</para> |
43 | system.</para> |
44 | </section> |
44 | </section> |
45 | 45 | ||
46 | <section id="frame_allocator"> |
46 | <section id="frame_allocator"> |
47 | <indexterm> |
47 | <indexterm> |
48 | <primary>frame allocator</primary> |
48 | <primary>frame allocator</primary> |
49 | </indexterm> |
49 | </indexterm> |
50 | 50 | ||
51 | <title>Frame allocator</title> |
51 | <title>Frame allocator</title> |
52 | 52 | ||
53 | <para>The frame allocator satisfies kernel requests to allocate |
53 | <para>The frame allocator satisfies kernel requests to allocate |
54 | power-of-two sized blocks of physical memory. Because of zonal |
54 | power-of-two sized blocks of physical memory. Because of zonal |
55 | organization of physical memory, the frame allocator is always working |
55 | organization of physical memory, the frame allocator is always working |
56 | within a context of a particular frame zone. In order to carry out the |
56 | within a context of a particular frame zone. In order to carry out the |
57 | allocation requests, the frame allocator is tightly integrated with the |
57 | allocation requests, the frame allocator is tightly integrated with the |
58 | buddy system belonging to the zone. The frame allocator is also |
58 | buddy system belonging to the zone. The frame allocator is also |
59 | responsible for updating information about the number of free and busy |
59 | responsible for updating information about the number of free and busy |
60 | frames in the zone. <figure> |
60 | frames in the zone. <figure> |
61 | <mediaobject id="frame_alloc"> |
61 | <mediaobject id="frame_alloc"> |
62 | <imageobject role="eps"> |
62 | <imageobject role="eps"> |
63 | <imagedata fileref="images.vector/frame_alloc.eps" format="EPS" /> |
63 | <imagedata fileref="images.vector/frame_alloc.eps" format="EPS" /> |
64 | </imageobject> |
64 | </imageobject> |
65 | 65 | ||
66 | <imageobject role="html"> |
66 | <imageobject role="html"> |
67 | <imagedata fileref="images/frame_alloc.png" format="PNG" /> |
67 | <imagedata fileref="images/frame_alloc.png" format="PNG" /> |
68 | </imageobject> |
68 | </imageobject> |
69 | 69 | ||
70 | <imageobject role="fop"> |
70 | <imageobject role="fop"> |
71 | <imagedata fileref="images.vector/frame_alloc.svg" format="SVG" /> |
71 | <imagedata fileref="images.vector/frame_alloc.svg" format="SVG" /> |
72 | </imageobject> |
72 | </imageobject> |
73 | </mediaobject> |
73 | </mediaobject> |
74 | 74 | ||
75 | <title>Frame allocator scheme.</title> |
75 | <title>Frame allocator scheme.</title> |
76 | </figure></para> |
76 | </figure></para> |
77 | 77 | ||
78 | <formalpara> |
78 | <formalpara> |
79 | <title>Allocation / deallocation</title> |
79 | <title>Allocation / deallocation</title> |
80 | 80 | ||
81 | <para>Upon allocation request via function <code>frame_alloc</code>, |
81 | <para>Upon allocation request via function <code>frame_alloc()</code>, |
82 | the frame allocator first tries to find a zone that can satisfy the |
82 | the frame allocator first tries to find a zone that can satisfy the |
83 | request (i.e. has the required amount of free frames). Once a suitable |
83 | request (i.e. has the required amount of free frames). Once a suitable |
84 | zone is found, the frame allocator uses the buddy allocator on the |
84 | zone is found, the frame allocator uses the buddy allocator on the |
85 | zone's buddy system to perform the allocation. During deallocation, |
85 | zone's buddy system to perform the allocation. During deallocation, |
86 | which is triggered by a call to <code>frame_free</code>, the frame |
86 | which is triggered by a call to <code>frame_free()</code>, the frame |
87 | allocator looks up the respective zone that contains the frame being |
87 | allocator looks up the respective zone that contains the frame being |
88 | deallocated. Afterwards, it calls the buddy allocator again, this time |
88 | deallocated. Afterwards, it calls the buddy allocator again, this time |
89 | to take care of deallocation within the zone's buddy system.</para> |
89 | to take care of deallocation within the zone's buddy system.</para> |
90 | </formalpara> |
90 | </formalpara> |
91 | </section> |
91 | </section> |
92 | 92 | ||
93 | <section id="buddy_allocator"> |
93 | <section id="buddy_allocator"> |
94 | <indexterm> |
94 | <indexterm> |
95 | <primary>buddy system</primary> |
95 | <primary>buddy system</primary> |
96 | </indexterm> |
96 | </indexterm> |
97 | 97 | ||
98 | <title>Buddy allocator</title> |
98 | <title>Buddy allocator</title> |
99 | 99 | ||
100 | <para>In the buddy system, the memory is broken down into power-of-two |
100 | <para>In the buddy system, the memory is broken down into power-of-two |
101 | sized naturally aligned blocks. These blocks are organized in an array |
101 | sized naturally aligned blocks. These blocks are organized in an array |
102 | of lists, in which the list with index <emphasis>i</emphasis> contains all unallocated blocks |
102 | of lists, in which the list with index <emphasis>i</emphasis> contains |
- | 103 | all unallocated blocks of size |
|
103 | of size <emphasis>2<superscript>i</superscript></emphasis>. The |
104 | <emphasis>2<superscript>i</superscript></emphasis>. The index |
104 | index <emphasis>i</emphasis> is called the order of block. Should there be two adjacent |
105 | <emphasis>i</emphasis> is called the order of block. Should there be two |
105 | equally sized blocks in the list <emphasis>i</emphasis> (i.e. buddies), the |
106 | adjacent equally sized blocks in the list <emphasis>i</emphasis> (i.e. |
106 | buddy allocator would coalesce them and put the resulting block in list |
107 | buddies), the buddy allocator would coalesce them and put the resulting |
107 | <emphasis>i + 1</emphasis>, provided that the resulting block would |
108 | block in list <emphasis>i + 1</emphasis>, provided that the resulting |
108 | be naturally aligned. Similarily, when the allocator is asked to |
109 | block would be naturally aligned. Similarily, when the allocator is |
109 | allocate a block of size |
110 | asked to allocate a block of size |
110 | <emphasis>2<superscript>i</superscript></emphasis>, it first tries |
111 | <emphasis>2<superscript>i</superscript></emphasis>, it first tries to |
111 | to satisfy the request from the list with index <emphasis>i</emphasis>. If the request cannot |
112 | satisfy the request from the list with index <emphasis>i</emphasis>. If |
112 | be satisfied (i.e. the list <emphasis>i</emphasis> is empty), the buddy allocator will try to |
113 | the request cannot be satisfied (i.e. the list <emphasis>i</emphasis> is |
- | 114 | empty), the buddy allocator will try to allocate and split a larger |
|
113 | allocate and split a larger block from the list with index <emphasis>i + 1</emphasis>. Both |
115 | block from the list with index <emphasis>i + 1</emphasis>. Both of these |
114 | of these algorithms are recursive. The recursion ends either when there |
116 | algorithms are recursive. The recursion ends either when there are no |
115 | are no blocks to coalesce in the former case or when there are no blocks |
117 | blocks to coalesce in the former case or when there are no blocks that |
116 | that can be split in the latter case.</para> |
118 | can be split in the latter case.</para> |
117 | 119 | ||
118 | <para>This approach greatly reduces external fragmentation of memory and |
120 | <para>This approach greatly reduces external fragmentation of memory and |
119 | helps in allocating bigger continuous blocks of memory aligned to their |
121 | helps in allocating bigger continuous blocks of memory aligned to their |
120 | size. On the other hand, the buddy allocator suffers increased internal |
122 | size. On the other hand, the buddy allocator suffers increased internal |
121 | fragmentation of memory and is not suitable for general kernel |
123 | fragmentation of memory and is not suitable for general kernel |
122 | allocations. This purpose is better addressed by the <link |
124 | allocations. This purpose is better addressed by the <link |
123 | linkend="slab">slab allocator</link>.<figure> |
125 | linkend="slab">slab allocator</link>.<figure> |
124 | <mediaobject id="buddy_alloc"> |
126 | <mediaobject id="buddy_alloc"> |
125 | <imageobject role="eps"> |
127 | <imageobject role="eps"> |
126 | <imagedata fileref="images.vector/buddy_alloc.eps" format="EPS" /> |
128 | <imagedata fileref="images.vector/buddy_alloc.eps" format="EPS" /> |
127 | </imageobject> |
129 | </imageobject> |
128 | 130 | ||
129 | <imageobject role="html"> |
131 | <imageobject role="html"> |
130 | <imagedata fileref="images/buddy_alloc.png" format="PNG" /> |
132 | <imagedata fileref="images/buddy_alloc.png" format="PNG" /> |
131 | </imageobject> |
133 | </imageobject> |
132 | 134 | ||
133 | <imageobject role="fop"> |
135 | <imageobject role="fop"> |
134 | <imagedata fileref="images.vector/buddy_alloc.svg" format="SVG" /> |
136 | <imagedata fileref="images.vector/buddy_alloc.svg" format="SVG" /> |
135 | </imageobject> |
137 | </imageobject> |
136 | </mediaobject> |
138 | </mediaobject> |
137 | 139 | ||
138 | <title>Buddy system scheme.</title> |
140 | <title>Buddy system scheme.</title> |
139 | </figure></para> |
141 | </figure></para> |
140 | 142 | ||
141 | <section> |
143 | <section> |
142 | <title>Implementation</title> |
144 | <title>Implementation</title> |
143 | 145 | ||
144 | <para>The buddy allocator is, in fact, an abstract framework wich can |
146 | <para>The buddy allocator is, in fact, an abstract framework wich can |
145 | be easily specialized to serve one particular task. It knows nothing |
147 | be easily specialized to serve one particular task. It knows nothing |
146 | about the nature of memory it helps to allocate. In order to beat the |
148 | about the nature of memory it helps to allocate. In order to beat the |
147 | lack of this knowledge, the buddy allocator exports an interface that |
149 | lack of this knowledge, the buddy allocator exports an interface that |
148 | each of its clients is required to implement. When supplied with an |
150 | each of its clients is required to implement. When supplied with an |
149 | implementation of this interface, the buddy allocator can use |
151 | implementation of this interface, the buddy allocator can use |
150 | specialized external functions to find a buddy for a block, split and |
152 | specialized external functions to find a buddy for a block, split and |
151 | coalesce blocks, manipulate block order and mark blocks busy or |
153 | coalesce blocks, manipulate block order and mark blocks busy or |
152 | available.</para> |
154 | available.</para> |
153 | 155 | ||
154 | <formalpara> |
156 | <formalpara> |
155 | <title>Data organization</title> |
157 | <title>Data organization</title> |
156 | 158 | ||
157 | <para>Each entity allocable by the buddy allocator is required to |
159 | <para>Each entity allocable by the buddy allocator is required to |
158 | contain space for storing block order number and a link variable |
160 | contain space for storing block order number and a link variable |
159 | used to interconnect blocks within the same order.</para> |
161 | used to interconnect blocks within the same order.</para> |
160 | 162 | ||
161 | <para>Whatever entities are allocated by the buddy allocator, the |
163 | <para>Whatever entities are allocated by the buddy allocator, the |
162 | first entity within a block is used to represent the entire block. |
164 | first entity within a block is used to represent the entire block. |
163 | The first entity keeps the order of the whole block. Other entities |
165 | The first entity keeps the order of the whole block. Other entities |
164 | within the block are assigned the magic value |
166 | within the block are assigned the magic value |
165 | <constant>BUDDY_INNER_BLOCK</constant>. This is especially important |
167 | <constant>BUDDY_INNER_BLOCK</constant>. This is especially important |
166 | for effective identification of buddies in a one-dimensional array |
168 | for effective identification of buddies in a one-dimensional array |
167 | because the entity that represents a potential buddy cannot be |
169 | because the entity that represents a potential buddy cannot be |
168 | associated with <constant>BUDDY_INNER_BLOCK</constant> (i.e. if it |
170 | associated with <constant>BUDDY_INNER_BLOCK</constant> (i.e. if it |
169 | is associated with <constant>BUDDY_INNER_BLOCK</constant> then it is |
171 | is associated with <constant>BUDDY_INNER_BLOCK</constant> then it is |
170 | not a buddy).</para> |
172 | not a buddy).</para> |
171 | </formalpara> |
173 | </formalpara> |
172 | </section> |
174 | </section> |
173 | </section> |
175 | </section> |
174 | 176 | ||
175 | <section id="slab"> |
177 | <section id="slab"> |
176 | <indexterm> |
178 | <indexterm> |
177 | <primary>slab allocator</primary> |
179 | <primary>slab allocator</primary> |
178 | </indexterm> |
180 | </indexterm> |
179 | 181 | ||
180 | <title>Slab allocator</title> |
182 | <title>Slab allocator</title> |
181 | 183 | ||
182 | <para>The majority of memory allocation requests in the kernel is for |
184 | <para>The majority of memory allocation requests in the kernel is for |
183 | small, frequently used data structures. The basic idea behind the slab |
185 | small, frequently used data structures. The basic idea behind the slab |
184 | allocator is that commonly used objects are preallocated in continuous |
186 | allocator is that commonly used objects are preallocated in continuous |
185 | areas of physical memory called slabs<footnote> |
187 | areas of physical memory called slabs<footnote> |
186 | <para>Slabs are in fact blocks of physical memory frames allocated |
188 | <para>Slabs are in fact blocks of physical memory frames allocated |
187 | from the frame allocator.</para> |
189 | from the frame allocator.</para> |
188 | </footnote>. Whenever an object is to be allocated, the slab allocator |
190 | </footnote>. Whenever an object is to be allocated, the slab allocator |
189 | returns the first available item from a suitable slab corresponding to |
191 | returns the first available item from a suitable slab corresponding to |
190 | the object type<footnote> |
192 | the object type<footnote> |
191 | <para>The mechanism is rather more complicated, see the next |
193 | <para>The mechanism is rather more complicated, see the next |
192 | paragraph.</para> |
194 | paragraph.</para> |
193 | </footnote>. Due to the fact that the sizes of the requested and |
195 | </footnote>. Due to the fact that the sizes of the requested and |
194 | allocated object match, the slab allocator significantly reduces |
196 | allocated object match, the slab allocator significantly reduces |
195 | internal fragmentation.</para> |
197 | internal fragmentation.</para> |
196 | 198 | ||
197 | <indexterm> |
199 | <indexterm> |
198 | <primary>slab allocator</primary> |
200 | <primary>slab allocator</primary> |
199 | 201 | ||
200 | <secondary>- slab cache</secondary> |
202 | <secondary>- slab cache</secondary> |
201 | </indexterm> |
203 | </indexterm> |
202 | 204 | ||
203 | <para>Slabs of one object type are organized in a structure called slab |
205 | <para>Slabs of one object type are organized in a structure called slab |
204 | cache. There are ususally more slabs in the slab cache, depending on |
206 | cache. There are ususally more slabs in the slab cache, depending on |
205 | previous allocations. If the the slab cache runs out of available slabs, |
207 | previous allocations. If the the slab cache runs out of available slabs, |
206 | new slabs are allocated. In order to exploit parallelism and to avoid |
208 | new slabs are allocated. In order to exploit parallelism and to avoid |
207 | locking of shared spinlocks, slab caches can have variants of |
209 | locking of shared spinlocks, slab caches can have variants of |
208 | processor-private slabs called magazines. On each processor, there is a |
210 | processor-private slabs called magazines. On each processor, there is a |
209 | two-magazine cache. Full magazines that are not part of any |
211 | two-magazine cache. Full magazines that are not part of any |
210 | per-processor magazine cache are stored in a global list of full |
212 | per-processor magazine cache are stored in a global list of full |
211 | magazines.</para> |
213 | magazines.</para> |
212 | 214 | ||
213 | <indexterm> |
215 | <indexterm> |
214 | <primary>slab allocator</primary> |
216 | <primary>slab allocator</primary> |
215 | 217 | ||
216 | <secondary>- magazine</secondary> |
218 | <secondary>- magazine</secondary> |
217 | </indexterm> |
219 | </indexterm> |
218 | 220 | ||
219 | <para>Each object begins its life in a slab. When it is allocated from |
221 | <para>Each object begins its life in a slab. When it is allocated from |
220 | there, the slab allocator calls a constructor that is registered in the |
222 | there, the slab allocator calls a constructor that is registered in the |
221 | respective slab cache. The constructor initializes and brings the object |
223 | respective slab cache. The constructor initializes and brings the object |
222 | into a known state. The object is then used by the user. When the user |
224 | into a known state. The object is then used by the user. When the user |
223 | later frees the object, the slab allocator puts it into a processor |
225 | later frees the object, the slab allocator puts it into a processor |
224 | private <indexterm> |
226 | private <indexterm> |
225 | <primary>slab allocator</primary> |
227 | <primary>slab allocator</primary> |
226 | 228 | ||
227 | <secondary>- magazine</secondary> |
229 | <secondary>- magazine</secondary> |
228 | </indexterm>magazine cache, from where it can be precedently allocated |
230 | </indexterm>magazine cache, from where it can be precedently allocated |
229 | again. Note that allocations satisfied from a magazine are already |
231 | again. Note that allocations satisfied from a magazine are already |
230 | initialized by the constructor. When both of the processor cached |
232 | initialized by the constructor. When both of the processor cached |
231 | magazines get full, the allocator will move one of the magazines to the |
233 | magazines get full, the allocator will move one of the magazines to the |
232 | list of full magazines. Similarily, when allocating from an empty |
234 | list of full magazines. Similarily, when allocating from an empty |
233 | processor magazine cache, the kernel will reload only one magazine from |
235 | processor magazine cache, the kernel will reload only one magazine from |
234 | the list of full magazines. In other words, the slab allocator tries to |
236 | the list of full magazines. In other words, the slab allocator tries to |
235 | keep the processor magazine cache only half-full in order to prevent |
237 | keep the processor magazine cache only half-full in order to prevent |
236 | thrashing when allocations and deallocations interleave on magazine |
238 | thrashing when allocations and deallocations interleave on magazine |
237 | boundaries. The advantage of this setup is that during most of the |
239 | boundaries. The advantage of this setup is that during most of the |
238 | allocations, no global spinlock needs to be held.</para> |
240 | allocations, no global spinlock needs to be held.</para> |
239 | 241 | ||
240 | <para>Should HelenOS run short of memory, it would start deallocating |
242 | <para>Should HelenOS run short of memory, it would start deallocating |
241 | objects from magazines, calling slab cache destructor on them and |
243 | objects from magazines, calling slab cache destructor on them and |
242 | putting them back into slabs. When a slab contanins no allocated object, |
244 | putting them back into slabs. When a slab contanins no allocated object, |
243 | it is immediately freed.</para> |
245 | it is immediately freed.</para> |
244 | 246 | ||
245 | <para> |
247 | <para> |
246 | <figure> |
248 | <figure> |
247 | <mediaobject id="slab_alloc"> |
249 | <mediaobject id="slab_alloc"> |
248 | <imageobject role="eps"> |
250 | <imageobject role="eps"> |
249 | <imagedata fileref="images.vector/slab_alloc.eps" format="EPS" /> |
251 | <imagedata fileref="images.vector/slab_alloc.eps" format="EPS" /> |
250 | </imageobject> |
252 | </imageobject> |
251 | 253 | ||
252 | <imageobject role="html"> |
254 | <imageobject role="html"> |
253 | <imagedata fileref="images/slab_alloc.png" format="PNG" /> |
255 | <imagedata fileref="images/slab_alloc.png" format="PNG" /> |
254 | </imageobject> |
256 | </imageobject> |
255 | 257 | ||
256 | <imageobject role="fop"> |
258 | <imageobject role="fop"> |
257 | <imagedata fileref="images.vector/slab_alloc.svg" format="SVG" /> |
259 | <imagedata fileref="images.vector/slab_alloc.svg" format="SVG" /> |
258 | </imageobject> |
260 | </imageobject> |
259 | </mediaobject> |
261 | </mediaobject> |
260 | 262 | ||
261 | <title>Slab allocator scheme.</title> |
263 | <title>Slab allocator scheme.</title> |
262 | </figure> |
264 | </figure> |
263 | </para> |
265 | </para> |
264 | 266 | ||
265 | <section> |
267 | <section> |
266 | <title>Implementation</title> |
268 | <title>Implementation</title> |
267 | 269 | ||
268 | <para>The slab allocator is closely modelled after OpenSolaris slab |
270 | <para>The slab allocator is closely modelled after OpenSolaris slab |
269 | allocator by Jeff Bonwick and Jonathan Adams <xref |
271 | allocator by Jeff Bonwick and Jonathan Adams <xref |
270 | linkend="Bonwick01" /> with the following exceptions:<itemizedlist> |
272 | linkend="Bonwick01" /> with the following exceptions:<itemizedlist> |
- | 273 | <listitem> |
|
271 | <listitem><para>empty slabs are immediately deallocated and</para></listitem> |
274 | <para>empty slabs are immediately deallocated and</para> |
- | 275 | </listitem> |
|
272 | 276 | ||
273 | <listitem> |
277 | <listitem> |
274 | <para>empty magazines are deallocated when not needed.</para> |
278 | <para>empty magazines are deallocated when not needed.</para> |
275 | </listitem> |
279 | </listitem> |
276 | </itemizedlist>The following features are not currently supported |
280 | </itemizedlist>The following features are not currently supported |
277 | but would be easy to do: <itemizedlist> |
281 | but would be easy to do: <itemizedlist> |
278 | <listitem>cache coloring and</listitem> |
282 | <listitem>cache coloring and</listitem> |
279 | 283 | ||
280 | <listitem>dynamic magazine grow (different magazine sizes are |
284 | <listitem>dynamic magazine grow (different magazine sizes are |
281 | already supported, but the allocation strategy would need to be |
285 | already supported, but the allocation strategy would need to be |
282 | adjusted).</listitem> |
286 | adjusted).</listitem> |
283 | </itemizedlist></para> |
287 | </itemizedlist></para> |
284 | 288 | ||
285 | <section> |
289 | <section> |
286 | <title>Allocation/deallocation</title> |
290 | <title>Allocation/deallocation</title> |
287 | 291 | ||
288 | <para>The following two paragraphs summarize and complete the |
292 | <para>The following two paragraphs summarize and complete the |
289 | description of the slab allocator operation (i.e. |
293 | description of the slab allocator operation (i.e. |
290 | <code>slab_alloc</code> and <code>slab_free</code> |
294 | <code>slab_alloc()</code> and <code>slab_free()</code> |
291 | operations).</para> |
295 | functions).</para> |
292 | 296 | ||
293 | <formalpara> |
297 | <formalpara> |
294 | <title>Allocation</title> |
298 | <title>Allocation</title> |
295 | 299 | ||
296 | <para><emphasis>Step 1.</emphasis> When an allocation request |
300 | <para><emphasis>Step 1.</emphasis> When an allocation request |
297 | comes, the slab allocator checks availability of memory in the |
301 | comes, the slab allocator checks availability of memory in the |
298 | current magazine of the local processor magazine cache. If the |
302 | current magazine of the local processor magazine cache. If the |
299 | available memory is there, the allocator just pops the object from |
303 | available memory is there, the allocator just pops the object from |
300 | magazine and returns it.</para> |
304 | magazine and returns it.</para> |
301 | 305 | ||
302 | <para><emphasis>Step 2.</emphasis> If the current magazine in the |
306 | <para><emphasis>Step 2.</emphasis> If the current magazine in the |
303 | processor magazine cache is empty, the allocator will attempt to |
307 | processor magazine cache is empty, the allocator will attempt to |
304 | swap it with the last magazine from the cache and return to the |
308 | swap it with the last magazine from the cache and return to the |
305 | first step. If also the last magazine is empty, the algorithm will |
309 | first step. If also the last magazine is empty, the algorithm will |
306 | fall through to Step 3.</para> |
310 | fall through to Step 3.</para> |
307 | 311 | ||
308 | <para><emphasis>Step 3.</emphasis> Now the allocator is in the |
312 | <para><emphasis>Step 3.</emphasis> Now the allocator is in the |
309 | situation when both magazines in the processor magazine cache are |
313 | situation when both magazines in the processor magazine cache are |
310 | empty. The allocator reloads one magazine from the shared list of |
314 | empty. The allocator reloads one magazine from the shared list of |
311 | full magazines. If the reload is successful (i.e. there are full |
315 | full magazines. If the reload is successful (i.e. there are full |
312 | magazines in the list), the algorithm continues with Step |
316 | magazines in the list), the algorithm continues with Step |
313 | 1.</para> |
317 | 1.</para> |
314 | 318 | ||
315 | <para><emphasis>Step 4.</emphasis> In this fail-safe step, an |
319 | <para><emphasis>Step 4.</emphasis> In this fail-safe step, an |
316 | object is allocated from the conventional slab layer and a pointer |
320 | object is allocated from the conventional slab layer and a pointer |
317 | to it is returned. If also the last magazine is full,</para> |
321 | to it is returned. If also the last magazine is full,</para> |
318 | </formalpara> |
322 | </formalpara> |
319 | 323 | ||
320 | <formalpara> |
324 | <formalpara> |
321 | <title>Deallocation</title> |
325 | <title>Deallocation</title> |
322 | 326 | ||
323 | <para><emphasis>Step 1.</emphasis> During a deallocation request, |
327 | <para><emphasis>Step 1.</emphasis> During a deallocation request, |
324 | the slab allocator checks if the current magazine of the local |
328 | the slab allocator checks if the current magazine of the local |
325 | processor magazine cache is not full. If it is, the pointer to the |
329 | processor magazine cache is not full. If it is, the pointer to the |
326 | objects is just pushed into the magazine and the algorithm |
330 | objects is just pushed into the magazine and the algorithm |
327 | returns.</para> |
331 | returns.</para> |
328 | 332 | ||
329 | <para><emphasis>Step 2.</emphasis> If the current magazine is |
333 | <para><emphasis>Step 2.</emphasis> If the current magazine is |
330 | full, the allocator will attempt to swap it with the last magazine |
334 | full, the allocator will attempt to swap it with the last magazine |
331 | from the cache and return to the first step. If also the last |
335 | from the cache and return to the first step. If also the last |
332 | magazine is empty, the algorithm will fall through to Step |
336 | magazine is empty, the algorithm will fall through to Step |
333 | 3.</para> |
337 | 3.</para> |
334 | 338 | ||
335 | <para><emphasis>Step 3.</emphasis> Now the allocator is in the |
339 | <para><emphasis>Step 3.</emphasis> Now the allocator is in the |
336 | situation when both magazines in the processor magazine cache are |
340 | situation when both magazines in the processor magazine cache are |
337 | full. The allocator tries to allocate a new empty magazine and |
341 | full. The allocator tries to allocate a new empty magazine and |
338 | flush one of the full magazines to the shared list of full |
342 | flush one of the full magazines to the shared list of full |
339 | magazines. If it is successfull, the algoritm continues with Step |
343 | magazines. If it is successfull, the algoritm continues with Step |
340 | 1.</para> |
344 | 1.</para> |
341 | 345 | ||
342 | <para><emphasis>Step 4. </emphasis>In case of low memory condition |
346 | <para><emphasis>Step 4. </emphasis>In case of low memory condition |
343 | when the allocation of empty magazine fails, the object is moved |
347 | when the allocation of empty magazine fails, the object is moved |
344 | directly into slab. In the worst case object deallocation does not |
348 | directly into slab. In the worst case object deallocation does not |
345 | need to allocate any additional memory.</para> |
349 | need to allocate any additional memory.</para> |
346 | </formalpara> |
350 | </formalpara> |
347 | </section> |
351 | </section> |
348 | </section> |
352 | </section> |
349 | </section> |
353 | </section> |
350 | </section> |
354 | </section> |
351 | 355 | ||
352 | <section> |
356 | <section> |
353 | <title>Virtual memory management</title> |
357 | <title>Virtual memory management</title> |
354 | 358 | ||
- | 359 | <para>Virtual memory is essential for an operating system because it makes |
|
- | 360 | several things possible. First, it helps to isolate tasks from each other |
|
- | 361 | by encapsulating them in their private address spaces. Second, virtual |
|
- | 362 | memory can give tasks the feeling of more memory available than is |
|
- | 363 | actually possible. And third, by using virtual memory, there might be |
|
- | 364 | multiple copies of the same program, linked to the same addresses, running |
|
- | 365 | in the system. There are at least two known mechanisms for implementing |
|
- | 366 | virtual memory: segmentation and paging. Even though some processor |
|
- | 367 | architectures supported by HelenOS<footnote> |
|
- | 368 | <para>ia32 has full-fledged segmentation.</para> |
|
- | 369 | </footnote> provide both mechanism, the kernel makes use solely of |
|
- | 370 | paging.</para> |
|
- | 371 | ||
355 | <section> |
372 | <section id="paging"> |
356 | <title>Introduction</title> |
373 | <title>VAT subsystem</title> |
- | 374 | ||
- | 375 | <para>In a paged virtual memory, the entire virtual address space is |
|
- | 376 | divided into small power-of-two sized naturally aligned blocks called |
|
- | 377 | pages. The processor implements a translation mechanism, that allows the |
|
- | 378 | operating system to manage mappings between set of pages and set of |
|
- | 379 | indentically sized and identically aligned pieces of physical memory |
|
- | 380 | called frames. In a result, references to continuous virtual memory |
|
- | 381 | areas don't necessarily need to reference continuos area of physical |
|
- | 382 | memory. Supported page sizes usually range from several kilobytes to |
|
- | 383 | several megabytes. Each page that takes part in the mapping is |
|
- | 384 | associated with certain attributes that further desribe the mapping |
|
- | 385 | (e.g. access rights, dirty and accessed bits and present bit).</para> |
|
- | 386 | ||
- | 387 | <para>When the processor accesses a page that is not present (i.e. its |
|
- | 388 | present bit is not set), the operating system is notified through a |
|
- | 389 | special exception called page fault. It is then up to the operating |
|
- | 390 | system to service the page fault. In HelenOS, some page faults are fatal |
|
- | 391 | and result in either task termination or, in the worse case, kernel |
|
- | 392 | panic<footnote> |
|
- | 393 | <para>Such a condition would be either caused by a hardware failure |
|
- | 394 | or a bug in the kernel.</para> |
|
- | 395 | </footnote>, while other page faults are used to load memory on demand |
|
- | 396 | or to notify the kernel about certain events.</para> |
|
- | 397 | ||
- | 398 | <indexterm> |
|
- | 399 | <primary>page tables</primary> |
|
- | 400 | </indexterm> |
|
- | 401 | ||
- | 402 | <para>The set of all page mappings is stored in a memory structure |
|
- | 403 | called page tables. Some architectures have no hardware support for page |
|
- | 404 | tables<footnote> |
|
- | 405 | <para>On mips32, TLB-only model is used and the operating system is |
|
- | 406 | responsible for managing software defined page tables.</para> |
|
- | 407 | </footnote> while other processor architectures<footnote> |
|
- | 408 | <para>Like amd64 and ia32.</para> |
|
- | 409 | </footnote> understand the whole memory format thereof. Despite all |
|
- | 410 | the possible differences in page table formats, the HelenOS VAT |
|
- | 411 | subsystem<footnote> |
|
- | 412 | <para>Virtual Address Translation subsystem.</para> |
|
- | 413 | </footnote> unifies the page table operations under one programming |
|
- | 414 | interface. For all parts of the kernel, three basic functions are |
|
- | 415 | provided:</para> |
|
- | 416 | ||
- | 417 | <itemizedlist> |
|
- | 418 | <listitem> |
|
- | 419 | <para><code>page_mapping_insert()</code>,</para> |
|
- | 420 | </listitem> |
|
- | 421 | ||
- | 422 | <listitem> |
|
- | 423 | <para><code>page_mapping_find()</code> and</para> |
|
- | 424 | </listitem> |
|
- | 425 | ||
- | 426 | <listitem> |
|
- | 427 | <para><code>page_mapping_remove()</code>.</para> |
|
- | 428 | </listitem> |
|
- | 429 | </itemizedlist> |
|
- | 430 | ||
- | 431 | <para>The <code>page_mapping_insert()</code> function is used to |
|
- | 432 | introduce a mapping for one virtual memory page belonging to a |
|
- | 433 | particular address space into the page tables. Once the mapping is in |
|
- | 434 | the page tables, it can be searched by <code>page_mapping_find()</code> |
|
- | 435 | and removed by <code>page_mapping_remove()</code>. All of these |
|
- | 436 | functions internally select the page table mechanism specific functions |
|
- | 437 | that carry out the self operation.</para> |
|
- | 438 | ||
- | 439 | <para>There are currently two supported mechanisms: generic 4-level |
|
- | 440 | hierarchical page tables and global page hash table. Both of the |
|
- | 441 | mechanisms are generic as they cover several hardware platforms. For |
|
- | 442 | instance, the 4-level hierarchical page table mechanism is used by |
|
- | 443 | amd64, ia32, mips32 and ppc32, respectively. These architectures have |
|
- | 444 | the following page table format: 4-level, 2-level, TLB-only and hardware |
|
- | 445 | hash table, respectively. On the other hand, the global page hash table |
|
- | 446 | is used on ia64 that can be TLB-only or use a hardware hash table. |
|
- | 447 | Although only two mechanisms are currently implemented, other mechanisms |
|
- | 448 | (e.g. B+tree) can be easily added.</para> |
|
- | 449 | ||
- | 450 | <section id="page_tables"> |
|
- | 451 | <indexterm> |
|
- | 452 | <primary>page tables</primary> |
|
- | 453 | ||
- | 454 | <secondary>- hierarchical</secondary> |
|
- | 455 | </indexterm> |
|
357 | 456 | ||
358 | <para>Virtual memory is a special memory management technique, used by |
457 | <title>Hierarchical 4-level page tables</title> |
359 | kernel to achieve a bunch of mission critical goals. <itemizedlist> |
- | |
360 | <listitem> |
- | |
361 | Isolate each task from other tasks that are running on the system at the same time. |
- | |
362 | </listitem> |
- | |
363 | 458 | ||
364 | <listitem> |
459 | <para>Hierarchical 4-level page tables are generalization of the |
365 | Allow to allocate more memory, than is actual physical memory size of the machine. |
460 | frequently used hierarchical model of page tables. In this mechanism, |
366 | </listitem> |
461 | each address space has its own page tables. To avoid confusion in |
367 | - | ||
368 | <listitem> |
462 | terminology used by hardware vendors, in HelenOS, the root level page |
369 | Allowing, in general, to load and execute two programs that are linked on the same address without complicated relocations. |
463 | table is called PTL0, the two middle levels are called PTL1 and PTL2, |
370 | </listitem> |
464 | and, finally, the leaf level is called PTL3. All architectures using |
371 | </itemizedlist></para> |
465 | this mechanism are required to use PTL0 and PTL3. However, the middle |
372 | - | ||
373 | <para><!-- |
- | |
374 | <para> |
466 | levels can be left out, depending on the hardware hierachy or |
375 | Address spaces. Address space area (B+ tree). Only for uspace. Set of syscalls (shrink/extend etc). |
467 | structure of software-only page tables. The genericity is achieved |
376 | Special address space area type - device - prohibits shrink/extend syscalls to call on it. |
468 | through a set of macros that define transitions from one level to |
377 | Address space has link to mapping tables (hierarchical - per Address space, hash - global tables). |
469 | another. Unused levels are optimised out by the compiler.</para> |
378 | </para> |
470 | </section> |
379 | 471 | ||
- | 472 | <section> |
|
- | 473 | <indexterm> |
|
- | 474 | <primary>page tables</primary> |
|
- | 475 | ||
- | 476 | <secondary>- hashing</secondary> |
|
- | 477 | </indexterm> |
|
- | 478 | ||
- | 479 | <title>Global page hash table</title> |
|
- | 480 | ||
- | 481 | <para>Implementation of the global page hash table was encouraged by |
|
- | 482 | 64-bit architectures that can have rather sparse address spaces. The |
|
- | 483 | hash table contains valid mappings only. Each entry of the hash table |
|
- | 484 | contains an address space pointer, virtual memory page number (VPN), |
|
- | 485 | physical memory frame number (PFN) and a set of flags. The pair of the |
|
- | 486 | address space pointer and the virtual memory page number is used as a |
|
- | 487 | key for the hash table. One of the major differences between the |
|
- | 488 | global page hash table and hierarchical 4-level page tables is that |
|
- | 489 | there is only a single global page hash table in the system while |
|
- | 490 | hierarchical page tables exist per address space. Thus, the global |
|
- | 491 | page hash table contains information about mappings of all address |
|
- | 492 | spaces in the system. </para> |
|
- | 493 | ||
- | 494 | <para>The global page hash table mechanism uses the generic hash table |
|
- | 495 | type as described in the chapter about <link linkend="hashtables">data |
|
- | 496 | structures</link> earlier in this book.</para> |
|
- | 497 | </section> |
|
- | 498 | </section> |
|
- | 499 | </section> |
|
- | 500 | ||
- | 501 | <section id="tlb"> |
|
- | 502 | <indexterm> |
|
- | 503 | <primary>TLB</primary> |
|
- | 504 | </indexterm> |
|
- | 505 | ||
- | 506 | <title>Translation Lookaside buffer</title> |
|
- | 507 | ||
- | 508 | <para>Due to the extensive overhead during the page mapping lookup in the |
|
- | 509 | page tables, all architectures has fast assotiative cache memory built-in |
|
- | 510 | CPU. This memory called TLB stores recently used page table |
|
- | 511 | entries.</para> |
|
- | 512 | ||
- | 513 | <section id="tlb_shootdown"> |
|
- | 514 | <indexterm> |
|
- | 515 | <primary>TLB</primary> |
|
- | 516 | ||
- | 517 | <secondary>- TLB shootdown</secondary> |
|
- | 518 | </indexterm> |
|
- | 519 | ||
- | 520 | <title>TLB consistency. TLB shootdown algorithm.</title> |
|
- | 521 | ||
- | 522 | <para>Operating system is responsible for keeping TLB consistent by |
|
- | 523 | invalidating the contents of TLB, whenever there is some change in page |
|
- | 524 | tables. Those changes may occur when page or group of pages were |
|
- | 525 | unmapped, mapping is changed or system switching active address space to |
|
- | 526 | schedule a new system task. Moreover, this invalidation operation must |
|
- | 527 | be done an all system CPUs because each CPU has its own independent TLB |
|
- | 528 | cache. Thus maintaining TLB consistency on SMP configuration as not as |
|
- | 529 | trivial task as it looks on the first glance. Naive solution would |
|
- | 530 | assume that is the CPU which wants to invalidate TLB will invalidate TLB |
|
- | 531 | caches on other CPUs. It is not possible on the most of the |
|
- | 532 | architectures, because of the simple fact - flushing TLB is allowed only |
|
- | 533 | on the local CPU and there is no possibility to access other CPUs' TLB |
|
- | 534 | caches, thus invalidate TLB remotely.</para> |
|
- | 535 | ||
- | 536 | <para>Technique of remote invalidation of TLB entries is called "TLB |
|
- | 537 | shootdown". HelenOS uses a variation of the algorithm described by D. |
|
- | 538 | Black et al., "Translation Lookaside Buffer Consistency: A Software |
|
- | 539 | Approach," Proc. Third Int'l Conf. Architectural Support for Programming |
|
- | 540 | Languages and Operating Systems, 1989, pp. 113-122. <xref |
|
- | 541 | linkend="Black89" /></para> |
|
- | 542 | ||
- | 543 | <para>As the situation demands, you will want partitial invalidation of |
|
- | 544 | TLB caches. In case of simple memory mapping change it is necessary to |
|
- | 545 | invalidate only one or more adjacent pages. In case if the architecture |
|
- | 546 | is aware of ASIDs, when kernel needs to dump some ASID to use by another |
|
- | 547 | task, it invalidates only entries from this particular address space. |
|
- | 548 | Final option of the TLB invalidation is the complete TLB cache |
|
- | 549 | invalidation, which is the operation that flushes all entries in |
|
380 | --></para> |
550 | TLB.</para> |
- | 551 | ||
- | 552 | <para>TLB shootdown is performed in two phases.</para> |
|
- | 553 | ||
- | 554 | <formalpara> |
|
- | 555 | <title>Phase 1.</title> |
|
- | 556 | ||
- | 557 | <para>First, initiator locks a global TLB spinlock, then request is |
|
- | 558 | being put to the local request cache of every other CPU in the system |
|
- | 559 | protected by its spinlock. In case the cache is full, all requests in |
|
- | 560 | the cache are replaced by one request, indicating global TLB flush. |
|
- | 561 | Then the initiator thread sends an IPI message indicating the TLB |
|
- | 562 | shootdown request to the rest of the CPUs and waits actively until all |
|
- | 563 | CPUs confirm TLB invalidating action execution by setting up a special |
|
- | 564 | flag. After setting this flag this thread is blocked on the TLB |
|
- | 565 | spinlock, held by the initiator.</para> |
|
- | 566 | </formalpara> |
|
- | 567 | ||
- | 568 | <formalpara> |
|
- | 569 | <title>Phase 2.</title> |
|
- | 570 | ||
- | 571 | <para>All CPUs are waiting on the TLB spinlock to execute TLB |
|
- | 572 | invalidation action and have indicated their intention to the |
|
- | 573 | initiator. Initiator continues, cleaning up its TLB and releasing the |
|
- | 574 | global TLB spinlock. After this all other CPUs gain and immidiately |
|
- | 575 | release TLB spinlock and perform TLB invalidation actions.</para> |
|
- | 576 | </formalpara> |
|
381 | </section> |
577 | </section> |
382 | 578 | ||
383 | <section> |
579 | <section> |
384 | <title>Address spaces</title> |
580 | <title>Address spaces</title> |
385 | 581 | ||
386 | <section> |
582 | <section> |
387 | <indexterm> |
583 | <indexterm> |
388 | <primary>address space</primary> |
584 | <primary>address space</primary> |
389 | 585 | ||
390 | <secondary>- area</secondary> |
586 | <secondary>- area</secondary> |
391 | </indexterm> |
587 | </indexterm> |
392 | 588 | ||
393 | <title>Address space areas</title> |
589 | <title>Address space areas</title> |
394 | 590 | ||
395 | <para>Each address space consists of mutually disjunctive continuous |
591 | <para>Each address space consists of mutually disjunctive continuous |
396 | address space areas. Address space area is precisely defined by its |
592 | address space areas. Address space area is precisely defined by its |
397 | base address and the number of frames/pages is contains.</para> |
593 | base address and the number of frames/pages is contains.</para> |
398 | 594 | ||
399 | <para>Address space area , that define behaviour and permissions on |
595 | <para>Address space area , that define behaviour and permissions on |
400 | the particular area. <itemizedlist> |
596 | the particular area. <itemizedlist> |
401 | <listitem><emphasis>AS_AREA_READ</emphasis> flag indicates reading |
597 | <listitem><emphasis>AS_AREA_READ</emphasis> flag indicates reading |
402 | permission.</listitem> |
598 | permission.</listitem> |
403 | 599 | ||
404 | <listitem><emphasis>AS_AREA_WRITE</emphasis> flag indicates |
600 | <listitem><emphasis>AS_AREA_WRITE</emphasis> flag indicates |
405 | writing permission.</listitem> |
601 | writing permission.</listitem> |
406 | 602 | ||
407 | <listitem><emphasis>AS_AREA_EXEC</emphasis> flag indicates code |
603 | <listitem><emphasis>AS_AREA_EXEC</emphasis> flag indicates code |
408 | execution permission. Some architectures do not support execution |
604 | execution permission. Some architectures do not support execution |
409 | persmission restriction. In this case this flag has no |
605 | persmission restriction. In this case this flag has no |
410 | effect.</listitem> |
606 | effect.</listitem> |
411 | 607 | ||
412 | <listitem><emphasis>AS_AREA_DEVICE</emphasis> marks area as mapped |
608 | <listitem><emphasis>AS_AREA_DEVICE</emphasis> marks area as mapped |
413 | to the device memory.</listitem> |
609 | to the device memory.</listitem> |
414 | </itemizedlist></para> |
610 | </itemizedlist></para> |
415 | 611 | ||
416 | <para>Kernel provides possibility tasks create/expand/shrink/share its |
612 | <para>Kernel provides possibility tasks create/expand/shrink/share its |
417 | address space via the set of syscalls.</para> |
613 | address space via the set of syscalls.</para> |
418 | </section> |
614 | </section> |
419 | 615 | ||
420 | <section> |
616 | <section> |
421 | <indexterm> |
617 | <indexterm> |
422 | <primary>address space</primary> |
618 | <primary>address space</primary> |
423 | 619 | ||
424 | <secondary>- ASID</secondary> |
620 | <secondary>- ASID</secondary> |
425 | </indexterm> |
621 | </indexterm> |
426 | 622 | ||
427 | <title>Address Space ID (ASID)</title> |
623 | <title>Address Space ID (ASID)</title> |
428 | 624 | ||
429 | <para>Every task in the operating system has it's own view of the |
625 | <para>Every task in the operating system has it's own view of the |
430 | virtual memory. When performing context switch between different |
626 | virtual memory. When performing context switch between different |
431 | tasks, the kernel must switch the address space mapping as well. As |
627 | tasks, the kernel must switch the address space mapping as well. As |
432 | modern processors perform very aggressive caching of virtual mappings, |
628 | modern processors perform very aggressive caching of virtual mappings, |
433 | flushing the complete TLB on every context switch would be very |
629 | flushing the complete TLB on every context switch would be very |
434 | inefficient. To avoid such performance penalty, some architectures |
630 | inefficient. To avoid such performance penalty, some architectures |
435 | introduce an address space identifier, which allows storing several |
631 | introduce an address space identifier, which allows storing several |
436 | different mappings inside TLB.</para> |
632 | different mappings inside TLB.</para> |
437 | 633 | ||
438 | <para>HelenOS kernel can take advantage of this hardware support by |
634 | <para>HelenOS kernel can take advantage of this hardware support by |
439 | having an ASID abstraction. I.e. on ia64 kernel ASID is derived from |
635 | having an ASID abstraction. I.e. on ia64 kernel ASID is derived from |
440 | RID (region identifier) and on the mips32 kernel ASID is actually the |
636 | RID (region identifier) and on the mips32 kernel ASID is actually the |
441 | hardware identifier. As expected, this ASID information record is the |
637 | hardware identifier. As expected, this ASID information record is the |
442 | part of <emphasis>as_t</emphasis> structure.</para> |
638 | part of <emphasis>as_t</emphasis> structure.</para> |
443 | 639 | ||
444 | <para>Due to the hardware limitations, hardware ASID has limited |
640 | <para>Due to the hardware limitations, hardware ASID has limited |
445 | length from 8 bits on ia64 to 24 bits on mips32, which makes it |
641 | length from 8 bits on ia64 to 24 bits on mips32, which makes it |
446 | impossible to use it as unique address space identifier for all tasks |
642 | impossible to use it as unique address space identifier for all tasks |
447 | running in the system. In such situations special ASID stealing |
643 | running in the system. In such situations special ASID stealing |
448 | algoritm is used, which takes ASID from inactive task and assigns it |
644 | algoritm is used, which takes ASID from inactive task and assigns it |
449 | to the active task.</para> |
645 | to the active task.</para> |
450 | 646 | ||
451 | <indexterm> |
647 | <indexterm> |
452 | <primary>address space</primary> |
648 | <primary>address space</primary> |
453 | 649 | ||
454 | <secondary>- ASID stealing</secondary> |
650 | <secondary>- ASID stealing</secondary> |
455 | </indexterm> |
651 | </indexterm> |
456 | 652 | ||
457 | <para> |
653 | <para> |
458 | <classname>ASID stealing algoritm here.</classname> |
654 | <classname>ASID stealing algoritm here.</classname> |
459 | </para> |
655 | </para> |
460 | </section> |
656 | </section> |
461 | </section> |
- | |
462 | - | ||
463 | <section id="paging"> |
- | |
464 | <title>Virtual address translation</title> |
- | |
465 | - | ||
466 | <section> |
- | |
467 | <title>Introduction</title> |
- | |
468 | - | ||
469 | <para>Virtual memory is usually using paged memory model, where |
- | |
470 | virtual memory address space is divided into the |
- | |
471 | <emphasis>pages</emphasis> (usually having size 4096 bytes) and |
- | |
472 | physical memory is divided into the frames (same sized as a page, of |
- | |
473 | course). Each page may be mapped to some frame and then, upon memory |
- | |
474 | access to the virtual address, CPU performs <emphasis>address |
- | |
475 | translation</emphasis> during the instruction execution. Non-existing |
- | |
476 | mapping generates page fault exception, calling kernel exception |
- | |
477 | handler, thus allowing kernel to manipulate rules of memory access. |
- | |
478 | Information for pages mapping is stored by kernel in the <link |
- | |
479 | linkend="page_tables">page tables</link></para> |
- | |
480 | - | ||
481 | <indexterm> |
- | |
482 | <primary>page tables</primary> |
- | |
483 | </indexterm> |
- | |
484 | - | ||
485 | <para>The majority of the architectures use multi-level page tables, |
- | |
486 | which means need to access physical memory several times before |
- | |
487 | getting physical address. This fact would make serios performance |
- | |
488 | overhead in virtual memory management. To avoid this <link |
- | |
489 | linkend="tlb">Traslation Lookaside Buffer (TLB)</link> is used.</para> |
- | |
490 | - | ||
491 | <para>HelenOS kernel has two different approaches to the paging |
- | |
492 | implementation: <emphasis>4 level page tables</emphasis> and |
- | |
493 | <emphasis>global hash table</emphasis>, which are accessible via |
- | |
494 | generic paging abstraction layer. Such different functionality was |
- | |
495 | caused by the major architectural differences between supported |
- | |
496 | platforms. This abstraction is implemented with help of the global |
- | |
497 | structure of pointers to basic mapping functions |
- | |
498 | <emphasis>page_mapping_operations</emphasis>. To achieve different |
- | |
499 | functionality of page tables, corresponding layer must implement |
- | |
500 | functions, declared in |
- | |
501 | <emphasis>page_mapping_operations</emphasis></para> |
- | |
502 | - | ||
503 | <para>Thanks to the abstract paging interface, there was a place left |
- | |
504 | for more paging implementations (besides already implemented |
- | |
505 | hieararchical page tables and hash table), for example <indexterm> |
- | |
506 | <primary>B-tree</primary> |
- | |
507 | </indexterm> B-Tree based page tables.</para> |
- | |
508 | </section> |
- | |
509 | - | ||
510 | <section id="page_tables"> |
- | |
511 | <indexterm> |
- | |
512 | <primary>page tables</primary> |
- | |
513 | - | ||
514 | <secondary>- hierarchical</secondary> |
- | |
515 | </indexterm> |
- | |
516 | - | ||
517 | <title>Hierarchical 4-level page tables</title> |
- | |
518 | - | ||
519 | <para>Hierarchical 4-level page tables are the generalization of the |
- | |
520 | hardware capabilities of most architectures. Each address space has |
- | |
521 | its own page tables.<itemizedlist> |
- | |
522 | <listitem>ia32 uses 2-level page tables, with full hardware |
- | |
523 | support.</listitem> |
- | |
524 | - | ||
525 | <listitem>amd64 uses 4-level page tables, also coming with full |
- | |
526 | hardware support.</listitem> |
- | |
527 | - | ||
528 | <listitem>mips and ppc32 have 2-level tables, software simulated |
- | |
529 | support.</listitem> |
- | |
530 | </itemizedlist></para> |
- | |
531 | </section> |
- | |
532 | - | ||
533 | <section> |
- | |
534 | <indexterm> |
- | |
535 | <primary>page tables</primary> |
- | |
536 | - | ||
537 | <secondary>- hashing</secondary> |
- | |
538 | </indexterm> |
- | |
539 | - | ||
540 | <title>Global hash table</title> |
- | |
541 | - | ||
542 | <para>Implementation of the global hash table was encouraged by the |
- | |
543 | ia64 architecture support. One of the major differences between global |
- | |
544 | hash table and hierarchical tables is that global hash table exists |
- | |
545 | only once in the system and the hierarchical tables are maintained per |
- | |
546 | address space.</para> |
- | |
547 | - | ||
548 | <para>Thus, hash table contains information about all address spaces |
- | |
549 | mappings in the system, so, the hash of an entry must contain |
- | |
550 | information of both address space pointer or id and the virtual |
- | |
551 | address of the page. Generic hash table implementation assumes that |
- | |
552 | the addresses of the pointers to the address spaces are likely to be |
- | |
553 | on the close addresses, so it uses least significant bits for hash; |
- | |
554 | also it assumes that the virtual page addresses have roughly the same |
- | |
555 | probability of occurring, so the least significant bits of VPN compose |
- | |
556 | the hash index.</para> |
- | |
557 | - | ||
558 | <para>Paging hash table uses generic hash table with collision chains |
- | |
559 | (see the <link linkend="hashtables">Data Structures</link> chapter of |
- | |
560 | this manual for details).</para> |
- | |
561 | </section> |
- | |
562 | </section> |
- | |
563 | - | ||
564 | <section id="tlb"> |
- | |
565 | <indexterm> |
- | |
566 | <primary>TLB</primary> |
- | |
567 | </indexterm> |
- | |
568 | - | ||
569 | <title>Translation Lookaside buffer</title> |
- | |
570 | - | ||
571 | <para>Due to the extensive overhead during the page mapping lookup in |
- | |
572 | the page tables, all architectures has fast assotiative cache memory |
- | |
573 | built-in CPU. This memory called TLB stores recently used page table |
- | |
574 | entries.</para> |
- | |
575 | - | ||
576 | <section id="tlb_shootdown"> |
- | |
577 | <indexterm> |
- | |
578 | <primary>TLB</primary> |
- | |
579 | - | ||
580 | <secondary>- TLB shootdown</secondary> |
- | |
581 | </indexterm> |
- | |
582 | - | ||
583 | <title>TLB consistency. TLB shootdown algorithm.</title> |
- | |
584 | - | ||
585 | <para>Operating system is responsible for keeping TLB consistent by |
- | |
586 | invalidating the contents of TLB, whenever there is some change in |
- | |
587 | page tables. Those changes may occur when page or group of pages were |
- | |
588 | unmapped, mapping is changed or system switching active address space |
- | |
589 | to schedule a new system task. Moreover, this invalidation operation |
- | |
590 | must be done an all system CPUs because each CPU has its own |
- | |
591 | independent TLB cache. Thus maintaining TLB consistency on SMP |
- | |
592 | configuration as not as trivial task as it looks on the first glance. |
- | |
593 | Naive solution would assume that is the CPU which wants to invalidate |
- | |
594 | TLB will invalidate TLB caches on other CPUs. It is not possible on |
- | |
595 | the most of the architectures, because of the simple fact - flushing |
- | |
596 | TLB is allowed only on the local CPU and there is no possibility to |
- | |
597 | access other CPUs' TLB caches, thus invalidate TLB remotely.</para> |
- | |
598 | - | ||
599 | <para>Technique of remote invalidation of TLB entries is called "TLB |
- | |
600 | shootdown". HelenOS uses a variation of the algorithm described by D. |
- | |
601 | Black et al., "Translation Lookaside Buffer Consistency: A Software |
- | |
602 | Approach," Proc. Third Int'l Conf. Architectural Support for |
- | |
603 | Programming Languages and Operating Systems, 1989, pp. 113-122. <xref |
- | |
604 | linkend="Black89" /></para> |
- | |
605 | - | ||
606 | <para>As the situation demands, you will want partitial invalidation |
- | |
607 | of TLB caches. In case of simple memory mapping change it is necessary |
- | |
608 | to invalidate only one or more adjacent pages. In case if the |
- | |
609 | architecture is aware of ASIDs, when kernel needs to dump some ASID to |
- | |
610 | use by another task, it invalidates only entries from this particular |
- | |
611 | address space. Final option of the TLB invalidation is the complete |
- | |
612 | TLB cache invalidation, which is the operation that flushes all |
- | |
613 | entries in TLB.</para> |
- | |
614 | - | ||
615 | <para>TLB shootdown is performed in two phases.</para> |
- | |
616 | - | ||
617 | <formalpara> |
- | |
618 | <title>Phase 1.</title> |
- | |
619 | - | ||
620 | <para>First, initiator locks a global TLB spinlock, then request is |
- | |
621 | being put to the local request cache of every other CPU in the |
- | |
622 | system protected by its spinlock. In case the cache is full, all |
- | |
623 | requests in the cache are replaced by one request, indicating global |
- | |
624 | TLB flush. Then the initiator thread sends an IPI message indicating |
- | |
625 | the TLB shootdown request to the rest of the CPUs and waits actively |
- | |
626 | until all CPUs confirm TLB invalidating action execution by setting |
- | |
627 | up a special flag. After setting this flag this thread is blocked on |
- | |
628 | the TLB spinlock, held by the initiator.</para> |
- | |
629 | </formalpara> |
- | |
630 | - | ||
631 | <formalpara> |
- | |
632 | <title>Phase 2.</title> |
- | |
633 | - | ||
634 | <para>All CPUs are waiting on the TLB spinlock to execute TLB |
- | |
635 | invalidation action and have indicated their intention to the |
- | |
636 | initiator. Initiator continues, cleaning up its TLB and releasing |
- | |
637 | the global TLB spinlock. After this all other CPUs gain and |
- | |
638 | immidiately release TLB spinlock and perform TLB invalidation |
- | |
639 | actions.</para> |
- | |
640 | </formalpara> |
- | |
641 | </section> |
- | |
642 | </section> |
657 | </section> |
643 | </section> |
658 | </section> |
644 | </chapter> |
659 | </chapter> |