1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> 2<html> 3<head> 4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5<title>Memory allocation algorithms</title> 6<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> 7<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 8<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> 9<link rel="up" href="../interprocess.html" title="Chapter 18. Boost.Interprocess"> 10<link rel="prev" href="allocators_containers.html" title="Allocators, containers and memory allocation algorithms"> 11<link rel="next" href="streams.html" title="Direct iostream formatting: vectorstream and bufferstream"> 12</head> 13<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 14<table cellpadding="2" width="100%"><tr> 15<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> 16<td align="center"><a href="../../../index.html">Home</a></td> 17<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> 18<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 19<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 20<td align="center"><a href="../../../more/index.htm">More</a></td> 21</tr></table> 22<hr> 23<div class="spirit-nav"> 24<a accesskey="p" href="allocators_containers.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../interprocess.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="streams.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 25</div> 26<div class="section"> 27<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 28<a name="interprocess.memory_algorithms"></a><a class="link" href="memory_algorithms.html" title="Memory allocation algorithms">Memory allocation algorithms</a> 29</h2></div></div></div> 30<div class="toc"><dl class="toc"> 31<dt><span class="section"><a href="memory_algorithms.html#interprocess.memory_algorithms.simple_seq_fit">simple_seq_fit: 32 A simple shared memory management algorithm</a></span></dt> 33<dt><span class="section"><a href="memory_algorithms.html#interprocess.memory_algorithms.rbtree_best_fit">rbtree_best_fit: 34 Best-fit logarithmic-time complexity allocation</a></span></dt> 35</dl></div> 36<div class="section"> 37<div class="titlepage"><div><div><h3 class="title"> 38<a name="interprocess.memory_algorithms.simple_seq_fit"></a><a class="link" href="memory_algorithms.html#interprocess.memory_algorithms.simple_seq_fit" title="simple_seq_fit: A simple shared memory management algorithm">simple_seq_fit: 39 A simple shared memory management algorithm</a> 40</h3></div></div></div> 41<p> 42 The algorithm is a variation of sequential fit using singly linked list of 43 free memory buffers. The algorithm is based on the article about shared memory 44 titled <a href="http://home.earthlink.net/~joshwalker1/writing/SharedMemory.html" target="_top"><span class="emphasis"><em>"Taming 45 Shared Memory"</em></span> </a>. The algorithm is as follows: 46 </p> 47<p> 48 The shared memory is divided in blocks of free shared memory, each one with 49 some control data and several bytes of memory ready to be used. The control 50 data contains a pointer (in our case offset_ptr) to the next free block and 51 the size of the block. The allocator consists of a singly linked list of 52 free blocks, ordered by address. The last block, points always to the first 53 block: 54 </p> 55<pre class="programlisting"><span class="identifier">simple_seq_fit</span> <span class="identifier">memory</span> <span class="identifier">layout</span><span class="special">:</span> 56 57 <span class="identifier">main</span> <span class="identifier">extra</span> <span class="identifier">allocated</span> <span class="identifier">free_block_1</span> <span class="identifier">allocated</span> <span class="identifier">free_block_2</span> <span class="identifier">allocated</span> <span class="identifier">free_block_3</span> 58 <span class="identifier">header</span> <span class="identifier">header</span> <span class="identifier">block</span> <span class="identifier">ctrl</span> <span class="identifier">usr</span> <span class="identifier">block</span> <span class="identifier">ctrl</span> <span class="identifier">usr</span> <span class="identifier">block</span> <span class="identifier">ctrl</span> <span class="identifier">usr</span> 59 <span class="identifier">_________</span> <span class="identifier">_____</span> <span class="identifier">_________</span> <span class="identifier">_______________</span> <span class="identifier">_________</span> <span class="identifier">_______________</span> <span class="identifier">_________</span> <span class="identifier">_______________</span> 60 <span class="special">|</span> <span class="special">||</span> <span class="special">||</span> <span class="special">||</span> <span class="special">|</span> <span class="special">||</span> <span class="special">||</span> <span class="special">|</span> <span class="special">||</span> <span class="special">||</span> <span class="special">|</span> <span class="special">|</span> 61 <span class="special">|</span><span class="identifier">free</span><span class="special">|</span><span class="identifier">ctrl</span><span class="special">||</span><span class="identifier">extra</span><span class="special">||</span> <span class="special">||</span><span class="identifier">next</span><span class="special">|</span><span class="identifier">size</span><span class="special">|</span> <span class="identifier">mem</span> <span class="special">||</span> <span class="special">||</span><span class="identifier">next</span><span class="special">|</span><span class="identifier">size</span><span class="special">|</span> <span class="identifier">mem</span> <span class="special">||</span> <span class="special">||</span><span class="identifier">next</span><span class="special">|</span><span class="identifier">size</span><span class="special">|</span> <span class="identifier">mem</span> <span class="special">|</span> 62 <span class="special">|</span><span class="identifier">_________</span><span class="special">||</span><span class="identifier">_____</span><span class="special">||</span><span class="identifier">_________</span><span class="special">||</span><span class="identifier">_________</span><span class="special">|</span><span class="identifier">_____</span><span class="special">||</span><span class="identifier">_________</span><span class="special">||</span><span class="identifier">_________</span><span class="special">|</span><span class="identifier">_____</span><span class="special">||</span><span class="identifier">_________</span><span class="special">||</span><span class="identifier">_________</span><span class="special">|</span><span class="identifier">_____</span><span class="special">|</span> 63 <span class="special">|</span> <span class="special">|</span> <span class="special">|</span> <span class="special">|</span> <span class="special">|</span> <span class="special">|</span> <span class="special">|</span> 64 <span class="special">|</span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">|</span> <span class="special">|</span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">|</span> <span class="special">|</span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">></span><span class="identifier">_</span><span class="special">|</span> <span class="special">|</span> 65 <span class="special">|</span> <span class="special">|</span> 66 <span class="special">|</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">_</span><span class="special"><</span><span class="identifier">__</span><span class="special">|</span> 67</pre> 68<p> 69 When a user requests N bytes of memory, the allocator traverses the free 70 block list looking for a block large enough. If the "mem" part 71 of the block has the same size as the requested memory, we erase the block 72 from the list and return a pointer to the "mem" part of the block. 73 If the "mem" part size is bigger than needed, we split the block 74 in two blocks, one of the requested size and the other with remaining size. 75 Now, we take the block with the exact size, erase it from list and give it 76 to the user. 77 </p> 78<p> 79 When the user deallocates a block, we traverse the list (remember that the 80 list is ordered), and search its place depending on the block address. Once 81 found, we try to merge the block with adjacent blocks if possible. 82 </p> 83<p> 84 To ease implementation, the size of the free memory block is measured in 85 multiples of "basic_size" bytes. The basic size will be the size 86 of the control block aligned to machine most restrictive alignment. 87 </p> 88<p> 89 This algorithm is a low size overhead algorithm suitable for simple allocation 90 schemes. This algorithm should only be used when size is a major concern, 91 because the performance of this algorithm suffers when the memory is fragmented. 92 This algorithm has linear allocation and deallocation time, so when the number 93 of allocations is high, the user should use a more performance-friendly algorithm. 94 </p> 95<p> 96 In most 32 systems, with 8 byte alignment, "basic_size" is 8 bytes. 97 This means that an allocation request of 1 byte leads to the creation of 98 a 16 byte block, where 8 bytes are available to the user. The allocation 99 of 8 bytes leads also to the same 16 byte block. 100 </p> 101</div> 102<div class="section"> 103<div class="titlepage"><div><div><h3 class="title"> 104<a name="interprocess.memory_algorithms.rbtree_best_fit"></a><a class="link" href="memory_algorithms.html#interprocess.memory_algorithms.rbtree_best_fit" title="rbtree_best_fit: Best-fit logarithmic-time complexity allocation">rbtree_best_fit: 105 Best-fit logarithmic-time complexity allocation</a> 106</h3></div></div></div> 107<p> 108 This algorithm is an advanced algorithm using red-black trees to sort the 109 free portions of the memory segment by size. This allows logarithmic complexity 110 allocation. Apart from this, a doubly-linked list of all portions of memory 111 (free and allocated) is maintained to allow constant-time access to previous 112 and next blocks when doing merging operations. 113 </p> 114<p> 115 The data used to create the red-black tree of free nodes is overwritten by 116 the user since it's no longer used once the memory is allocated. This maintains 117 the memory size overhead down to the doubly linked list overhead, which is 118 pretty small (two pointers). Basically this is the scheme: 119 </p> 120<pre class="programlisting"><span class="identifier">rbtree_best_fit</span> <span class="identifier">memory</span> <span class="identifier">layout</span><span class="special">:</span> 121 122 <span class="identifier">main</span> <span class="identifier">allocated</span> <span class="identifier">block</span> <span class="identifier">free</span> <span class="identifier">block</span> <span class="identifier">allocated</span> <span class="identifier">block</span> <span class="identifier">free</span> <span class="identifier">block</span> 123 <span class="identifier">header</span> 124 <span class="identifier">_______________</span> <span class="identifier">_______________</span> <span class="identifier">_________________________________</span> <span class="identifier">_______________</span> <span class="identifier">_________________________________</span> 125 <span class="special">|</span> <span class="special">||</span> <span class="special">|</span> <span class="special">||</span> <span class="special">|</span> <span class="special">|</span> <span class="special">||</span> <span class="special">|</span> <span class="special">||</span> <span class="special">|</span> <span class="special">|</span> <span class="special">|</span> 126 <span class="special">|</span> <span class="identifier">main</span> <span class="identifier">header</span> <span class="special">||</span><span class="identifier">next</span><span class="special">|</span><span class="identifier">prev</span><span class="special">|</span> <span class="identifier">mem</span> <span class="special">||</span><span class="identifier">next</span><span class="special">|</span><span class="identifier">prev</span><span class="special">|</span><span class="identifier">left</span><span class="special">|</span><span class="identifier">right</span><span class="special">|</span><span class="identifier">parent</span><span class="special">|</span> <span class="identifier">mem</span> <span class="special">||</span><span class="identifier">next</span><span class="special">|</span><span class="identifier">prev</span><span class="special">|</span> <span class="identifier">mem</span> <span class="special">||</span><span class="identifier">next</span><span class="special">|</span><span class="identifier">prev</span><span class="special">|</span><span class="identifier">left</span><span class="special">|</span><span class="identifier">right</span><span class="special">|</span><span class="identifier">parent</span><span class="special">|</span> <span class="identifier">mem</span> <span class="special">|</span> 127 <span class="special">|</span><span class="identifier">_______________</span><span class="special">||</span><span class="identifier">_________</span><span class="special">|</span><span class="identifier">_____</span><span class="special">||</span><span class="identifier">_________</span><span class="special">|</span><span class="identifier">_________________</span><span class="special">|</span><span class="identifier">_____</span><span class="special">||</span><span class="identifier">_________</span><span class="special">|</span><span class="identifier">_____</span><span class="special">||</span><span class="identifier">_________</span><span class="special">|</span><span class="identifier">_________________</span><span class="special">|</span><span class="identifier">_____</span><span class="special">|</span> 128</pre> 129<p> 130 This allocation algorithm is pretty fast and scales well with big shared 131 memory segments and big number of allocations. To form a block a minimum 132 memory size is needed: the sum of the doubly linked list and the red-black 133 tree control data. The size of a block is measured in multiples of the most 134 restrictive alignment value. 135 </p> 136<p> 137 In most 32 systems with 8 byte alignment the minimum size of a block is 24 138 byte. When a block is allocated the control data related to the red black 139 tree is overwritten by the user (because it's only needed for free blocks). 140 </p> 141<p> 142 In those systems a 1 byte allocation request means that: 143 </p> 144<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 145<li class="listitem"> 146 24 bytes of memory from the segment are used to form a block. 147 </li> 148<li class="listitem"> 149 16 bytes of them are usable for the user. 150 </li> 151</ul></div> 152<p> 153 For really small allocations (<= 8 bytes), this algorithm wastes more 154 memory than the simple sequential fit algorithm (8 bytes more). For allocations 155 bigger than 8 bytes the memory overhead is exactly the same. This is the 156 default allocation algorithm in <span class="bold"><strong>Boost.Interprocess</strong></span> 157 managed memory segments. 158 </p> 159</div> 160</div> 161<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 162<td align="left"></td> 163<td align="right"><div class="copyright-footer">Copyright © 2005-2015 Ion Gaztanaga<p> 164 Distributed under the Boost Software License, Version 1.0. (See accompanying 165 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 166 </p> 167</div></td> 168</tr></table> 169<hr> 170<div class="spirit-nav"> 171<a accesskey="p" href="allocators_containers.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../interprocess.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="streams.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 172</div> 173</body> 174</html> 175
