docs/SLOB.tex

   1 \documentclass[a4paper,10pt]{article}
   2
   3 \begin{document}
   4
   5 \title{\textbf{SLOB allocator}}
   6 \author{Pawel Dziepak}
   7 \date{\textit{July 25, 2008}}
   8 \maketitle
   9
  10 \section{Introduction}
  11 \paragraph{}SLOB (Simple List of Blocks) allocator was designed and created by Matt Mackall
  12 to use it in Linux kernel while working on embedded system. Its advantages
  13 are speed and small size of stored metadata. On the other hand SLOB allocator
  14 memory quickly gets fragmented.
  15
  16 \section{Algorithm}
  17 \paragraph{}SLOB is based on standard K\&R (Kernighan \& Ritchie) heap allocator. It stores
  18 lists of memory areas that are allocated. When system needs more space on heap
  19 allocator goes through the areas and looks for a space between two blocks that
  20 is big enough to fit new object. If none is found algorithm allocate memory
  21 after the last block. SLOB uses first-fit policy which can be easily replaced
  22 (by inheritance of slob class and replacing slob::allocate method) with other
  23 policies such as best-fit.
  24
  25 \section{More information}
  26 \paragraph{}The message on LKML by Matt Mackall introducing SLOB to Linux is mirrored
  27 at this URL: http://lkml.org/lkml/2005/11/1/230
  28
  29 \end{document}