.. mode: -*- rst -*- Free list allocator =================== :Tag: design.mps.freelist :Author: Gareth Rees :Date: 2013-05-18 :Status: incomplete design :Revision: $Id: //info.ravenbrook.com/project/mps/version/1.113/design/freelist.txt#1 $ :Copyright: See section `Copyright and License`_. Introduction ------------ _`.intro`: This document describes the free list allocator for the Memory Pool System. _`.readership`: Any MPS developer. Overview -------- _`.overview`: The free list allocator is an "emergency" allocator. It is intended for use as a fallback allocation strategy in low memory situations, when memory is not available for the control structures needed by other allocators. In these situations the free list allocator ensures that memory is not lost, but with several disadvantages: #. operations on the free list take time proportional to the number of free blocks; #. the data structures are stored in client memory and so are vulnerable to corruption; #. the data structures have poor locality (and thus potentially poor cache performance). When memory becomes available again to allocate control structures, the free lists can be "flushed" back into the more efficient data structures. _`.bg`: The free list allocator was formerly part of the Coalescing Block Structure module (see design.mps.cbs) but it was split into its own module because this makes it: #. simpler (no need to interact with CBS) and thus more maintainable; #. possible to test directly (no need to create a CBS and then force its control pool to run out of memory); and #. usable as a fallback allocator in other pools (not just in pools that use CBS). Definitions ----------- _`.def.range`: A (contiguous) *range* of addresses is a semi-open interval on address space. _`.def.isolated`: A contiguous range is *isolated* with respect to some property it has, if adjacent elements do not have that property. Requirements ------------ _`.req.set`: Must maintain a set of free address ranges. _`.req.add`: Must be able to add free address ranges to the set. _`.req.remove`: Must be able to remove address ranges from the set (in particular, when memory is allocated). _`.req.iterate`: Must support the iteration of all isolated contiguous ranges. _`.req.protocol`: Must detect protocol violations. _`.req.align`: Must support an alignment (the alignment of all addresses specifying ranges) of down to ``sizeof(void *)`` without losing memory. _`.req.zero-overhead`: Must have zero space overhead for the storage of any set of free blocks, so that it can be used to manage memory when no memory can be allocated for control structures. _`.req.source`: This set of requirements is derived from those of the CBS module (see design.mps.cbs.req), except that there is no equivalent of design.mps.cbs.req.fast, and design.mps.cbs.req.small has been replaced with `.req.zero-overhead`_. Interface --------- Types ..... ``typedef struct FreelistStruct *Freelist`` _`.type.freelist`: The type of free lists. The structure ``FreelistStruct`` is declared in the header so that it can be inlined in other structures, but you should not depend on its details. ``typedef Bool (*FreelistIterateMethod)(Bool *deleteReturn, Freelist fl, Range range, void *closureP, Size closureS)`` _`.type.iterate.method`: A callback function that may be passed to ``FreelistIterate()``. It is called for every isolated contiguous range in address order, and with the closure arguments that were originally passed to ``FreelistIterate()``. It must update ``*deleteReturn`` to ``TRUE`` if the range must be deleted from the free lists, or ``FALSE`` if the range must be kept. The function must return ``TRUE`` if the iteration must continue, and ``FALSE`` if the iteration must stop (after possibly deleting the current range). Functions ......... ``Res FreelistInit(Freelist fl, Align alignment)`` _`.function.init`: Initialize the ``Freelist`` structure pointed to by ``fl``. The argument ``alignment`` is the alignment of address ranges to be maintained. An initialised free list contains no address ranges. ``void FreelistFinish(Freelist fl)`` _`.function.finish`: Finish the free list pointed to by ``fl``. ``Res FreelistInsert(Range rangeReturn, Freelist fl, Range range)`` _`.function.insert`: If any part of ``range`` is already in the free list ``fl``, then leave the free list unchanged and return ``ResFAIL``. Otherwise, insert ``range`` into the free list ``fl``; update ``rangeReturn`` to describe the contiguous isolated range containing the inserted range (this may differ from ``range`` if there was coalescence on either side) and return ``ResOK``. ``Res FreelistDelete(Range rangeReturn, Freelist fl, Range range)`` _`.function.delete`: If any part of the range is not in the free list, then leave the free list unchanged and return ``ResFAIL``. Otherwise, remove ``range`` from the free list and update ``rangeReturn`` to describe the contiguous isolated range that formerly contained the deleted range (this may differ from ``range`` if there were fragments left on either side), and return ``ResOK``. ``void FreelistIterate(Freelist fl, FreelistIterateMethod iterate, void *closureP, Size closureS)`` _`.function.iterate`: Iterate all isolated contiguous ranges in the free list ``fl`` in address order, calling ``iterate`` for each one. See ``FreelistIterateMethod`` for details. ``Bool FreelistFindFirst(Range rangeReturn, Range oldRangeReturn, Freelist fl, Size size, FindDelete findDelete)`` _`.function.find.first`: Locate the first isolated contiguous range in address order, within the free list ``fl``, of at least ``size`` bytes, update ``rangeReturn`` to that range, and return ``TRUE``. If there is no such continuous range, return ``FALSE``. In addition, optionally delete the found range from the free list, depending on the ``findDelete`` argument. This saves a separate call to ``FreelistDelete()``, and uses the knowledge of exactly where we found the range. The value of ``findDelete`` must come from this enumeration:: enum { FindDeleteNONE, /* don't delete after finding */ FindDeleteLOW, /* delete size bytes from low end of block */ FindDeleteHIGH, /* delete size bytes from high end of block */ FindDeleteENTIRE /* delete entire range */ }; The original contiguous isolated range in which the range was found is returned via the ``oldRangeReturn`` argument. (If ``findDelete`` is ``FindDeleteNONE`` or ``FindDeleteENTIRE``, then this will be identical to the range returned via the ``rangeReturn`` argument.) ``Bool FreelistFindLast(Range rangeReturn, Range oldRangeReturn, Freelist fl, Size size, FindDelete findDelete)`` _`.function.find.last`: Like ``FreelistFindFirst()``, except that it finds the last block in address order. ``Bool FreelistFindLargest(Range rangeReturn, Range oldRangeReturn, Freelist fl, Size, size, FindDelete findDelete)`` _`.function.find.largest`: Locate the largest block within the free list ``fl``, and if that block is at least as big as ``size``, return its range via the ``rangeReturn`` argument, and return ``TRUE``. If there are no blocks in the free list at least as large as ``size``, return ``FALSE``. Pass 0 for ``size`` if you want the largest block unconditionally. Like ``FreelistFindFirst()``, optionally delete the range from the free list. (Always the whole range: specifying ``FindDeleteLOW`` or ``FindDeleteHIGH`` has the same effect as ``FindDeleteENTIRE``). ``void FreelistFlushToCBS(Freelist fl, CBS cbs)`` Remove free address ranges from the free list ``fl`` and add them to the Coalescing Block Structure ``cbs``. Continue until a call to ``CBSInsert()`` fails, or until the free list is empty, whichever happens first. ``Res FreelistDescribe(Freelist fl, mps_lib_FILE *stream)`` _`.function.describe`: Print a textual representation of the free list ``fl`` to the given stream, indicating the contiguous ranges in order. It is provided for debugging purposes only. Implementation -------------- _`.impl.list`: The isolated contiguous free address ranges are kept on an address-ordered singly linked free list. (As in traditional ``malloc()`` implementations.) _`.impl.block`: If the free address range is large enough to contain an inline block descriptor consisting of two pointers, then the two pointers stored are to the next free range in address order (or ``NULL`` if there are no more ranges), and to the limit of current free address range, in that order. _`.impl.grain`: Otherwise, the free address range must be large enough to contain a single pointer. The pointer stored is to the next free range in address order, or ``NULL`` if there are no more ranges. _`.impl.tag`: Grains and blocks are distinguished by a one-bit tag in the low bit of the first word (the one containing the pointer to the next range). Grains have this bit set; blocks have this bit reset. _`.impl.invariant`: The ranges stored in the free list are *isolated*: no two ranges are adjacent or overlapping. _`.impl.merge`: When a free address range is added to the free list, it is merged with adjacent ranges so as to maintain `.impl.invariant`_. _`.impl.rule.break`: The use of ``NULL`` to mark the end of the list violates the rule that exceptional values should not be used to distinguish exeptional situations. This infraction allows the implementation to meet `.req.zero-overhead`_. (There are other ways to do this, such as using another tag to indicate the last block in the list, but these would be more complicated.) Opportunities for improvement ----------------------------- _`.improve.length`: When iterating over the list, we could check that the number of elements visited in the course of the iteration does not exceed the recorded size of the list. _`.improve.maxsize`: We could maintain the maximum size of any range on the list, and use that to make an early exit from ``FreelistFindLargest()``. It's not clear that this would actually be an improvement. Document History ---------------- - 2013-05-18 GDR_ Initial draft based on CBS "emergency block" design. .. _GDR: http://www.ravenbrook.com/consultants/gdr/ Copyright and License --------------------- Copyright © 2013-2014 Ravenbrook Limited. All rights reserved. . This is an open source license. Contact Ravenbrook for commercial licensing options. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: #. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. #. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. #. Redistributions in any form must be accompanied by information on how to obtain complete source code for this software and any accompanying software that uses this software. The source code must either be included in the distribution or be available for no more than the cost of distribution plus a nominal fee, and must be freely redistributable under reasonable conditions. For an executable file, complete source code means the source code for all modules it contains. It does not include source code for modules or files that typically accompany the major components of the operating system on which the executable file runs. **This software is provided by the copyright holders and contributors "as is" and any express or implied warranties, including, but not limited to, the implied warranties of merchantability, fitness for a particular purpose, or non-infringement, are disclaimed. In no event shall the copyright holders and contributors be liable for any direct, indirect, incidental, special, exemplary, or consequential damages (including, but not limited to, procurement of substitute goods or services; loss of use, data, or profits; or business interruption) however caused and on any theory of liability, whether in contract, strict liability, or tort (including negligence or otherwise) arising in any way out of the use of this software, even if advised of the possibility of such damage.**