Subversion Repositories HelenOS-doc

Rev

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