STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
write_pool.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/mng/write_pool.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2003-2004 Roman Dementiev <[email protected]>
7  * Copyright (C) 2009 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 #ifndef STXXL_MNG_WRITE_POOL_HEADER
15 #define STXXL_MNG_WRITE_POOL_HEADER
16 
17 #include <list>
18 #include <stxxl/bits/config.h>
19 #include <stxxl/bits/noncopyable.h>
20 #include <stxxl/bits/deprecated.h>
22 
23 #define STXXL_VERBOSE_WPOOL(msg) STXXL_VERBOSE1("write_pool[" << static_cast<void*>(this) << "]" << msg)
24 
26 
27 //! \addtogroup schedlayer
28 //! \{
29 
30 //! Implements dynamically resizable buffered writing pool.
31 template <class BlockType>
32 class write_pool : private noncopyable
33 {
34 public:
35  typedef BlockType block_type;
36  typedef typename block_type::bid_type bid_type;
37 
38  // a hack to make wait_any work with busy_entry type
39  struct busy_entry
40  {
44 
45  busy_entry() : block(NULL) { }
46  busy_entry(const busy_entry& a) : block(a.block), req(a.req), bid(a.bid) { }
48  : block(bl), req(r), bid(bi) { }
49 
50  operator request_ptr () { return req; }
51  };
52  typedef typename std::list<block_type*>::iterator free_blocks_iterator;
53  typedef typename std::list<busy_entry>::iterator busy_blocks_iterator;
54 
55 protected:
56  // contains free write blocks
57  std::list<block_type*> free_blocks;
58  // blocks that are in writing
59  std::list<busy_entry> busy_blocks;
60 
61 public:
62  //! Constructs pool.
63  //! \param init_size initial number of blocks in the pool
64  explicit write_pool(unsigned_type init_size = 1)
65  {
66  for (unsigned_type i = 0; i < init_size; ++i)
67  {
68  free_blocks.push_back(new block_type);
69  STXXL_VERBOSE_WPOOL(" create block=" << free_blocks.back());
70  }
71  }
72 
73  void swap(write_pool& obj)
74  {
75  std::swap(free_blocks, obj.free_blocks);
76  std::swap(busy_blocks, obj.busy_blocks);
77  }
78 
79  //! Waits for completion of all ongoing write requests and frees memory.
81  {
82  STXXL_VERBOSE_WPOOL("::~write_pool free_blocks.size()=" << free_blocks.size() <<
83  " busy_blocks.size()=" << busy_blocks.size());
84  while (!free_blocks.empty())
85  {
86  STXXL_VERBOSE_WPOOL(" delete free block=" << free_blocks.back());
87  delete free_blocks.back();
88  free_blocks.pop_back();
89  }
90 
91  try
92  {
93  for (busy_blocks_iterator i2 = busy_blocks.begin(); i2 != busy_blocks.end(); ++i2)
94  {
95  i2->req->wait();
96  if (free_blocks.empty())
97  STXXL_VERBOSE_WPOOL(" delete busy block=(empty)");
98  else
99  STXXL_VERBOSE_WPOOL(" delete busy block=" << free_blocks.back());
100  delete i2->block;
101  }
102  }
103  catch (...)
104  { }
105  }
106 
107  //! Returns number of owned blocks.
108  unsigned_type size() const { return free_blocks.size() + busy_blocks.size(); }
109 
110  //! Passes a block to the pool for writing.
111  //! \param block block to write. Ownership of the block goes to the pool.
112  //! \c block must be allocated dynamically with using \c new .
113  //! \param bid location, where to write
114  //! \warning \c block must be allocated dynamically with using \c new .
115  //! \return request object of the write operation
117  {
118  STXXL_VERBOSE_WPOOL("::write: " << block << " @ " << bid);
119  for (busy_blocks_iterator i2 = busy_blocks.begin(); i2 != busy_blocks.end(); ++i2)
120  {
121  if (i2->bid == bid) {
122  assert(i2->block != block);
123  STXXL_VERBOSE_WPOOL("WAW dependency");
124  // try to cancel the obsolete request
125  i2->req->cancel();
126  // invalidate the bid of the stale write request,
127  // prevents prefetch_pool from stealing a stale block
128  i2->bid.storage = 0;
129  }
130  }
131  request_ptr result = block->write(bid);
132  busy_blocks.push_back(busy_entry(block, result, bid));
133  block = NULL; // prevent caller from using the block any further
134  return result;
135  }
136 
137  //! Take out a block from the pool.
138  //! \return pointer to the block. Ownership of the block goes to the caller.
140  {
141  STXXL_ASSERT(size() > 0);
142  if (!free_blocks.empty())
143  {
144  block_type* p = free_blocks.back();
145  STXXL_VERBOSE_WPOOL("::steal : " << free_blocks.size() << " free blocks available, serve block=" << p);
146  free_blocks.pop_back();
147  return p;
148  }
149  STXXL_VERBOSE_WPOOL("::steal : all " << busy_blocks.size() << " are busy");
150  busy_blocks_iterator completed = wait_any(busy_blocks.begin(), busy_blocks.end());
151  assert(completed != busy_blocks.end()); // we got something reasonable from wait_any
152  assert(completed->req->poll()); // and it is *really* completed
153  block_type* p = completed->block;
154  busy_blocks.erase(completed);
155  check_all_busy(); // for debug
156  STXXL_VERBOSE_WPOOL(" serve block=" << p);
157  return p;
158  }
159 
160  // deprecated name for the steal()
162  {
163  return steal();
164  }
165 
166  //! Resizes size of the pool.
167  //! \param new_size new size of the pool after the call
168  void resize(unsigned_type new_size)
169  {
170  int_type diff = int_type(new_size) - int_type(size());
171  if (diff > 0)
172  {
173  while (--diff >= 0)
174  {
175  free_blocks.push_back(new block_type);
176  STXXL_VERBOSE_WPOOL(" create block=" << free_blocks.back());
177  }
178 
179  return;
180  }
181 
182  while (++diff <= 0)
183  delete steal();
184  }
185 
187  {
188  busy_blocks_iterator i2 = busy_blocks.begin();
189  for ( ; i2 != busy_blocks.end(); ++i2)
190  {
191  if (i2->bid == bid)
192  return i2->req;
193  }
194  return request_ptr();
195  }
196 
198  {
199  for (busy_blocks_iterator i2 = busy_blocks.begin(); i2 != busy_blocks.end(); ++i2)
200  {
201  if (i2->bid == bid)
202  return true;
203  }
204  return false;
205  }
206 
208  {
209  busy_blocks_iterator i2 = busy_blocks.begin();
210  for ( ; i2 != busy_blocks.end(); ++i2)
211  {
212  if (i2->bid == bid)
213  {
214  block_type* p = i2->block;
215  i2->req->wait();
216  busy_blocks.erase(i2);
217  return p;
218  }
219  }
220  return NULL;
221  }
222 
223  // returns a block and a (potentially unfinished) I/O request associated with it
224  std::pair<block_type*, request_ptr> steal_request(bid_type bid)
225  {
226  for (busy_blocks_iterator i2 = busy_blocks.begin(); i2 != busy_blocks.end(); ++i2)
227  {
228  if (i2->bid == bid)
229  {
230  // remove busy block from list, request has not yet been waited for!
231  block_type* blk = i2->block;
232  request_ptr req = i2->req;
233  busy_blocks.erase(i2);
234 
235  STXXL_VERBOSE_WPOOL("::steal_request block=" << blk);
236  // hand over block and (unfinished) request to caller
237  return std::pair<block_type*, request_ptr>(blk, req);
238  }
239  }
240  STXXL_VERBOSE_WPOOL("::steal_request NOT FOUND");
241  // not matching request found, return a dummy
242  return std::pair<block_type*, request_ptr>((block_type*)NULL, request_ptr());
243  }
244 
245  void add(block_type*& block)
246  {
247  STXXL_VERBOSE_WPOOL("::add " << block);
248  free_blocks.push_back(block);
249  block = NULL; // prevent caller from using the block any further
250  }
251 
252 protected:
254  {
255  busy_blocks_iterator cur = busy_blocks.begin();
256  int_type cnt = 0;
257  while (cur != busy_blocks.end())
258  {
259  if (cur->req->poll())
260  {
261  free_blocks.push_back(cur->block);
262  cur = busy_blocks.erase(cur);
263  ++cnt;
264  continue;
265  }
266  ++cur;
267  }
268  STXXL_VERBOSE_WPOOL("::check_all_busy : " << cnt <<
269  " are completed out of " << busy_blocks.size() + cnt << " busy blocks");
270  }
271 };
272 
273 //! \}
274 
276 
277 namespace std {
278 
279 template <class BlockType>
280 void swap(stxxl::write_pool<BlockType>& a,
282 {
283  a.swap(b);
284 }
285 
286 } // namespace std
287 
288 #endif // !STXXL_MNG_WRITE_POOL_HEADER
289 // vim: et:ts=4:sw=4
bool has_request(bid_type bid)
Definition: write_pool.h:197
#define STXXL_ASSERT(condition)
Definition: verbose.h:220
void add(block_type *&block)
Definition: write_pool.h:245
Definition: write_pool.h:39
block_type * steal()
Take out a block from the pool.
Definition: write_pool.h:139
bid_type bid
Definition: write_pool.h:43
std::list< busy_entry >::iterator busy_blocks_iterator
Definition: write_pool.h:53
write_pool(unsigned_type init_size=1)
Constructs pool.
Definition: write_pool.h:64
#define STXXL_VERBOSE_WPOOL(msg)
Definition: write_pool.h:23
std::list< busy_entry > busy_blocks
Definition: write_pool.h:59
#define STXXL_DEPRECATED(x)
Definition: deprecated.h:30
block_type * block
Definition: write_pool.h:41
busy_entry()
Definition: write_pool.h:45
void resize(unsigned_type new_size)
Resizes size of the pool.
Definition: write_pool.h:168
request_ptr get_request(bid_type bid)
Definition: write_pool.h:186
std::pair< block_type *, request_ptr > steal_request(bid_type bid)
Definition: write_pool.h:224
BlockType block_type
Definition: write_pool.h:35
Implements dynamically resizable buffered writing pool.
Definition: write_pool.h:32
block_type::bid_type bid_type
Definition: write_pool.h:36
counting_ptr< request > request_ptr
A reference counting pointer for request.
Definition: request.h:113
choose_int_types< my_pointer_size >::int_type int_type
Definition: types.h:63
void check_all_busy()
Definition: write_pool.h:253
std::list< block_type * > free_blocks
Definition: write_pool.h:57
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
block_type * steal(bid_type bid)
Definition: write_pool.h:207
request_ptr write(block_type *&block, bid_type bid)
Passes a block to the pool for writing.
Definition: write_pool.h:116
std::list< block_type * >::iterator free_blocks_iterator
Definition: write_pool.h:52
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
RequestIterator wait_any(RequestIterator reqs_begin, RequestIterator reqs_end)
Suspends calling thread until any of requests is completed.
busy_entry(const busy_entry &a)
Definition: write_pool.h:46
unsigned_type size() const
Returns number of owned blocks.
Definition: write_pool.h:108
request_ptr req
Definition: write_pool.h:42
busy_entry(block_type *&bl, request_ptr &r, bid_type &bi)
Definition: write_pool.h:47
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
~write_pool()
Waits for completion of all ongoing write requests and frees memory.
Definition: write_pool.h:80
void swap(write_pool &obj)
Definition: write_pool.h:73