rtree/small/matras.h

filter: Statementstmt 0.0% 0 / 9 Branchbran 0.0% 0 / 2 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 0.0% 0 / 11 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/DR/R.pm ↑ Summary matras.c »
1 #ifndef INCLUDES_TARANTOOL_SMALL_MATRAS_H
2 #define INCLUDES_TARANTOOL_SMALL_MATRAS_H
3 /*
4 * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
5 *
6 * Redistribution and use in source and binary forms, with or
7 * without modification, are permitted provided that the following
8 * conditions are met:
9 *
10 * 1. Redistributions of source code must retain the above
11 * copyright notice, this list of conditions and the
12 * following disclaimer.
13 *
14 * 2. Redistributions in binary form must reproduce the above
15 * copyright notice, this list of conditions and the following
16 * disclaimer in the documentation and/or other materials
17 * provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
23 * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
24 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
27 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
30 * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33  
34 /* {{{ Description */
35 /*
36 * matras - Memory Address TRanSlation Allocator (Smile)
37 * matras is as allocator, that provides aligned blocks of specified
38 * size (N), and a 32-bit integer identifiers for
39 * each returned block. Block identifiers grow incrementally
40 * starting from 0.
41 *
42 * The block size (N) must be a power of 2 (checked by assert in
43 * the debug build). matras can restore a pointer to the block
44 * give block ID, so one can store such 32-bit ids instead of
45 * storing pointers to blocks.
46 *
47 * Since block IDs grow incrementally from 0 and matras
48 * instance stores the number of provided blocks, there is a
49 * simple way to iterate over all provided blocks.
50 *
51 * Implementation
52 * --------------
53 * To support block allocation, matras allocates extents of memory
54 * by means of the supplied allocator, each extent having the same
55 * size (M), M is a power of 2 and a multiple of N.
56 * There is no way to free a single block, except the last one,
57 * allocated, which happens to be the one with the largest ID.
58 * Destroying a matras instance frees all allocated extents.
59 *
60 * Address translation
61 * -------------------
62 * To implement 32-bit address space for block identifiers,
63 * matras maintains a simple tree of address translation tables.
64 *
65 * * First N1 bits of the identifier denote a level 0 extend
66 * id, which stores the address of level 1 extent.
67 *
68 * * Second N2 bits of block identifier stores the address
69 * of a level 2 extent, which stores actual blocks.
70 *
71 * * The remaining N3 bits denote the block number
72 * within the extent.
73 *
74 * Actual values of N1 and N2 are a function of block size B,
75 * extent size M and sizeof(void *).
76 *
77 * To sum up, with a given N and M matras instance:
78 *
79 * 1) can provide not more than
80 * pow(M / sizeof(void*), 2) * (M / N) blocks
81 *
82 * 2) costs 2 random memory accesses to provide a new block
83 * or restore a block pointer from block id
84 *
85 * 3) has an approximate memory overhead of size (L * M)
86 *
87 * Of course, the integer type used for block id (matras_id_t,
88 * usually is a typedef to uint32) also limits the maximum number
89 * of objects that can be allocated by a single instance of matras.
90 *
91 * Versioning
92 * ----------
93 * Starting from Tarantool 1.6, matras implements a way to create
94 * a consistent read view of allocated data with
95 * matras_create_read_view(). Once a read view is
96 * created, the same block identifier can return two different
97 * physical addresses in two views: the created view
98 * and the current or latest view. Multiple read views can be
99 * created. To work correctly with possibly existing read views,
100 * the application must inform matras that data in a block is about to
101 * change, using matras_touch() call. Only a block which belong to
102 * the current, i.e. latest, view, can be changed: created
103 * views are immutable.
104 *
105 * The implementation of read views is based on copy-on-write
106 * technique, which is cheap enough as long as not too many
107 * objects have to be touched while a view exists.
108 * Another important property of the copy-on-write mechanism is
109 * that whenever a write occurs, the writer pays the penalty
110 * and copies the block to a new location, and gets a new physical
111 * address for the same block id. The reader keeps using the
112 * old address. This makes it possible to access the
113 * created read view in a concurrent thread, as long as this
114 * thread is created after the read view itself is created.
115 */
116 /* }}} */
117  
118 #include <assert.h>
119 #include <stdint.h>
120  
121 #if defined(__cplusplus)
122 extern "C" {
123 #endif /* defined(__cplusplus) */
124  
125 /**
126 * Type of a block ID.
127 */
128 #ifdef WIN32
129 typedef unsigned __int32 matras_id_t;
130 #else
131 typedef uint32_t matras_id_t;
132 #endif
133  
134 /**
135 * Type of the extent allocator (the allocator for regions
136 * of size M). Is allowed to return NULL, but is not allowed
137 * to throw an exception
138 */
139 typedef void *(*matras_alloc_func)(void *ctx);
140 typedef void (*matras_free_func)(void *ctx, void *ptr);
141  
142 /**
143 * sruct matras_view represents appropriate mapping between
144 * block ID and it's pointer.
145 * matras structure has one main read/write view, and a number
146 * of user created read-only views.
147 */
148 struct matras_view {
149 /* root extent of the view */
150 void *root;
151 /* block count in the view */
152 matras_id_t block_count;
153 /* all views are linked into doubly linked list */
154 struct matras_view *prev_view, *next_view;
155 };
156  
157 /**
158 * matras - memory allocator of blocks of equal
159 * size with support of address translation.
160 */
161 struct matras {
162 /* Main read/write view of the matras */
163 struct matras_view head;
164 /* Block size (N) */
165 matras_id_t block_size;
166 /* Extent size (M) */
167 matras_id_t extent_size;
168 /* Numberof allocated extents */
169 matras_id_t extent_count;
170 /* binary logarithm of maximum possible created blocks count */
171 matras_id_t log2_capacity;
172 /* See "Shifts and masks explanation" below */
173 matras_id_t shift1, shift2;
174 /* See "Shifts and masks explanation" below */
175 matras_id_t mask1, mask2;
176 /* External extent allocator */
177 matras_alloc_func alloc_func;
178 /* External extent deallocator */
179 matras_free_func free_func;
180 /* Argument passed to extent allocator */
181 void *alloc_ctx;
182 };
183  
184 /*
185 * "Shifts and masks explanation"
186 * For 3-level matras (L = 3), as claimed above, block ID consist of
187 * three parts (N1, N2 and N3).
188 * In order to optimize splitting ID, several masks and shifts
189 * are precalculated during matras initialization.
190 * Heres is an example block ID bits, high order bits first:
191 * ID : 0 0 0 0 N1 N1 N1 N1 N2 N2 N2 N2 N3 N3 N3 N3 N3
192 * mask1: 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
193 * mask1: 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
194 * <---------shift1-------->
195 * <---shift2-->
196 * When defined in such way, one can simply split ID to N1, N2 and N3:
197 * N1 = ID >> shift1
198 * N2 = (ID & mask1) >> shift2
199 * N3 = ID & mask2
200 */
201  
202 /*
203 * matras API declaration
204 */
205  
206 /**
207 * Initialize an empty instance of pointer translating
208 * block allocator. Does not allocate memory.
209 */
210 void
211 matras_create(struct matras *m, matras_id_t extent_size, matras_id_t block_size,
212 matras_alloc_func alloc_func, matras_free_func free_func,
213 void *alloc_ctx);
214  
215 /**
216 * Free all memory used by an instance of matras and
217 * reinitialize it.
218 * Identical to matras_destroy(m); matras_create(m, ...);
219 */
220 void
221 matras_reset(struct matras *m);
222  
223 /**
224 * Free all memory used by an instance of matras.
225 */
226 void
227 matras_destroy(struct matras *m);
228  
229 /**
230 * Allocate a new block. Return both, block pointer and block
231 * id.
232 *
233 * @retval NULL failed to allocate memory
234 */
235 void *
236 matras_alloc(struct matras *m, matras_id_t *id);
237  
238 /*
239 * Deallocate last block (block with maximum ID)
240 */
241 void
242 matras_dealloc(struct matras *m);
243  
244 /**
245 * Allocate a range_count of blocks. Return both, first block pointer
246 * and first block id. This method only works if current number of blocks and
247 * number of blocks in one extent are divisible by range_count.
248 * range_count must also be less or equal to number of blocks in one extent.
249 *
250 * @retval NULL failed to allocate memory
251 */
252 void *
253 matras_alloc_range(struct matras *m, matras_id_t *id, matras_id_t range_count);
254  
255 /*
256 * Deallocate last range_count of blocks (blocks with maximum ID)
257 * This method only works if current number of blocks and
258 * number of blocks in one extent are divisible by range_count.
259 * range_count must also be less or equal to number of blocks in one extent.
260 */
261 void
262 matras_dealloc_range(struct matras *m, matras_id_t range_count);
263  
264 /**
265 * Convert block id into block address.
266 */
267 static void *
268 matras_get(const struct matras *m, matras_id_t id);
269  
270 /**
271 * Convert block id of a specified version into block address.
272 */
273 static void *
274 matras_view_get(const struct matras *m, const struct matras_view *v,
275 matras_id_t id);
276  
277 /*
278 * Getting number of allocated extents (of size extent_size each)
279 */
280 matras_id_t
281 matras_extent_count(const struct matras *m);
282  
283 /*
284 * Connect read view to the matras so that it is always connected with main,
285 * "head" read view. Such a read view does not consume any resources and
286 * should not be destroyed.
287 */
288 static void
289 matras_head_read_view(struct matras_view *v);
290  
291 /*
292 * Create new read view.
293 */
294 void
295 matras_create_read_view(struct matras *m, struct matras_view *v);
296  
297 /*
298 * Delete a read view.
299 */
300 void
301 matras_destroy_read_view(struct matras *m, struct matras_view *v);
302  
303 /*
304 * Determine if the read view is created.
305 * @return 1 if the read view was created with matras_create_read_view
306 * @return 0 if the read view was initialized with matras_head_read_view
307 */
308 static int
309 matras_is_read_view_created(struct matras_view *v);
310  
311 /*
312 * Notify matras that memory at given ID will be changed.
313 * Returns (perhaps new) address of memory associated with that block.
314 * Returns NULL on memory error
315 * Only needed (and does any work) if some versions are used.
316 */
317 void *
318 matras_touch(struct matras *m, matras_id_t id);
319  
320 /*
321 * matras_head_read_view implementation.
322 */
323 static inline void
324 matras_head_read_view(struct matras_view *v)
325 {
326 v->next_view = 0;
327 }
328  
329 /*
330 * matras_is_read_view_created implementation.
331 */
332 static inline int
333 matras_is_read_view_created(struct matras_view *v)
334 {
335 return v->next_view ? 1 : 0;
336 }
337  
338 /**
339 * Common part of matras_view_get and matras_get
340 */
341 static inline void *
342 0 matras_view_get_no_check(const struct matras *m, const struct matras_view *v,
343 matras_id_t id)
344 {
345 0 ▶ assert(id < v->block_count);
Branch: 1 branch
BranchTrueFalseTotal
assert(id < v->block_count); 0 0 0
346  
347 /* see "Shifts and masks explanation" for details */
348 0 matras_id_t n1 = id >> m->shift1;
349 0 matras_id_t n2 = (id & m->mask1) >> m->shift2;
350 0 matras_id_t n3 = (id & m->mask2);
351  
352 0 char ***extent = (char ***)v->root;
353 0 return &extent[n1][n2][n3 * m->block_size];
354 }
355  
356 /**
357 * matras_view_get definition
358 */
359 static inline void *
360 matras_view_get(const struct matras *m, const struct matras_view *v,
361 matras_id_t id)
362 {
363 return matras_view_get_no_check(m, v->next_view ? v : &m->head, id);
364 }
365  
366 /**
367 * matras_get definition
368 */
369 static inline void *
370 0 matras_get(const struct matras *m, matras_id_t id)
371 {
372 0 return matras_view_get_no_check(m, &m->head, id);
373 }
374  
375 #if defined(__cplusplus)
376 } /* extern "C" */
377 #endif /* defined(__cplusplus) */
378 #endif /* INCLUDES_TARANTOOL_SMALL_MATRAS_H */
« blib/lib/DR/R.pm ↑ Summary matras.c »