1 /*
2 * \brief Heap partition
3 * \author Norman Feske
4 * \date 2006-05-15
5 */
6
7 /*
8 * Copyright (C) 2006-2013 Genode Labs GmbH
9 *
10 * This file is part of the Genode OS framework, which is distributed
11 * under the terms of the GNU General Public License version 2.
12 */
13
14 #ifndef _INCLUDE__BASE__HEAP_H_
15 #define _INCLUDE__BASE__HEAP_H_
16
17 #include <util/list.h>
18 #include <ram_session/ram_session.h>
19 #include <rm_session/rm_session.h>
20 #include <base/allocator_avl.h>
21 #include <base/lock.h>
22
23 namespace Genode {
24
25 /**
26 * Heap that uses dataspaces as backing store
27 *
28 * The heap class provides an allocator that uses a list of dataspaces of a ram
29 * session as backing store. One dataspace may be used for holding multiple blocks.
30 */
31 class Heap : public Allocator
32 {
33 private:
34
35 enum {
36 MIN_CHUNK_SIZE = 4*1024, /* in machine words */
37 MAX_CHUNK_SIZE = 256*1024
38 }
39
40 class Dataspace : public List<Dataspace>::Element
41 {
42 public:
43
44 Ram_dataspace_capability cap;
45 void *local_addr;
46
47 Dataspace(Ram_dataspace_capability c, void *a)
48 : cap(c), local_addr(a){}
49
50 inline void * operator new(Genode::size_t, void* addr){
51 return addr}
52 inline void operator delete(void*){ }
53 }
54
55 class Dataspace_pool : public List<Dataspace>
56 {
57 private:
58
59 Ram_session *_ram_session; /* ram session for backing store */
60 Rm_session *_rm_session; /* region manager */
61
62 public:
63
64 /**
65 * Constructor
66 */
67 Dataspace_pool(Ram_session *ram_session, Rm_session *rm_session):
68 _ram_session(ram_session), _rm_session(rm_session){ }
69
70 /**
71 * Destructor
72 */
73 ~Dataspace_pool();
74
75 /**
76 * Expand dataspace by specified size
77 *
78 * \param size number of bytes to add to the dataspace pool
79 * \param md_alloc allocator to expand. This allocator is also
80 * used for meta data allocation (only after
81 * being successfully expanded).
82 * \throw Rm_session::Invalid_dataspace,
83 * Rm_session::Region_conflict
84 * \return 0 on success or negative error code
85 */
86 int expand(size_t size, Range_allocator *alloc);
87
88 void reassign_resources(Ram_session *ram, Rm_session *rm) {
89 _ram_session = ram, _rm_session = rm;}
90 }
91
92 /*
93 * NOTE: The order of the member variables is important for
94 * the calling order of the destructors!
95 */
96
97 Lock _lock;
98 Dataspace_pool _ds_pool; /* list of dataspaces */
99 Allocator_avl _alloc; /* local allocator */
100 size_t _quota_limit;
101 size_t _quota_used;
102 size_t _chunk_size;
103
104 /**
105 * Try to allocate block at our local allocator
106 *
107 * \return true on success
108 *
109 * This function is a utility used by `alloc` to avoid
110 * code duplication.
111 */
112 bool _try_local_alloc(size_t size, void **out_addr);
113
114 public:
115
116 enum { UNLIMITED = ~0 }
117
118 Heap(Ram_session *ram_session,
119 Rm_session *rm_session,
120 size_t quota_limit= UNLIMITED,
121 void *static_addr= 0,
122 size_t static_size= 0)
123 :
124 _ds_pool(ram_session, rm_session),
125 _alloc(0),
126 _quota_limit(quota_limit), _quota_used(0),
127 _chunk_size(MIN_CHUNK_SIZE)
128 {
129 if (static_addr)
130 _alloc.add_range((addr_t), static_size);
131 }
132
133 /**
134 * Reconfigure quota limit
135 *
136 * \return negative error code if new quota limit is higher than
137 * currently used quota.
138 */
139 int quota_limit(size_t new_quota_limit);
140
141 /**
142 * Re-assign RAM and RM sessions
143 */
144 void reassign_resources(Ram_session *ram, Rm_session *rm) {
145 _ds_pool.reassign_resources(ram, rm);}
146
147
148 /*************************
149 ** Allocator interface **
150 *************************/
151
152 bool alloc(size_t, void **);
153 void free(void *, size_t);
154 size_t consumed() { return _quota_used}
155 size_t overhead(size_t size) { return _alloc.overhead(size)}
156 bool need_size_for_free() const { return false}
157 }
158
159
160 /**
161 * Heap that allocates each block at a separate dataspace
162 */
163 class Sliced_heap : public Allocator
164 {
165 private:
166
167 class Block;
168
169 Ram_session *_ram_session; /* ram session for backing store */
170 Rm_session *_rm_session; /* region manager */
171 size_t _consumed; /* number of allocated bytes */
172 List<Block> _block_list; /* list of allocated blocks */
173 Lock _lock; /* serialize allocations */
174
175 public:
176
177 /**
178 * Constructor
179 */
180 Sliced_heap(Ram_session *ram_session, Rm_session *rm_session);
181
182 /**
183 * Destructor
184 */
185 ~Sliced_heap();
186
187
188 /*************************
189 ** Allocator interface **
190 *************************/
191
192 bool alloc(size_t, void **);
193 void free(void *, size_t);
194 size_t consumed() { return _consumed}
195 size_t overhead(size_t size);
196 bool need_size_for_free() const { return false}
197 }
198 }
199
200 #endif /* _INCLUDE__BASE__HEAP_H_ */