Thrill  0.1
disk_block_allocator.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * foxxll/mng/disk_block_allocator.cpp
3  *
4  * Part of FOXXLL. See http://foxxll.org
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 
14 #include <cassert>
15 #include <map>
16 #include <ostream>
17 #include <utility>
18 
21 #include <foxxll/common/types.hpp>
23 
24 namespace foxxll {
25 
27 {
28  uint64_t total = 0;
29  space_map_type::const_iterator cur = free_space_.begin();
30  TLX_LOG1 << "Free regions dump:";
31  for ( ; cur != free_space_.end(); ++cur)
32  {
33  TLX_LOG1 << "Free chunk: begin: " << (cur->first) << " size: " << (cur->second);
34  total += cur->second;
35  }
36  TLX_LOG1 << "Total bytes: " << total;
37 }
38 
40  uint64_t block_pos, uint64_t block_size,
41  const space_map_type::iterator& pred,
42  const space_map_type::iterator& succ) const
43 {
44  TLX_LOG1 << "Error deallocating block at " << block_pos << " size " << block_size;
45  TLX_LOG1 << ((pred == succ) ? "pred==succ" : "pred!=succ");
46  if (pred == free_space_.end()) {
47  TLX_LOG1 << "pred==free_space_.end()";
48  }
49  else {
50  if (pred == free_space_.begin())
51  TLX_LOG1 << "pred==free_space_.begin()";
52  TLX_LOG1 << "pred: begin=" << pred->first << " size=" << pred->second;
53  }
54  if (succ == free_space_.end()) {
55  TLX_LOG1 << "succ==free_space_.end()";
56  }
57  else {
58  if (succ == free_space_.begin())
59  TLX_LOG1 << "succ==free_space_.begin()";
60  TLX_LOG1 << "succ: begin=" << succ->first << " size=" << succ->second;
61  }
62  dump();
63 }
64 
65 void disk_block_allocator::add_free_region(uint64_t block_pos, uint64_t block_size)
66 {
67  TLX_LOG << "Deallocating a block with size: " << block_size << " position: " << block_pos;
68  uint64_t region_pos = block_pos;
69  uint64_t region_size = block_size;
70 
71  // First we try to find adjacent free slots and if successful we coalesce them
72  // During this procedure we also identify double-frees and similar issues
73  if (!free_space_.empty())
74  {
75  auto succ = free_space_.upper_bound(region_pos);
76  auto pred = succ;
77 
78  if (pred != free_space_.begin())
79  pred--;
80 
81  if (pred != free_space_.end()) {
82  if (pred->first <= region_pos && (pred->first + pred->second) > region_pos) {
84  bad_ext_alloc, "disk_block_allocator::check_corruption",
85  "Error: double deallocation of external memory, trying to deallocate "
86  "region " << region_pos << " + " << region_size << " in empty space"
87  "[" << pred->first << " + " << pred->second << "]"
88  );
89  }
90  }
91 
92  if (succ != free_space_.end()) {
93  if (region_pos <= succ->first && (region_pos + region_size) > succ->first) {
95  bad_ext_alloc, "disk_block_allocator::check_corruption",
96  "Error: double deallocation of external memory, trying to deallocate "
97  "region " << region_pos << " + " << region_size << " which overlaps empty space "
98  "[" << succ->first << " + " << succ->second << "]"
99  );
100  }
101  }
102 
103  if (succ == free_space_.end()) {
104  if (pred == free_space_.end()) {
105  deallocation_error(block_pos, block_size, pred, succ);
106  assert(false);
107  }
108  else if ((*pred).first + (*pred).second == region_pos) {
109  // coalesce with predecessor
110  region_size += (*pred).second;
111  region_pos = (*pred).first;
112  free_space_.erase(pred);
113  }
114  }
115  else {
116  if (free_space_.size() > 1) {
117  // check it now, as succ may change!
118  const bool succ_is_not_the_first = (succ != free_space_.begin());
119 
120  if ((*succ).first == region_pos + region_size) {
121  // coalesce with successor
122  region_size += (*succ).second;
123  free_space_.erase(succ);
124  if (succ_is_not_the_first)
125  succ = pred;
126  }
127 
128  if (succ_is_not_the_first) {
129  if (pred == free_space_.end()) {
130  deallocation_error(block_pos, block_size, pred, succ);
131  assert(false);
132  }
133  else if ((*pred).first + (*pred).second == region_pos) {
134  // coalesce with predecessor
135  region_size += (*pred).second;
136  region_pos = (*pred).first;
137  free_space_.erase(pred);
138  }
139  }
140  }
141  else {
142  if ((*succ).first == region_pos + region_size) {
143  // coalesce with successor
144  region_size += (*succ).second;
145  free_space_.erase(succ);
146  }
147  }
148  }
149  }
150 
151  free_space_[region_pos] = region_size;
152  free_bytes_ += block_size;
153 }
154 
155 } // namespace foxxll
156 
157 /**************************************************************************/
void add_free_region(uint64_t block_pos, uint64_t block_size)
#define FOXXLL_THROW2(exception_type, location, error_message)
Throws exception_type with "Error in [location] : [error_message]".
void deallocation_error(uint64_t block_pos, uint64_t block_size, const space_map_type::iterator &pred, const space_map_type::iterator &succ) const
FOXXLL library namespace
space_map_type free_space_
map of free space as places
#define TLX_LOG1
Definition: core.hpp:145
#define TLX_LOG
Default logging method: output if the local debug variable is true.
Definition: core.hpp:141