1 /*
2  * (c) 2008-2009 Adam Lackorzynski <adam@os.inf.tu-dresden.de>,
3  *               Alexander Warg <warg@os.inf.tu-dresden.de>,
4  *               Carsten Weinhold <weinhold@os.inf.tu-dresden.de>
5  *     economic rights: Technische Universität Dresden (Germany)
6  *
7  * This file is part of TUD:OS and distributed under the terms of the
8  * GNU General Public License 2.
9  * Please see the COPYING-GPL-2 file for details.
10  */
11 #include "mem_man.h"
12 #include "globals.h"
13 
14 #include <l4/cxx/iostream>
15 #include <l4/sys/assert.h>
16 
17 Mem_man Mem_man::_ram;
18 
19 Region const *
find(Region const & r,bool force) const20 Mem_man::find(Region const &r, bool force) const
21 {
22   if (!r.valid())
23     return 0;
24 
25   Tree::Const_iterator n = _tree.find(r);
26   if (n == _tree.end())
27     return 0;
28 
29   if (n->contains(r) || force)
30     return &(*n);
31 
32   return 0;
33 }
34 
35 bool
add(Region const & r)36 Mem_man::add(Region const &r)
37 {
38   /* try to merge with prev region */
39   Region rs = r;
40   if (rs.start() > 0)
41     {
42       rs.start(rs.start()-1);
43 
44       Tree::Node n = _tree.find_node(rs);
45       if (n && n->owner() == r.owner() && n->rights() == r.rights())
46         {
47           r.start(n->start());
48           int err = _tree.remove(*n);
49           if (err < 0)
50             {
51               L4::cout << "err=" << err << " dump:\n";
52               dump();
53               l4_assert(!"BUG");
54             }
55         }
56     }
57 
58   /* try to merge with next region */
59   rs = r;
60   if (rs.end() + 1 != 0)
61     {
62       rs.end(rs.end()+1);
63 
64       Tree::Node n = _tree.find_node(rs);
65       if (n && n->owner() == r.owner() && n->rights() == r.rights())
66         {
67           r.end(n->end());
68           int err = _tree.remove(*n);
69           if (err < 0)
70             {
71               L4::cout << "err=" << err << " dump:\n";
72               dump();
73               l4_assert(!"BUG");
74             }
75         }
76     }
77 
78   /* do throw away regions owned by myself */
79   if (r.owner() == sigma0_taskno)
80     return true;
81 
82   while (_tree.insert(r).second == -_tree.E_nomem)
83     if (!ram()->morecore())
84       {
85         if (debug_errors)
86           L4::cout << PROG_NAME": Out of memory\n";
87         return false;
88       }
89 
90   return true;
91 }
92 
93 bool
add_free(Region const & r)94 Mem_man::add_free(Region const &r)
95 {
96   if (!r.valid())
97     return true;
98 
99   // calculate the combined set of all overlapping regions within the tree
100   while (1)
101     {
102       Tree::Node n = _tree.find_node(r);
103 
104       if (!n)
105         break;
106 
107       if (n->start() < r.start())
108         r.start(n->start());
109       if (n->end() > r.end())
110         r.end(n->end());
111 
112       int err = _tree.remove(*n);
113       if (err < 0)
114         {
115           L4::cout << "err=" << err << " dump:\n";
116           dump();
117           l4_assert(!"BUG");
118         }
119     }
120 
121   return add(r);
122 }
123 
124 bool
alloc_from(Region const * r2,Region const & _r)125 Mem_man::alloc_from(Region const *r2, Region const &_r)
126 {
127   if (!_r.valid())
128     return false;
129 
130   Region r(_r);
131   if (r2->owner() && r2->owner() != r.owner())
132     return false;
133 
134   if (r2->owner() == r.owner() && r2->rights() == r.rights())
135     return true;
136 
137   if (r == *r2)
138     {
139       if (0)
140         {
141           L4::cout << "dump " << r << " " << *r2 << "\n";
142           dump();
143         }
144       int err = _tree.remove(*r2);
145       if (err < 0)
146         {
147           L4::cout << "err=" << err << " dump:\n";
148           dump();
149           l4_assert(!"BUG");
150         }
151       return add(r);
152     }
153 
154   Region r2_orig = *r2;
155 
156   if (r.start() == r2->start())
157     {
158       r2->start(r.end() + 1);
159       if (0)
160         L4::cout << "move start to " << *r2 << '\n';
161     }
162   else if (r.end() == r2->end())
163     {
164       r2->end(r.start() - 1);
165       if (0)
166         L4::cout << "shrink end to " << *r2 << '\n';
167     }
168   else
169     {
170       Region const nr(r.end() + 1, r2->end(), r2->owner(), r2->rights());
171       r2->end(r.start() - 1);
172       if (0)
173         L4::cout << "split to " << *r2 << "; " << nr << '\n';
174 
175       if (nr.valid() && !add(nr))
176         {
177           r2->restore_range_from(r2_orig);
178           return false;
179         }
180     }
181 
182   if (!add(r))
183     {
184       r2->restore_range_from(r2_orig);
185       return false;
186     }
187 
188   return true;
189 }
190 
191 unsigned long
alloc(Region const & r)192 Mem_man::alloc(Region const &r)
193 {
194   if (!r.valid())
195     return ~0UL;
196   Region const *r2 = find(r);
197   if (!r2)
198     return ~0UL;
199 
200   if (0)
201     L4::cout << "alloc_from(" << *r2 << ", " << r << ")\n";
202   if (!alloc_from(r2, r))
203     return ~0UL;
204 
205   return r.start();
206 }
207 
208 /**
209  * Allocate region from its containing region and inherit its rights.
210  *
211  * @param[in] r        Region to allocate. Its rights are the necessary minimal
212  *                     rights of the containing region.
213  * @param[out] rights  Address of the variable that will receive the full rights
214  *                     of the containing region.
215  *
216  * @retval true   The region was allocated.
217  * @retval false  The region was not allocated.
218  */
219 bool
alloc_get_rights(Region const & r,L4_fpage_rights * rights)220 Mem_man::alloc_get_rights(Region const &r, L4_fpage_rights *rights)
221 {
222   Region q = r;
223   auto const *p = find(q);
224   if (!p)
225     return false;
226   if ((p->rights() & q.rights()) != q.rights())
227     return false;
228 
229   *rights = p->rights();
230   q.rights(p->rights());
231   return alloc_from(p, q);
232 }
233 
234 /**
235  * Add a reserved memory region into the map.
236  *
237  * \return true if the region could be reserved, or false in the case
238  * of an error. Note, any error is considered fatal and might create
239  * an inconsistent / incorrect memory map.
240  */
241 bool
reserve(Region const & r)242 Mem_man::reserve(Region const &r)
243 {
244   if (!r.valid())
245     return false;
246 
247   for (;;)
248     {
249       auto r2 = _tree.find(r);
250 
251       //Region const *r2 = find(r, true);
252       if (r2 == _tree.end())
253         {
254           if (0)
255             L4::cout << this << ": ADD: " << r << "\n";
256           return add(r);
257         }
258 
259       if (0)
260         L4::cout << this << ":  RESERVE: " << r << " from " << (*r2) << "\n";
261 
262       if (r2->owner() && r2->owner() != r.owner())
263         return false;
264 
265       // allow exact matches to update owner and rights of the reserved region
266       if (*r2 == r && (r2->owner() != r.owner() || r2->rights() != r.rights()))
267         {
268           int err = _tree.remove(*r2);
269           if (err < 0)
270             {
271               L4::cout << "err=" << err << " dump:\n";
272               dump();
273               l4_assert(!"BUG");
274             }
275           return add(r);
276         }
277 
278       // contained region will not get any updated rights
279       if (r2->contains(r) && r2->owner() == r.owner())
280         return true;
281 
282       if (r2->contains(r))
283         {
284           Region r2_orig = *r2;
285 
286           if (r2->start() == r.start())
287             r2->start(r.end() + 1);
288           else
289             {
290               Region const nr(r.end() + 1, r2->end(), r2->owner(), r2->rights());
291               r2->end(r.start() - 1);
292               if (0)
293                 L4::cout << this << ": ADDnr: " << nr << "\n";
294               // FIXME: we could avoid the merge code for this add
295               //        because this region is per definition not mergeable
296               if (nr.valid() && !add(nr))
297                 {
298                   r2->restore_range_from(r2_orig);
299                   return false;
300                 }
301             }
302 
303           if (0)
304             L4::cout << this << ": ADD: " << r << "\n";
305 
306           if (!add(r))
307             {
308               r2->restore_range_from(r2_orig);
309               return false;
310             }
311           return true;
312         }
313 
314       if (r.contains(*r2))
315         {
316           if (0)
317             L4::cout << this << ": REMOVE: " << *r2 << "\n";
318           _tree.remove(*r2);
319           continue;
320         }
321 
322       if (r2->start() < r.start())
323         {
324           if (r2->owner())
325             r.start(r2->end() + 1);
326           else
327             r2->end(r.start() - 1);
328         }
329       else
330         {
331           if (r2->owner())
332             r.end(r2->start() - 1);
333           else
334             r2->start(r.end() + 1);
335         }
336     }
337 }
338 
339 
340 bool
morecore()341 Mem_man::morecore()
342 {
343   Tree::Item_type *n = 0;
344   for (Tree::Rev_iterator i = _tree.rbegin(); i != _tree.rend(); ++i)
345     {
346       if (i->owner())
347         continue;
348 
349       l4_addr_t st = l4_round_page(i->start());
350 
351       if (st < i->end() && i->end() - st >= L4_PAGESIZE - 1)
352         {
353           n = &(*i);
354           break;
355         }
356     }
357 
358   if (!n)
359     {
360       if (debug_memory_maps)
361         L4::cout << PROG_NAME": morecore did not find more free memory\n";
362       return false;
363     }
364 
365   Region a = Region::bs(l4_round_page(n->end() - L4_PAGESIZE - 1),
366                         L4_PAGESIZE, sigma0_taskno);
367 
368   Page_alloc_base::free((void*)a.start());
369 
370   alloc_from(n, a);
371 
372   if (debug_memory_maps)
373     L4::cout << PROG_NAME": morecore: total=" << Page_alloc_base::total() / 1024
374              << "kB avail=" << Page_alloc_base::allocator()->avail() / 1024
375              << "kB: added " << a << '\n';
376   return true;
377 }
378 
379 unsigned long
alloc_first(unsigned long size,unsigned owner)380 Mem_man::alloc_first(unsigned long size, unsigned owner)
381 {
382   Tree::Item_type *n = 0;
383 
384   for (Tree::Iterator i = _tree.begin(); i != _tree.end(); ++i)
385     {
386       if (i->owner())
387         continue;
388 
389       // wrap-around?
390       if ((i->start() + size - 1) < i->start())
391         continue;
392 
393       l4_addr_t st = (i->start() + size - 1) & ~(size - 1);
394       if (0)
395         L4::cout << "test: " << (void*)st << " - " << i->end() << '\n';
396 
397       if (st < i->end() && i->end() - st >= size - 1)
398         {
399           n = &(*i);
400           break;
401         }
402     }
403 
404   if (!n)
405     return ~0UL;
406 
407   Region a = Region::bs((n->start() + size - 1) & ~(size - 1), size, owner);
408 
409   if (!alloc_from(n, a))
410     return ~0UL;
411 
412   return a.start();
413 }
414 
415 void
dump()416 Mem_man::dump()
417 {
418   for (Tree::Iterator i = _tree.begin(); i != _tree.end(); ++i)
419     L4::cout << *i << '\n';
420 }
421