disk_allocator.cpp

Go to the documentation of this file.

/***************************************************************************
 * lib/mng/disk_allocator.cpp
 *
 * Part of the STXXL. See http://stxxl.sourceforge.net
 *
 * Copyright (C) 2002 Roman Dementiev <[email protected]>
 * Copyright (C) 2008, 2010 Andreas Beckmann <[email protected]>
 *
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 **************************************************************************/

#include <stxxl/bits/common/error_handling.h>
#include <stxxl/bits/common/exceptions.h>
#include <stxxl/bits/common/types.h>
#include <stxxl/bits/mng/disk_allocator.h>
#include <stxxl/bits/namespace.h>
#include <stxxl/bits/verbose.h>

#include <cassert>
#include <map>
#include <ostream>
#include <utility>

STXXL_BEGIN_NAMESPACE

void disk_allocator::dump() const
{
 int64 total = 0;
 sortseq::const_iterator cur = free_space.begin();
 STXXL_ERRMSG("Free regions dump:");
 for ( ; cur != free_space.end(); ++cur)
 {
 STXXL_ERRMSG("Free chunk: begin: " << (cur->first) << " size: " << (cur->second));
 total += cur->second;
 }
 STXXL_ERRMSG("Total bytes: " << total);
}

void disk_allocator::deallocation_error(
 stxxl::int64 block_pos, stxxl::int64 block_size,
 const sortseq::iterator& pred, const sortseq::iterator& succ) const
{
 STXXL_ERRMSG("Error deallocating block at " << block_pos << " size " << block_size);
 STXXL_ERRMSG(((pred == succ) ? "pred==succ" : "pred!=succ"));
 if (pred == free_space.end()) {
 STXXL_ERRMSG("pred==free_space.end()");
 } else {
 if (pred == free_space.begin())
 STXXL_ERRMSG("pred==free_space.begin()");
 STXXL_ERRMSG("pred: begin=" << pred->first << " size=" << pred->second);
 }
 if (succ == free_space.end()) {
 STXXL_ERRMSG("succ==free_space.end()");
 } else {
 if (succ == free_space.begin())
 STXXL_ERRMSG("succ==free_space.begin()");
 STXXL_ERRMSG("succ: begin=" << succ->first << " size=" << succ->second);
 }
 dump();
}

void disk_allocator::add_free_region(stxxl::int64 block_pos, stxxl::int64 block_size)
{
 //assert(block_size);
 //dump();
 STXXL_VERBOSE2("Deallocating a block with size: " << block_size << " position: " << block_pos);
 stxxl::int64 region_pos = block_pos;
 stxxl::int64 region_size = block_size;
 if (!free_space.empty())
 {
 sortseq::iterator succ = free_space.upper_bound(region_pos);
 sortseq::iterator pred = succ;
 if (pred != free_space.begin())
 pred--;
 if (pred != free_space.end())
 {
 if (pred->first <= region_pos && pred->first + pred->second > region_pos)
 {
 STXXL_THROW2(bad_ext_alloc, "disk_allocator::check_corruption", "Error: double deallocation of external memory, trying to deallocate region " << region_pos << " + " << region_size << " in empty space [" << pred->first << " + " << pred->second << "]");
 }
 }
 if (succ != free_space.end())
 {
 if (region_pos <= succ->first && region_pos + region_size > succ->first)
 {
 STXXL_THROW2(bad_ext_alloc, "disk_allocator::check_corruption", "Error: double deallocation of external memory, trying to deallocate region " << region_pos << " + " << region_size << " which overlaps empty space [" << succ->first << " + " << succ->second << "]");
 }
 }
 if (succ == free_space.end())
 {
 if (pred == free_space.end())
 {
 deallocation_error(block_pos, block_size, pred, succ);
 assert(pred != free_space.end());
 }
 if ((*pred).first + (*pred).second == region_pos)
 {
 // coalesce with predecessor
 region_size += (*pred).second;
 region_pos = (*pred).first;
 free_space.erase(pred);
 }
 }
 else
 {
 if (free_space.size() > 1)
 {
#if 0
 if (pred == succ)
 {
 deallocation_error(block_pos, block_size, pred, succ);
 assert(pred != succ);
 }
#endif
 bool succ_is_not_the_first = (succ != free_space.begin());
 if ((*succ).first == region_pos + region_size)
 {
 // coalesce with successor
 region_size += (*succ).second;
 free_space.erase(succ);
 //-tb: set succ to pred afterwards due to iterator invalidation
 succ = pred;
 }
 if (succ_is_not_the_first)
 {
 if (pred == free_space.end())
 {
 deallocation_error(block_pos, block_size, pred, succ);
 assert(pred != free_space.end());
 }
 if ((*pred).first + (*pred).second == region_pos)
 {
 // coalesce with predecessor
 region_size += (*pred).second;
 region_pos = (*pred).first;
 free_space.erase(pred);
 }
 }
 }
 else
 {
 if ((*succ).first == region_pos + region_size)
 {
 // coalesce with successor
 region_size += (*succ).second;
 free_space.erase(succ);
 }
 }
 }
 }

 free_space[region_pos] = region_size;
 free_bytes += block_size;

 //dump();
}

STXXL_END_NAMESPACE
// vim: et:ts=4:sw=4