Rev 64 | Rev 66 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 64 | Rev 65 | ||
---|---|---|---|
Line 159... | Line 159... | ||
159 | <section id="slab"> |
159 | <section id="slab"> |
160 | <title>Slab allocator</title> |
160 | <title>Slab allocator</title> |
161 | 161 | ||
162 | <para>The majority of memory allocation requests in the kernel is for |
162 | <para>The majority of memory allocation requests in the kernel is for |
163 | small, frequently used data structures. The basic idea behind the slab |
163 | small, frequently used data structures. The basic idea behind the slab |
164 | allocator is that deployment of lists of preallocated, commonly used |
164 | allocator is that commonly used objects are preallocated in continuous |
165 | objects. Whenever an object is to be allocated, the slab allocator takes |
165 | areas of physical memory called slabs<footnote> |
166 | the first item from the list corresponding to the object type. This |
166 | <para>Slabs are in fact blocks of physical memory frames allocated |
167 | avoids the overhead of allocating and dellocating commonly used types of |
167 | from the frame allocator.</para> |
168 | objects such as threads, B+tree nodes etc. Due to the fact that the |
- | |
169 | sizes of the requested and allocated object match, the slab allocator |
168 | </footnote>. Whenever an object is to be allocated, the slab allocator |
170 | significantly eliminates internal fragmentation. Moreover, each list can |
169 | returns the first available item from a suitable slab corresponding to |
171 | have a constructor and a destructor, which leads to performance gains |
170 | the object type<footnote> |
172 | because constructed and then destroyed objects don't need to be |
171 | <para>The mechanism is rather more complicated, see the next |
173 | reinitialized<footnote> |
172 | paragraph.</para> |
174 | <para>Provided that the assumption that the destructor leaves the |
173 | </footnote>. Due to the fact that the sizes of the requested and |
175 | object in a consistent state holds.</para> |
174 | allocated object match, the slab allocator significantly freduces |
176 | </footnote>.</para> |
175 | internal fragmentation.</para> |
177 | 176 | ||
178 | <para>In the slab allocator, objects of one type are kept in continuous |
177 | <para>Slabs of one object type are organized in a structure called slab |
179 | areas of physical memory called slabs. Slabs can span from one to |
178 | cache. There are ususally more slabs in the slab cache, depending on |
180 | several physical memory frames. Slabs of objects of one type are stored |
179 | previous allocations. If the the slab cache runs out of available slabs, |
181 | in slab caches. When the allocator needs to allocate an object, it |
180 | new slabs are allocated. In order to exploit parallelism and to avoid |
182 | searches available slabs. When the slab does not contain any free |
181 | locking of shared spinlocks, slab caches can have variants of |
- | 182 | CPU-private slabs called magazines. Each object begins its life in a |
|
183 | obejct, a new slab is allocated and added to the cache. Contrary to |
183 | slab. When it is allocated from there, the slab allocator calls a |
184 | allocation, deallocated objects are returned to their respective slabs. |
184 | constructor that is registered in the respective slab cache. The |
- | 185 | constructor initializes and brings the object into a known state. The |
|
- | 186 | object is then used by the user. When the user later frees the object, |
|
- | 187 | the slab allocator puts it into a CPU-private magazine, from where it |
|
185 | Empty slabs are deallocated immediately while empty slab caches are not |
188 | can be precedently allocated again. Note that allocations satisfied from |
- | 189 | a magazine are already initialized by the constructor.</para> |
|
- | 190 | ||
186 | freed until HelenOS runs short of memory.</para> |
191 | <para>Should HelenOS run short of memory, it would start deallocating |
- | 192 | objects from magazines, calling slab cache destructor on them and |
|
- | 193 | putting them back into slabs. When a slab contanins no allocated object, |
|
- | 194 | it is immediately freed.</para> |
|
187 | 195 | ||
188 | <para><figure> |
196 | <para><figure> |
189 | <mediaobject id="slab_alloc"> |
197 | <mediaobject id="slab_alloc"> |
190 | <imageobject role="html"> |
198 | <imageobject role="html"> |
191 | <imagedata fileref="images/slab_alloc.png" format="PNG" /> |
199 | <imagedata fileref="images/slab_alloc.png" format="PNG" /> |
192 | </imageobject> |
200 | </imageobject> |
193 | - | ||
194 | <imageobject role="fop"> |
- | |
195 | <imagedata fileref="images.vector/slab_alloc.svg" format="SVG" /> |
- | |
196 | </imageobject> |
- | |
197 | </mediaobject> |
201 | </mediaobject> |
198 | 202 | ||
199 | <title>Slab allocator scheme.</title> |
203 | <title>Slab allocator scheme.</title> |
200 | </figure></para> |
204 | </figure></para> |
201 | 205 | ||
202 | <section> |
206 | <section> |
203 | <para> |
- | |
204 | <termdef /> |
- | |
205 | - | ||
206 | |
- | |
207 | - | ||
208 | <termdef /> |
- | |
209 | </para> |
- | |
210 | </section> |
- | |
211 | - | ||
212 | <section> |
- | |
213 | <title>Implementation</title> |
207 | <title>Implementation</title> |
214 | 208 | ||
215 | <para>The slab allocator is closely modelled after <ulink |
209 | <para>The slab allocator is closely modelled after <ulink |
216 | url="http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/"> |
210 | url="http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/"> |
217 | OpenSolaris slab allocator by Jeff Bonwick and Jonathan Adams </ulink> |
211 | OpenSolaris slab allocator by Jeff Bonwick and Jonathan Adams </ulink> |
218 | with the following exceptions:<itemizedlist> |
212 | with the following exceptions:<itemizedlist> |
219 | <listitem></listitem> |
- | |
220 | - | ||
221 | <listitem> |
213 | <listitem> |
222 | empty magazines are deallocated when not needed |
214 | empty magazines are deallocated when not needed |
223 | </listitem> |
215 | </listitem> |
224 | </itemizedlist> Following features are not currently supported but |
216 | </itemizedlist> Following features are not currently supported but |
225 | would be easy to do: <itemizedlist> |
217 | would be easy to do: <itemizedlist> |
226 | <listitem> |
218 | <listitem> |
227 | cache coloring |
219 | cache coloring |