L4Re - L4 Runtime Environment
region_mapping
Go to the documentation of this file.
1 // -*- Mode: C++ -*-
2 // vim:ft=cpp
3 /**
4  * \file region_mapping
5  * \brief Region handling
6  */
7 /*
8  * (c) 2008-2009 Adam Lackorzynski <adam@os.inf.tu-dresden.de>,
9  * Alexander Warg <warg@os.inf.tu-dresden.de>,
10  * Björn Döbel <doebel@os.inf.tu-dresden.de>
11  * economic rights: Technische Universität Dresden (Germany)
12  *
13  * This file is part of TUD:OS and distributed under the terms of the
14  * GNU General Public License 2.
15  * Please see the COPYING-GPL-2 file for details.
16  *
17  * As a special exception, you may use this file as part of a free software
18  * library without restriction. Specifically, if other files instantiate
19  * templates or use macros or inline functions from this file, or you compile
20  * this file and link it with other files to produce an executable, this
21  * file does not by itself cause the resulting executable to be covered by
22  * the GNU General Public License. This exception does not however
23  * invalidate any other reasons why the executable file might be covered by
24  * the GNU General Public License.
25  */
26 
27 #pragma once
28 
29 #include <l4/cxx/avl_map>
30 #include <l4/sys/types.h>
31 #include <l4/re/rm>
32 
33 
34 namespace L4Re { namespace Util {
35 class Region
36 {
37 private:
38  l4_addr_t _start, _end;
39 
40 public:
41  Region() throw() : _start(~0UL), _end(~0UL) {}
42  Region(l4_addr_t addr) throw() : _start(addr), _end(addr) {}
43  Region(l4_addr_t start, l4_addr_t end) throw()
44  : _start(start), _end(end) {}
45  l4_addr_t start() const throw() { return _start; }
46  l4_addr_t end() const throw() { return _end; }
47  unsigned long size() const throw() { return end() - start() + 1; }
48  bool invalid() const throw() { return _start == ~0UL && _end == ~0UL; }
49  bool operator < (Region const &o) const throw()
50  { return end() < o.start(); }
51  bool contains(Region const &o) const throw()
52  { return o.start() >= start() && o.end() <= end(); }
53  bool operator == (Region const &o) const throw()
54  { return o.start() == start() && o.end() == end(); }
55  ~Region() throw() {}
56 };
57 
58 template< typename DS, typename OPS >
59 class Region_handler
60 {
61 private:
62  l4_addr_t _offs;
63  DS _mem;
64  l4_cap_idx_t _client_cap = L4_INVALID_CAP;
65  unsigned short _flags;
66 
67 public:
68  typedef DS Dataspace;
69  typedef OPS Ops;
70  typedef typename OPS::Map_result Map_result;
71 
72  Region_handler() throw() : _offs(0), _mem(), _flags() {}
73  Region_handler(Dataspace const &mem, l4_cap_idx_t client_cap,
74  l4_addr_t offset = 0, unsigned flags = 0) throw()
75  : _offs(offset), _mem(mem), _client_cap(client_cap), _flags(flags)
76  {}
77  Dataspace const &memory() const throw() { return _mem; }
78  l4_cap_idx_t client_cap_idx() const throw() { return _client_cap; }
79  l4_addr_t offset() const throw() { return _offs; }
80  l4_addr_t is_ro() const throw() { return _flags & L4Re::Rm::Read_only; }
81  unsigned long caching() const throw() { return _flags & L4Re::Rm::Caching; }
82  unsigned flags() const throw() { return _flags; }
83 
84  Region_handler operator + (long offset) const throw()
85  { Region_handler n = *this; n._offs += offset; return n; }
86 
87  void unmap(l4_addr_t va, l4_addr_t ds_offs, unsigned long size) const throw()
88  { Ops::unmap(this, va, ds_offs, size); }
89 
90  void free(l4_addr_t start, unsigned long size) const throw()
91  { Ops::free(this, start, size); }
92 
93  void take() const { Ops::take(this); }
94  void release() const { Ops::release(this); }
95 
96  int map(l4_addr_t addr, Region const &r, bool writable, Map_result *result) const
97  { return Ops::map(this, addr, r, writable, result); }
98 
99 };
100 
101 
102 template< typename Hdlr, template<typename T> class Alloc >
103 class Region_map
104 {
105 protected:
106  typedef cxx::Avl_map< Region, Hdlr, cxx::Lt_functor, Alloc > Tree;
107  Tree _rm; ///< Region Map
108  Tree _am; ///< Area Map
109 
110 private:
111  l4_addr_t _start;
112  l4_addr_t _end;
113 
114 protected:
115  void set_limits(l4_addr_t start, l4_addr_t end) throw()
116  {
117  _start = start;
118  _end = end;
119  }
120 
121 public:
122  typedef typename Tree::Item_type Item;
123  typedef typename Tree::Node Node;
124  typedef typename Tree::Key_type Key_type;
125  typedef Hdlr Region_handler;
126 
127  typedef typename Tree::Iterator Iterator;
128  typedef typename Tree::Const_iterator Const_iterator;
129  typedef typename Tree::Rev_iterator Rev_iterator;
130  typedef typename Tree::Const_rev_iterator Const_rev_iterator;
131 
132  Iterator begin() throw() { return _rm.begin(); }
133  Const_iterator begin() const throw() { return _rm.begin(); }
134  Iterator end() throw() { return _rm.end(); }
135  Const_iterator end() const throw() { return _rm.end(); }
136 
137  Iterator area_begin() throw() { return _am.begin(); }
138  Const_iterator area_begin() const throw() { return _am.begin(); }
139  Iterator area_end() throw() { return _am.end(); }
140  Const_iterator area_end() const throw() { return _am.end(); }
141  Node area_find(Key_type const &c) const throw() { return _am.find_node(c); }
142 
143  enum Attach_flags
144  {
145  None = 0,
146  Search = L4Re::Rm::Search_addr,
147  In_area = L4Re::Rm::In_area,
148  };
149 
150  l4_addr_t min_addr() const throw() { return _start; }
151  l4_addr_t max_addr() const throw() { return _end; }
152 
153 
154  Region_map(l4_addr_t start, l4_addr_t end) throw() : _start(start), _end(end) {}
155 
156  Node find(Key_type const &key) const throw()
157  {
158  Node n = _rm.find_node(key);
159  if (!n)
160  return Node();
161 
162  // 'find' should find any region overlapping with the searched one, the
163  // caller should check for further requirements
164  if (0)
165  if (!n->first.contains(key))
166  return Node();
167 
168  return n;
169  }
170 
171  Node lower_bound(Key_type const &key) const throw()
172  {
173  Node n = _rm.lower_bound_node(key);
174  return n;
175  }
176 
177  Node lower_bound_area(Key_type const &key) const throw()
178  {
179  Node n = _am.lower_bound_node(key);
180  return n;
181  }
182 
183  l4_addr_t attach_area(l4_addr_t addr, unsigned long size,
184  unsigned flags = None,
185  unsigned char align = L4_PAGESHIFT) throw()
186  {
187  if (size < 2)
188  return L4_INVALID_ADDR;
189 
190 
191  Region c;
192 
193  if (!(flags & Search))
194  {
195  c = Region(addr, addr + size - 1);
196  Node r = _am.find_node(c);
197  if (r)
198  return L4_INVALID_ADDR;
199  }
200 
201  while (flags & Search)
202  {
203  if (addr < min_addr() || (addr + size - 1) > max_addr())
204  addr = min_addr();
205  addr = find_free(addr, max_addr(), size, align, flags);
206  if (addr == L4_INVALID_ADDR)
207  return L4_INVALID_ADDR;
208 
209  c = Region(addr, addr + size - 1);
210  Node r = _am.find_node(c);
211  if (!r)
212  break;
213 
214  if (r->first.end() >= max_addr())
215  return L4_INVALID_ADDR;
216 
217  addr = r->first.end() + 1;
218  }
219 
220  if (_am.insert(c, Hdlr(typename Hdlr::Dataspace(), 0, flags)).second == 0)
221  return addr;
222 
223  return L4_INVALID_ADDR;
224  }
225 
226  bool detach_area(l4_addr_t addr) throw()
227  {
228  if (_am.remove(addr))
229  return false;
230 
231  return true;
232  }
233 
234  void *attach(void *addr, unsigned long size, Hdlr const &hdlr,
235  unsigned flags = None, unsigned char align = L4_PAGESHIFT) throw()
236  {
237  if (size < 2)
238  return L4_INVALID_PTR;
239 
240  l4_addr_t end = max_addr();
241  l4_addr_t beg = (l4_addr_t)addr;
242 
243  if (flags & In_area)
244  {
245  Node r = _am.find_node(Region(beg, beg + size - 1));
246  if (!r || (r->second.flags() & L4Re::Rm::Reserved))
247  return L4_INVALID_PTR;
248 
249  end = r->first.end();
250  }
251 
252  if (flags & Search)
253  {
254  beg = find_free(beg, end, size, align, flags);
255  if (beg == L4_INVALID_ADDR)
256  return L4_INVALID_PTR;
257  }
258 
259  if (!(flags & (Search | In_area)) && _am.find_node(Region(beg, beg + size - 1)))
260  return L4_INVALID_PTR;
261 
262  if (beg < min_addr() || beg + size -1 > end)
263  return L4_INVALID_PTR;
264 
265  if (_rm.insert(Region(beg, beg + size -1), hdlr).second == 0)
266  return (void*)beg;
267 
268  return L4_INVALID_PTR;
269  }
270 
271  int detach(void *addr, unsigned long sz, unsigned flags,
272  Region *reg, Hdlr *hdlr) throw()
273  {
274  Region dr((l4_addr_t)addr, (l4_addr_t)addr + sz - 1);
275  Region res(~0UL,0);
276 
277  Node r = find(dr);
278  if (!r)
279  return -L4_ENOENT;
280 
281  Region g = r->first;
282  Hdlr const &h = r->second;
283 
284  if (flags & L4Re::Rm::Detach_overlap || dr.contains(g))
285  {
286  if (_rm.remove(g))
287  return -L4_ENOENT;
288 
289  if (!(flags & L4Re::Rm::Detach_keep) && (h.flags() & L4Re::Rm::Detach_free))
290  h.free(0, g.size());
291 
292  if (hdlr) *hdlr = h;
293  if (reg) *reg = g;
294 
295  if (find(dr))
296  return Rm::Detached_ds | Rm::Detach_again;
297  else
298  return Rm::Detached_ds;
299  }
300  else if (dr.start() <= g.start())
301  {
302  // move the start of a region
303 
304  if (!(flags & L4Re::Rm::Detach_keep) && (h.flags() & L4Re::Rm::Detach_free))
305  h.free(0, dr.end() + 1 - g.start());
306 
307  unsigned long sz = dr.end() + 1 - g.start();
308  Item *cn = const_cast<Item*>((Item const *)r);
309  cn->first = Region(dr.end() + 1, g.end());
310  cn->second = cn->second + sz;
311  if (hdlr) *hdlr = Hdlr();
312  if (reg) *reg = Region(g.start(), dr.end());
313  if (find(dr))
314  return Rm::Kept_ds | Rm::Detach_again;
315  else
316  return Rm::Kept_ds;
317  }
318  else if (dr.end() >= g.end())
319  {
320  // move the end of a region
321 
322  if (!(flags & L4Re::Rm::Detach_keep) && (h.flags() & L4Re::Rm::Detach_free))
323  h.free(dr.start() - g.start(), g.end() + 1 - dr.start());
324 
325  Item *cn = const_cast<Item*>((Item const*)r);
326  cn->first = Region(g.start(), dr.start() -1);
327  if (hdlr) *hdlr = Hdlr();
328  if (reg) *reg = Region(dr.start(), g.end());
329 
330  if (find(dr))
331  return Rm::Kept_ds | Rm::Detach_again;
332  else
333  return Rm::Kept_ds;
334  }
335  else if (g.contains(dr))
336  {
337  // split a single region that contains the new region
338 
339  if (!(flags & L4Re::Rm::Detach_keep) && (h.flags() & L4Re::Rm::Detach_free))
340  h.free(dr.start() - g.start(), dr.size());
341 
342  // first move the end off the existing region before the new one
343  const_cast<Item*>((Item const *)r)->first = Region(g.start(), dr.start()-1);
344 
345  int err;
346 
347  // insert a second region for the remaining tail of
348  // the old existing region
349  err = _rm.insert(Region(dr.end() + 1, g.end()), h + (dr.end() + 1 - g.start())).second;
350 
351  if (err)
352  return err;
353 
354  if (hdlr) *hdlr = h;
355  if (reg) *reg = dr;
356  return Rm::Split_ds;
357  }
358  return -L4_ENOENT;
359  }
360 
361  l4_addr_t find_free(l4_addr_t start, l4_addr_t end, l4_addr_t size,
362  unsigned char align, unsigned flags) const throw();
363 
364 };
365 
366 
367 template< typename Hdlr, template<typename T> class Alloc >
368 l4_addr_t
369 Region_map<Hdlr, Alloc>::find_free(l4_addr_t start, l4_addr_t end,
370  unsigned long size, unsigned char align, unsigned flags) const throw()
371 {
372  l4_addr_t addr = start;
373 
374  if (addr == ~0UL || addr < min_addr() || addr >= end)
375  addr = min_addr();
376 
377  addr = l4_round_size(addr, align);
378  Node r;
379 
380  for(;;)
381  {
382  if (addr > 0 && addr - 1 > end - size)
383  return L4_INVALID_ADDR;
384 
385  Region c(addr, addr + size - 1);
386  r = _rm.find_node(c);
387 
388  if (!r)
389  {
390  if (!(flags & In_area) && (r = _am.find_node(c)))
391  {
392  if (r->first.end() > end - size)
393  return L4_INVALID_ADDR;
394 
395  addr = l4_round_size(r->first.end() + 1, align);
396  continue;
397  }
398  break;
399  }
400  else if (r->first.end() > end - size)
401  return L4_INVALID_ADDR;
402 
403  addr = l4_round_size(r->first.end() + 1, align);
404  }
405 
406  if (!r)
407  return addr;
408 
409  return L4_INVALID_ADDR;
410 }
411 
412 }}