STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
disk_allocator.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * lib/mng/disk_allocator.cpp
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2002 Roman Dementiev <[email protected]>
7  * Copyright (C) 2008, 2010 Andreas Beckmann <[email protected]>
8  *
9  * Distributed under the Boost Software License, Version 1.0.
10  * (See accompanying file LICENSE_1_0.txt or copy at
11  * http://www.boost.org/LICENSE_1_0.txt)
12  **************************************************************************/
13 
18 #include <stxxl/bits/namespace.h>
19 #include <stxxl/bits/verbose.h>
20 
21 #include <cassert>
22 #include <map>
23 #include <ostream>
24 #include <utility>
25 
27 
28 void disk_allocator::dump() const
29 {
30  int64 total = 0;
31  sortseq::const_iterator cur = free_space.begin();
32  STXXL_ERRMSG("Free regions dump:");
33  for ( ; cur != free_space.end(); ++cur)
34  {
35  STXXL_ERRMSG("Free chunk: begin: " << (cur->first) << " size: " << (cur->second));
36  total += cur->second;
37  }
38  STXXL_ERRMSG("Total bytes: " << total);
39 }
40 
41 void disk_allocator::deallocation_error(
42  stxxl::int64 block_pos, stxxl::int64 block_size,
43  const sortseq::iterator& pred, const sortseq::iterator& succ) const
44 {
45  STXXL_ERRMSG("Error deallocating block at " << block_pos << " size " << block_size);
46  STXXL_ERRMSG(((pred == succ) ? "pred==succ" : "pred!=succ"));
47  if (pred == free_space.end()) {
48  STXXL_ERRMSG("pred==free_space.end()");
49  }
50  else {
51  if (pred == free_space.begin())
52  STXXL_ERRMSG("pred==free_space.begin()");
53  STXXL_ERRMSG("pred: begin=" << pred->first << " size=" << pred->second);
54  }
55  if (succ == free_space.end()) {
56  STXXL_ERRMSG("succ==free_space.end()");
57  }
58  else {
59  if (succ == free_space.begin())
60  STXXL_ERRMSG("succ==free_space.begin()");
61  STXXL_ERRMSG("succ: begin=" << succ->first << " size=" << succ->second);
62  }
63  dump();
64 }
65 
66 void disk_allocator::add_free_region(stxxl::int64 block_pos, stxxl::int64 block_size)
67 {
68  //assert(block_size);
69  //dump();
70  STXXL_VERBOSE2("Deallocating a block with size: " << block_size << " position: " << block_pos);
71  stxxl::int64 region_pos = block_pos;
72  stxxl::int64 region_size = block_size;
73  if (!free_space.empty())
74  {
75  sortseq::iterator succ = free_space.upper_bound(region_pos);
76  sortseq::iterator pred = succ;
77  if (pred != free_space.begin())
78  pred--;
79  if (pred != free_space.end())
80  {
81  if (pred->first <= region_pos && pred->first + pred->second > region_pos)
82  {
83  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 << "]");
84  }
85  }
86  if (succ != free_space.end())
87  {
88  if (region_pos <= succ->first && region_pos + region_size > succ->first)
89  {
90  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 << "]");
91  }
92  }
93  if (succ == free_space.end())
94  {
95  if (pred == free_space.end())
96  {
97  deallocation_error(block_pos, block_size, pred, succ);
98  assert(pred != free_space.end());
99  }
100  if ((*pred).first + (*pred).second == region_pos)
101  {
102  // coalesce with predecessor
103  region_size += (*pred).second;
104  region_pos = (*pred).first;
105  free_space.erase(pred);
106  }
107  }
108  else
109  {
110  if (free_space.size() > 1)
111  {
112 #if 0
113  if (pred == succ)
114  {
115  deallocation_error(block_pos, block_size, pred, succ);
116  assert(pred != succ);
117  }
118 #endif
119  bool succ_is_not_the_first = (succ != free_space.begin());
120  if ((*succ).first == region_pos + region_size)
121  {
122  // coalesce with successor
123  region_size += (*succ).second;
124  free_space.erase(succ);
125  //-tb: set succ to pred afterwards due to iterator invalidation
126  succ = pred;
127  }
128  if (succ_is_not_the_first)
129  {
130  if (pred == free_space.end())
131  {
132  deallocation_error(block_pos, block_size, pred, succ);
133  assert(pred != free_space.end());
134  }
135  if ((*pred).first + (*pred).second == region_pos)
136  {
137  // coalesce with predecessor
138  region_size += (*pred).second;
139  region_pos = (*pred).first;
140  free_space.erase(pred);
141  }
142  }
143  }
144  else
145  {
146  if ((*succ).first == region_pos + region_size)
147  {
148  // coalesce with successor
149  region_size += (*succ).second;
150  free_space.erase(succ);
151  }
152  }
153  }
154  }
155 
156  free_space[region_pos] = region_size;
157  free_bytes += block_size;
158 
159  //dump();
160 }
161 
163 // vim: et:ts=4:sw=4
long long int int64
Definition: types.h:38
#define STXXL_VERBOSE2(x)
Definition: verbose.h:121
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
#define STXXL_THROW2(exception_type, location, error_message)
Throws exception_type with &quot;Error in [location] : [error_message]&quot;.
static long long total
#define STXXL_ERRMSG(x)
Definition: verbose.h:94
#define STXXL_END_NAMESPACE
Definition: namespace.h:17