summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorCedric Bail <cedric.bail@samsung.com>2013-07-01 17:09:02 +0900
committerCedric Bail <cedric.bail@samsung.com>2013-07-01 18:18:40 +0900
commitc435968f6965551c1e9d6103efe3261e884646f6 (patch)
tree58e27634edd47bc8c06d491131375c7a3f93d1e7 /src
parent6aa69a0c7d5eff48db340b1640cb5743d4a27723 (diff)
eo: a little more inlining, give me a 10% speed improvement.
Diffstat (limited to 'src')
-rw-r--r--src/Makefile_Eo.am2
-rw-r--r--src/lib/eo/eo_private.h8
-rw-r--r--src/lib/eo/eo_ptr_indirection.c498
-rw-r--r--src/lib/eo/eo_ptr_indirection.h2
-rw-r--r--src/lib/eo/eo_ptr_indirection.x504
5 files changed, 514 insertions, 500 deletions
diff --git a/src/Makefile_Eo.am b/src/Makefile_Eo.am
index e955632..ab24350 100644
--- a/src/Makefile_Eo.am
+++ b/src/Makefile_Eo.am
@@ -154,4 +154,4 @@ TESTS += tests/eo/test_signals
154endif 154endif
155 155
156 156
157EXTRA_DIST += tests/eo/eunit_tests.h 157EXTRA_DIST += tests/eo/eunit_tests.h lib/eo/eo_ptr_indirection.x
diff --git a/src/lib/eo/eo_private.h b/src/lib/eo/eo_private.h
index 4332383..b236b08 100644
--- a/src/lib/eo/eo_private.h
+++ b/src/lib/eo/eo_private.h
@@ -59,16 +59,16 @@ typedef struct _Eo_Class _Eo_Class;
59typedef struct _Eo_Internal _Eo; 59typedef struct _Eo_Internal _Eo;
60 60
61/* Retrieves the pointer to the object from the id */ 61/* Retrieves the pointer to the object from the id */
62_Eo *_eo_obj_pointer_get(const Eo_Id obj_id); 62static inline _Eo *_eo_obj_pointer_get(const Eo_Id obj_id);
63 63
64/* Allocates an entry for the given object */ 64/* Allocates an entry for the given object */
65Eo_Id _eo_id_allocate(const _Eo *obj); 65static inline Eo_Id _eo_id_allocate(const _Eo *obj);
66 66
67/* Releases an entry by the object id */ 67/* Releases an entry by the object id */
68void _eo_id_release(const Eo_Id obj_id); 68static inline void _eo_id_release(const Eo_Id obj_id);
69 69
70/* Free all the entries and the tables */ 70/* Free all the entries and the tables */
71void _eo_free_ids_tables(); 71static inline void _eo_free_ids_tables(void);
72 72
73void _eo_condtor_done(Eo *obj); 73void _eo_condtor_done(Eo *obj);
74 74
diff --git a/src/lib/eo/eo_ptr_indirection.c b/src/lib/eo/eo_ptr_indirection.c
index 3bb28c1..ee55901 100644
--- a/src/lib/eo/eo_ptr_indirection.c
+++ b/src/lib/eo/eo_ptr_indirection.c
@@ -3,507 +3,15 @@
3#endif 3#endif
4 4
5#include "eo_ptr_indirection.h" 5#include "eo_ptr_indirection.h"
6#include <assert.h>
7#ifdef __linux__
8#include <sys/types.h>
9#include <sys/stat.h>
10#include <fcntl.h>
11#include <sys/mman.h>
12#endif
13
14/* Start of pointer indirection:
15 *
16 * This feature is responsible of hiding from the developer the real pointer of
17 * the Eo object to supply a better memory management by preventing bad usage
18 * of the pointers.
19 *
20 * Eo * is no more a pointer but indexes to an entry into an ids table.
21 * For a better memory usage:
22 * - a tree structure is used, composed of a top level table pointing at
23 * mid tables pointing at tables composed of entries.
24 * - tables are allocated when needed (i.e no more empty entries in allocated tables.
25 * - empty tables are freed, except one kept as spare table.
26 *
27 * An Eo id is contructed by bits manipulation of table indexes and a generation.
28 *
29 * id = Mid Table | Table | Entry | Generation
30 *
31 * Generation helps finding abuse of ids. When an entry is assigned to an
32 * object, a generation is inserted into the id. If the developer uses this id
33 * although the object is freed and another one has replaced it into the same
34 * entry of the table, the generation will be different and an error will
35 * occur when accessing with the old id.
36 *
37 * Each Table is composed of:
38 * - an index 'start' indicating which free entry is the next one to use.
39 * - 2 indexes 'fifo_head' and 'fifo_tail' defining a fifo,
40 * that will help us to store the entries to be reused. It stores only the
41 * entries that have been used at least one time. The entries that have
42 * never been used are "pointed" by the start parameter.
43 * - entries composed of:
44 * - a pointer to the object
45 * - an index 'next_in_fifo' used to chain the free entries in the fifo
46 * - a flag indicating if the entry is active
47 * - a generation assigned to the object
48 *
49 * When an entry is searched into a table, we first use one of the entries that
50 * has never been used. If there is none, we try to pop from the fifo.
51 * If a such entry doesn't exist, we pass to the next table.
52 * When an entry is found, we reserve it to the object pointer
53 * then contruct and return the related Eo id.
54 *
55 * Assigning all the entries of a table before trying to reuse them from
56 * the fifo ensures that we are not going to soon recycle a released entry,
57 * thus minimize the risks of an aggressive del() then use() on a single entry.
58 *
59 * The indexes and a reference to the last table which served an entry is kept
60 * and is reused prior to the others untill it is full.
61 * When an object is freed, the entry into the table is released by appending
62 * it to the fifo.
63 */
64
65#if SIZEOF_UINTPTR_T == 4
66/* 32 bits */
67# define BITS_MID_TABLE_ID 5
68# define BITS_TABLE_ID 5
69# define BITS_ENTRY_ID 12
70# define BITS_GENERATION_COUNTER 10
71# define DROPPED_TABLES 0
72# define DROPPED_ENTRIES 4
73typedef int16_t Table_Index;
74typedef uint16_t Generation_Counter;
75#else
76/* 64 bits */
77# define BITS_MID_TABLE_ID 11
78# define BITS_TABLE_ID 11
79# define BITS_ENTRY_ID 12
80# define BITS_GENERATION_COUNTER 30
81# define DROPPED_TABLES 2
82# define DROPPED_ENTRIES 3
83typedef int16_t Table_Index;
84typedef uint32_t Generation_Counter;
85#endif
86
87/* Shifts macros to manipulate the Eo id */
88#define SHIFT_MID_TABLE_ID (BITS_TABLE_ID + \
89 BITS_ENTRY_ID + BITS_GENERATION_COUNTER)
90#define SHIFT_TABLE_ID (BITS_ENTRY_ID + BITS_GENERATION_COUNTER)
91#define SHIFT_ENTRY_ID (BITS_GENERATION_COUNTER)
92
93/* Maximum ranges - a few tables and entries are dropped to minimize the amount
94 * of wasted bytes, see _eo_id_mem_alloc */
95#define MAX_MID_TABLE_ID (1 << BITS_MID_TABLE_ID)
96#define MAX_TABLE_ID ((1 << BITS_TABLE_ID) - DROPPED_TABLES )
97#define MAX_ENTRY_ID ((1 << BITS_ENTRY_ID) - DROPPED_ENTRIES)
98#define MAX_GENERATIONS (1 << BITS_GENERATION_COUNTER)
99
100/* Masks */
101#define MASK_MID_TABLE_ID (MAX_MID_TABLE_ID - 1)
102#define MASK_TABLE_ID ((1 << BITS_TABLE_ID) - 1)
103#define MASK_ENTRY_ID ((1 << BITS_ENTRY_ID) - 1)
104#define MASK_GENERATIONS (MAX_GENERATIONS - 1)
105
106#define MEM_HEADER_SIZE 16
107#define MEM_PAGE_SIZE 4096
108#define MEM_MAGIC 0x3f61ec8a
109
110typedef struct _Mem_Header
111{
112 size_t size;
113 size_t magic;
114} Mem_Header;
115
116static void *
117_eo_id_mem_alloc(size_t size)
118{
119#ifdef __linux__
120 void *ptr;
121 Mem_Header *hdr;
122 size_t newsize;
123 newsize = MEM_PAGE_SIZE * ((size + MEM_HEADER_SIZE + MEM_PAGE_SIZE - 1) /
124 MEM_PAGE_SIZE);
125 ptr = mmap(NULL, newsize, PROT_READ | PROT_WRITE,
126 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
127 if (ptr == MAP_FAILED)
128 {
129 ERR("mmap of eo id table region failed!");
130 return NULL;
131 }
132 hdr = ptr;
133 hdr->size = newsize;
134 hdr->magic = MEM_MAGIC;
135 /* DBG("asked:%lu allocated:%lu wasted:%lu bytes", size, newsize, (newsize - size)); */
136 return (void *)(((unsigned char *)ptr) + MEM_HEADER_SIZE);
137#else
138 return malloc(size);
139#endif
140}
141
142static void *
143_eo_id_mem_calloc(size_t num, size_t size)
144{
145 void *ptr = _eo_id_mem_alloc(num * size);
146 if (!ptr) return NULL;
147 memset(ptr, 0, num * size);
148 return ptr;
149}
150
151static void
152_eo_id_mem_free(void *ptr)
153{
154#ifdef __linux__
155 Mem_Header *hdr;
156 if (!ptr) return;
157 hdr = (Mem_Header *)(((unsigned char *)ptr) - MEM_HEADER_SIZE);
158 if (hdr->magic != MEM_MAGIC)
159 {
160 ERR("unmap of eo table region has bad magic!");
161 return;
162 }
163 munmap(hdr, hdr->size);
164#else
165 free(ptr);
166#endif
167}
168
169#ifdef EINA_DEBUG_MALLOC
170static void
171_eo_id_mem_protect(void *ptr, Eina_Bool may_not_write)
172{
173# ifdef __linux__
174 Mem_Header *hdr;
175 if (!ptr) return;
176 hdr = (Mem_Header *)(((unsigned char *)ptr) - MEM_HEADER_SIZE);
177 if (hdr->magic != MEM_MAGIC)
178 {
179 ERR("mprotect of eo table region has bad magic!");
180 return;
181 }
182 mprotect(hdr, hdr->size, PROT_READ | ( may_not_write ? 0 : PROT_WRITE) );
183# endif
184}
185# define PROTECT(_ptr_) _eo_id_mem_protect((_ptr_), EINA_TRUE)
186# define UNPROTECT(_ptr_) _eo_id_mem_protect((_ptr_), EINA_FALSE)
187#else
188# define PROTECT(_ptr_)
189# define UNPROTECT(_ptr_)
190#endif
191
192/* Entry */
193typedef struct
194{
195 /* Pointer to the object */
196 _Eo *ptr;
197 /* Indicates where to find the next entry to recycle */
198 Table_Index next_in_fifo;
199 /* Active flag */
200 unsigned int active : 1;
201 /* Generation */
202 unsigned int generation : BITS_GENERATION_COUNTER;
203
204} _Eo_Id_Entry;
205
206/* Table */
207typedef struct
208{
209 /* Indicates where start the "never used" entries */
210 Table_Index start;
211 /* Indicates where to find the next entry to recycle */
212 Table_Index fifo_head;
213 /* Indicates where to add an entry to recycle */
214 Table_Index fifo_tail;
215 /* Packed mid table and table indexes */
216 Eo_Id partial_id;
217 /* Counter of free entries */
218 unsigned int free_entries;
219 /* Entries of the table holding real pointers and generations */
220 _Eo_Id_Entry entries[MAX_ENTRY_ID];
221} _Eo_Ids_Table;
222 6
223/* Tables handling pointers indirection */ 7/* Tables handling pointers indirection */
224static _Eo_Ids_Table **_eo_ids_tables[MAX_MID_TABLE_ID] = { NULL }; 8_Eo_Ids_Table **_eo_ids_tables[MAX_MID_TABLE_ID] = { NULL };
225 9
226/* Current table used for following allocations */ 10/* Current table used for following allocations */
227static _Eo_Ids_Table *_current_table = NULL; 11_Eo_Ids_Table *_current_table = NULL;
228 12
229/* Spare empty table */ 13/* Spare empty table */
230static _Eo_Ids_Table *_empty_table = NULL; 14_Eo_Ids_Table *_empty_table = NULL;
231 15
232/* Next generation to use when assigning a new entry to a Eo pointer */ 16/* Next generation to use when assigning a new entry to a Eo pointer */
233Generation_Counter _eo_generation_counter = 0; 17Generation_Counter _eo_generation_counter = 0;
234
235/* Macro used to compose an Eo id */
236#define EO_COMPOSE_PARTIAL_ID(MID_TABLE, TABLE) \
237 (((Eo_Id)(MID_TABLE & MASK_MID_TABLE_ID) << SHIFT_MID_TABLE_ID) | \
238 ((Eo_Id)(TABLE & MASK_TABLE_ID) << SHIFT_TABLE_ID))
239
240#define EO_COMPOSE_FINAL_ID(PARTIAL_ID, ENTRY, GENERATION) \
241 (PARTIAL_ID | \
242 ((ENTRY & MASK_ENTRY_ID) << SHIFT_ENTRY_ID) | \
243 (GENERATION & MASK_GENERATIONS ))
244
245/* Macro to extract from an Eo id the indexes of the tables */
246#define EO_DECOMPOSE_ID(ID, MID_TABLE, TABLE, ENTRY, GENERATION) \
247 MID_TABLE = (ID >> SHIFT_MID_TABLE_ID) & MASK_MID_TABLE_ID; \
248 TABLE = (ID >> SHIFT_TABLE_ID) & MASK_TABLE_ID; \
249 ENTRY = (ID >> SHIFT_ENTRY_ID) & MASK_ENTRY_ID; \
250 GENERATION = ID & MASK_GENERATIONS;
251
252/* Macro used for readability */
253#define TABLE_FROM_IDS _eo_ids_tables[mid_table_id][table_id]
254
255_Eo *
256_eo_obj_pointer_get(const Eo_Id obj_id)
257{
258#ifdef HAVE_EO_ID
259 _Eo_Id_Entry *entry;
260 Generation_Counter generation;
261 Table_Index mid_table_id, table_id, entry_id;
262
263 EO_DECOMPOSE_ID(obj_id, mid_table_id, table_id, entry_id, generation);
264
265 /* Check the validity of the entry */
266 if (_eo_ids_tables[mid_table_id] && TABLE_FROM_IDS)
267 {
268 entry = &(TABLE_FROM_IDS->entries[entry_id]);
269 if (entry && entry->active && (entry->generation == generation))
270 return entry->ptr;
271 }
272
273 ERR("obj_id %p is not pointing to a valid object. Maybe it has already been freed.",
274 (void *)obj_id);
275
276 return NULL;
277#else
278 return (_Eo *)obj_id;
279#endif
280}
281
282static inline _Eo_Id_Entry *
283_get_available_entry(_Eo_Ids_Table *table)
284{
285 _Eo_Id_Entry *entry = NULL;
286
287 if (table->start != MAX_ENTRY_ID)
288 {
289 /* Serve never used entries first */
290 entry = &(table->entries[table->start]);
291 UNPROTECT(table);
292 table->start++;
293 table->free_entries--;
294 }
295 else if (table->fifo_head != -1)
296 {
297 /* Pop a free entry from the fifo */
298 entry = &(table->entries[table->fifo_head]);
299 UNPROTECT(table);
300 if (entry->next_in_fifo == -1)
301 table->fifo_head = table->fifo_tail = -1;
302 else
303 table->fifo_head = entry->next_in_fifo;
304 table->free_entries--;
305 }
306
307 return entry;
308}
309
310static inline _Eo_Id_Entry *
311_search_tables()
312{
313 _Eo_Ids_Table *table;
314 _Eo_Id_Entry *entry;
315
316 for (Table_Index mid_table_id = 0; mid_table_id < MAX_MID_TABLE_ID; mid_table_id++)
317 {
318 if (!_eo_ids_tables[mid_table_id])
319 {
320 /* Allocate a new intermediate table */
321 _eo_ids_tables[mid_table_id] = _eo_id_mem_calloc(MAX_TABLE_ID, sizeof(_Eo_Ids_Table*));
322 }
323
324 for (Table_Index table_id = 0; table_id < MAX_TABLE_ID; table_id++)
325 {
326 table = TABLE_FROM_IDS;
327
328 if (!table)
329 {
330 if (_empty_table)
331 {
332 /* Recycle the available empty table */
333 table = _empty_table;
334 _empty_table = NULL;
335 UNPROTECT(table);
336 }
337 else
338 {
339 /* Allocate a new table */
340 table = _eo_id_mem_calloc(1, sizeof(_Eo_Ids_Table));
341 }
342 /* Initialize the table and reserve the first entry */
343 table->start = 1;
344 table->free_entries = MAX_ENTRY_ID - 1;
345 table->fifo_head = table->fifo_tail = -1;
346 table->partial_id = EO_COMPOSE_PARTIAL_ID(mid_table_id, table_id);
347 entry = &(table->entries[0]);
348 UNPROTECT(_eo_ids_tables[mid_table_id]);
349 TABLE_FROM_IDS = table;
350 PROTECT(_eo_ids_tables[mid_table_id]);
351 }
352 else
353 entry = _get_available_entry(table);
354
355 if (entry)
356 {
357 /* Store table info into current table */
358 _current_table = table;
359 return entry;
360 }
361 }
362 }
363
364 ERR("no more available entries to store eo objects");
365 _current_table = NULL;
366 return NULL;
367}
368
369Eo_Id
370_eo_id_allocate(const _Eo *obj)
371{
372#ifdef HAVE_EO_ID
373 _Eo_Id_Entry *entry = NULL;
374
375 if (_current_table)
376 entry = _get_available_entry(_current_table);
377
378 if (!entry)
379 {
380 entry = _search_tables();
381 if (!entry)
382 return 0;
383 }
384
385 /* [1;max-1] thus we never generate an Eo_Id equal to 0 */
386 _eo_generation_counter++;
387 if (_eo_generation_counter == MAX_GENERATIONS)
388 _eo_generation_counter = 1;
389 /* Fill the entry and return it's Eo Id */
390 entry->ptr = (_Eo *)obj;
391 entry->active = 1;
392 entry->generation = _eo_generation_counter;
393 PROTECT(_current_table);
394 return EO_COMPOSE_FINAL_ID(_current_table->partial_id,
395 (entry - _current_table->entries),
396 entry->generation);
397#else
398 return (Eo_Id)obj;
399#endif
400}
401
402void
403_eo_id_release(const Eo_Id obj_id)
404{
405#ifdef HAVE_EO_ID
406 _Eo_Ids_Table *table;
407 _Eo_Id_Entry *entry;
408 Generation_Counter generation;
409 Table_Index mid_table_id, table_id, entry_id;
410 EO_DECOMPOSE_ID(obj_id, mid_table_id, table_id, entry_id, generation);
411
412 /* Check the validity of the entry */
413 if (_eo_ids_tables[mid_table_id] && (table = TABLE_FROM_IDS))
414 {
415 entry = &(table->entries[entry_id]);
416 if (entry && entry->active && (entry->generation == generation))
417 {
418 UNPROTECT(table);
419 table->free_entries++;
420 /* Disable the entry */
421 entry->active = 0;
422 entry->next_in_fifo = -1;
423 /* Push the entry into the fifo */
424 if (table->fifo_tail == -1)
425 {
426 table->fifo_head = table->fifo_tail = entry_id;
427 }
428 else
429 {
430 table->entries[table->fifo_tail].next_in_fifo = entry_id;
431 table->fifo_tail = entry_id;
432 }
433 PROTECT(table);
434 if (table->free_entries == MAX_ENTRY_ID)
435 {
436 UNPROTECT(_eo_ids_tables[mid_table_id]);
437 TABLE_FROM_IDS = NULL;
438 PROTECT(_eo_ids_tables[mid_table_id]);
439 /* Recycle or free the empty table */
440 if (!_empty_table)
441 _empty_table = table;
442 else
443 _eo_id_mem_free(table);
444 if (_current_table == table)
445 _current_table = NULL;
446 }
447 return;
448 }
449 }
450
451 ERR("obj_id %p is not pointing to a valid object. Maybe it has already been freed.", (void *)obj_id);
452#else
453 (void) obj_id;
454#endif
455}
456
457void
458_eo_free_ids_tables()
459{
460 for (Table_Index mid_table_id = 0; mid_table_id < MAX_MID_TABLE_ID; mid_table_id++)
461 {
462 if (_eo_ids_tables[mid_table_id])
463 {
464 for (Table_Index table_id = 0; table_id < MAX_TABLE_ID; table_id++)
465 {
466 if (TABLE_FROM_IDS)
467 {
468 _eo_id_mem_free(TABLE_FROM_IDS);
469 }
470 }
471 _eo_id_mem_free(_eo_ids_tables[mid_table_id]);
472 }
473 _eo_ids_tables[mid_table_id] = NULL;
474 }
475 if (_empty_table) _eo_id_mem_free(_empty_table);
476 _empty_table = _current_table = NULL;
477}
478
479#ifdef EFL_DEBUG
480void
481_eo_print()
482{
483 _Eo_Id_Entry *entry;
484 unsigned long obj_number = 0;
485 for (Table_Index mid_table_id = 0; mid_table_id < MAX_MID_TABLE_ID; mid_table_id++)
486 {
487 if (_eo_ids_tables[mid_table_id])
488 {
489 for (Table_Index table_id = 0; table_id < MAX_TABLE_ID; table_id++)
490 {
491 if (TABLE_FROM_IDS)
492 {
493 for (Table_Index entry_id = 0; entry_id < MAX_ENTRY_ID; entry_id++)
494 {
495 entry = &(TABLE_FROM_IDS->entries[entry_id]);
496 if (entry->active)
497 {
498 printf("%ld: %p -> (%p, %p, %p, %p)\n", obj_number++,
499 entry->ptr,
500 (void *)mid_table_id, (void *)table_id, (void *)entry_id,
501 (void *)entry->generation);
502 }
503 }
504 }
505 }
506 }
507 }
508}
509#endif
diff --git a/src/lib/eo/eo_ptr_indirection.h b/src/lib/eo/eo_ptr_indirection.h
index c8f4e9c..cb890e7 100644
--- a/src/lib/eo/eo_ptr_indirection.h
+++ b/src/lib/eo/eo_ptr_indirection.h
@@ -44,5 +44,7 @@
44void _eo_print(); 44void _eo_print();
45#endif 45#endif
46 46
47#include "eo_ptr_indirection.x"
48
47#endif 49#endif
48 50
diff --git a/src/lib/eo/eo_ptr_indirection.x b/src/lib/eo/eo_ptr_indirection.x
new file mode 100644
index 0000000..3bec84f
--- /dev/null
+++ b/src/lib/eo/eo_ptr_indirection.x
@@ -0,0 +1,504 @@
1#include <assert.h>
2#ifdef __linux__
3#include <sys/types.h>
4#include <sys/stat.h>
5#include <fcntl.h>
6#include <sys/mman.h>
7#endif
8
9/* Start of pointer indirection:
10 *
11 * This feature is responsible of hiding from the developer the real pointer of
12 * the Eo object to supply a better memory management by preventing bad usage
13 * of the pointers.
14 *
15 * Eo * is no more a pointer but indexes to an entry into an ids table.
16 * For a better memory usage:
17 * - a tree structure is used, composed of a top level table pointing at
18 * mid tables pointing at tables composed of entries.
19 * - tables are allocated when needed (i.e no more empty entries in allocated tables.
20 * - empty tables are freed, except one kept as spare table.
21 *
22 * An Eo id is contructed by bits manipulation of table indexes and a generation.
23 *
24 * id = Mid Table | Table | Entry | Generation
25 *
26 * Generation helps finding abuse of ids. When an entry is assigned to an
27 * object, a generation is inserted into the id. If the developer uses this id
28 * although the object is freed and another one has replaced it into the same
29 * entry of the table, the generation will be different and an error will
30 * occur when accessing with the old id.
31 *
32 * Each Table is composed of:
33 * - an index 'start' indicating which free entry is the next one to use.
34 * - 2 indexes 'fifo_head' and 'fifo_tail' defining a fifo,
35 * that will help us to store the entries to be reused. It stores only the
36 * entries that have been used at least one time. The entries that have
37 * never been used are "pointed" by the start parameter.
38 * - entries composed of:
39 * - a pointer to the object
40 * - an index 'next_in_fifo' used to chain the free entries in the fifo
41 * - a flag indicating if the entry is active
42 * - a generation assigned to the object
43 *
44 * When an entry is searched into a table, we first use one of the entries that
45 * has never been used. If there is none, we try to pop from the fifo.
46 * If a such entry doesn't exist, we pass to the next table.
47 * When an entry is found, we reserve it to the object pointer
48 * then contruct and return the related Eo id.
49 *
50 * Assigning all the entries of a table before trying to reuse them from
51 * the fifo ensures that we are not going to soon recycle a released entry,
52 * thus minimize the risks of an aggressive del() then use() on a single entry.
53 *
54 * The indexes and a reference to the last table which served an entry is kept
55 * and is reused prior to the others untill it is full.
56 * When an object is freed, the entry into the table is released by appending
57 * it to the fifo.
58 */
59
60#if SIZEOF_UINTPTR_T == 4
61/* 32 bits */
62# define BITS_MID_TABLE_ID 5
63# define BITS_TABLE_ID 5
64# define BITS_ENTRY_ID 12
65# define BITS_GENERATION_COUNTER 10
66# define DROPPED_TABLES 0
67# define DROPPED_ENTRIES 4
68typedef int16_t Table_Index;
69typedef uint16_t Generation_Counter;
70#else
71/* 64 bits */
72# define BITS_MID_TABLE_ID 11
73# define BITS_TABLE_ID 11
74# define BITS_ENTRY_ID 12
75# define BITS_GENERATION_COUNTER 30
76# define DROPPED_TABLES 2
77# define DROPPED_ENTRIES 3
78typedef int16_t Table_Index;
79typedef uint32_t Generation_Counter;
80#endif
81
82/* Shifts macros to manipulate the Eo id */
83#define SHIFT_MID_TABLE_ID (BITS_TABLE_ID + \
84 BITS_ENTRY_ID + BITS_GENERATION_COUNTER)
85#define SHIFT_TABLE_ID (BITS_ENTRY_ID + BITS_GENERATION_COUNTER)
86#define SHIFT_ENTRY_ID (BITS_GENERATION_COUNTER)
87
88/* Maximum ranges - a few tables and entries are dropped to minimize the amount
89 * of wasted bytes, see _eo_id_mem_alloc */
90#define MAX_MID_TABLE_ID (1 << BITS_MID_TABLE_ID)
91#define MAX_TABLE_ID ((1 << BITS_TABLE_ID) - DROPPED_TABLES )
92#define MAX_ENTRY_ID ((1 << BITS_ENTRY_ID) - DROPPED_ENTRIES)
93#define MAX_GENERATIONS (1 << BITS_GENERATION_COUNTER)
94
95/* Masks */
96#define MASK_MID_TABLE_ID (MAX_MID_TABLE_ID - 1)
97#define MASK_TABLE_ID ((1 << BITS_TABLE_ID) - 1)
98#define MASK_ENTRY_ID ((1 << BITS_ENTRY_ID) - 1)
99#define MASK_GENERATIONS (MAX_GENERATIONS - 1)
100
101#define MEM_HEADER_SIZE 16
102#define MEM_PAGE_SIZE 4096
103#define MEM_MAGIC 0x3f61ec8a
104
105typedef struct _Mem_Header
106{
107 size_t size;
108 size_t magic;
109} Mem_Header;
110
111static void *
112_eo_id_mem_alloc(size_t size)
113{
114#ifdef __linux__
115 void *ptr;
116 Mem_Header *hdr;
117 size_t newsize;
118 newsize = MEM_PAGE_SIZE * ((size + MEM_HEADER_SIZE + MEM_PAGE_SIZE - 1) /
119 MEM_PAGE_SIZE);
120 ptr = mmap(NULL, newsize, PROT_READ | PROT_WRITE,
121 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
122 if (ptr == MAP_FAILED)
123 {
124 ERR("mmap of eo id table region failed!");
125 return NULL;
126 }
127 hdr = ptr;
128 hdr->size = newsize;
129 hdr->magic = MEM_MAGIC;
130 /* DBG("asked:%lu allocated:%lu wasted:%lu bytes", size, newsize, (newsize - size)); */
131 return (void *)(((unsigned char *)ptr) + MEM_HEADER_SIZE);
132#else
133 return malloc(size);
134#endif
135}
136
137static void *
138_eo_id_mem_calloc(size_t num, size_t size)
139{
140 void *ptr = _eo_id_mem_alloc(num * size);
141 if (!ptr) return NULL;
142 memset(ptr, 0, num * size);
143 return ptr;
144}
145
146static void
147_eo_id_mem_free(void *ptr)
148{
149#ifdef __linux__
150 Mem_Header *hdr;
151 if (!ptr) return;
152 hdr = (Mem_Header *)(((unsigned char *)ptr) - MEM_HEADER_SIZE);
153 if (hdr->magic != MEM_MAGIC)
154 {
155 ERR("unmap of eo table region has bad magic!");
156 return;
157 }
158 munmap(hdr, hdr->size);
159#else
160 free(ptr);
161#endif
162}
163
164#ifdef EINA_DEBUG_MALLOC
165static void
166_eo_id_mem_protect(void *ptr, Eina_Bool may_not_write)
167{
168# ifdef __linux__
169 Mem_Header *hdr;
170 if (!ptr) return;
171 hdr = (Mem_Header *)(((unsigned char *)ptr) - MEM_HEADER_SIZE);
172 if (hdr->magic != MEM_MAGIC)
173 {
174 ERR("mprotect of eo table region has bad magic!");
175 return;
176 }
177 mprotect(hdr, hdr->size, PROT_READ | ( may_not_write ? 0 : PROT_WRITE) );
178# endif
179}
180# define PROTECT(_ptr_) _eo_id_mem_protect((_ptr_), EINA_TRUE)
181# define UNPROTECT(_ptr_) _eo_id_mem_protect((_ptr_), EINA_FALSE)
182#else
183# define PROTECT(_ptr_)
184# define UNPROTECT(_ptr_)
185#endif
186
187/* Entry */
188typedef struct
189{
190 /* Pointer to the object */
191 _Eo *ptr;
192 /* Indicates where to find the next entry to recycle */
193 Table_Index next_in_fifo;
194 /* Active flag */
195 unsigned int active : 1;
196 /* Generation */
197 unsigned int generation : BITS_GENERATION_COUNTER;
198
199} _Eo_Id_Entry;
200
201/* Table */
202typedef struct
203{
204 /* Indicates where start the "never used" entries */
205 Table_Index start;
206 /* Indicates where to find the next entry to recycle */
207 Table_Index fifo_head;
208 /* Indicates where to add an entry to recycle */
209 Table_Index fifo_tail;
210 /* Packed mid table and table indexes */
211 Eo_Id partial_id;
212 /* Counter of free entries */
213 unsigned int free_entries;
214 /* Entries of the table holding real pointers and generations */
215 _Eo_Id_Entry entries[MAX_ENTRY_ID];
216} _Eo_Ids_Table;
217
218/* Tables handling pointers indirection */
219extern _Eo_Ids_Table **_eo_ids_tables[MAX_MID_TABLE_ID];
220
221/* Current table used for following allocations */
222extern _Eo_Ids_Table *_current_table;
223
224/* Spare empty table */
225extern _Eo_Ids_Table *_empty_table;
226
227/* Next generation to use when assigning a new entry to a Eo pointer */
228extern Generation_Counter _eo_generation_counter;
229
230/* Macro used to compose an Eo id */
231#define EO_COMPOSE_PARTIAL_ID(MID_TABLE, TABLE) \
232 (((Eo_Id)(MID_TABLE & MASK_MID_TABLE_ID) << SHIFT_MID_TABLE_ID) | \
233 ((Eo_Id)(TABLE & MASK_TABLE_ID) << SHIFT_TABLE_ID))
234
235#define EO_COMPOSE_FINAL_ID(PARTIAL_ID, ENTRY, GENERATION) \
236 (PARTIAL_ID | \
237 ((ENTRY & MASK_ENTRY_ID) << SHIFT_ENTRY_ID) | \
238 (GENERATION & MASK_GENERATIONS ))
239
240/* Macro to extract from an Eo id the indexes of the tables */
241#define EO_DECOMPOSE_ID(ID, MID_TABLE, TABLE, ENTRY, GENERATION) \
242 MID_TABLE = (ID >> SHIFT_MID_TABLE_ID) & MASK_MID_TABLE_ID; \
243 TABLE = (ID >> SHIFT_TABLE_ID) & MASK_TABLE_ID; \
244 ENTRY = (ID >> SHIFT_ENTRY_ID) & MASK_ENTRY_ID; \
245 GENERATION = ID & MASK_GENERATIONS;
246
247/* Macro used for readability */
248#define TABLE_FROM_IDS _eo_ids_tables[mid_table_id][table_id]
249
250static inline _Eo *
251_eo_obj_pointer_get(const Eo_Id obj_id)
252{
253#ifdef HAVE_EO_ID
254 _Eo_Id_Entry *entry;
255 Generation_Counter generation;
256 Table_Index mid_table_id, table_id, entry_id;
257
258 EO_DECOMPOSE_ID(obj_id, mid_table_id, table_id, entry_id, generation);
259
260 /* Check the validity of the entry */
261 if (_eo_ids_tables[mid_table_id] && TABLE_FROM_IDS)
262 {
263 entry = &(TABLE_FROM_IDS->entries[entry_id]);
264 if (entry && entry->active && (entry->generation == generation))
265 return entry->ptr;
266 }
267
268 ERR("obj_id %p is not pointing to a valid object. Maybe it has already been freed.",
269 (void *)obj_id);
270
271 return NULL;
272#else
273 return (_Eo *)obj_id;
274#endif
275}
276
277static inline _Eo_Id_Entry *
278_get_available_entry(_Eo_Ids_Table *table)
279{
280 _Eo_Id_Entry *entry = NULL;
281
282 if (table->start != MAX_ENTRY_ID)
283 {
284 /* Serve never used entries first */
285 entry = &(table->entries[table->start]);
286 UNPROTECT(table);
287 table->start++;
288 table->free_entries--;
289 }
290 else if (table->fifo_head != -1)
291 {
292 /* Pop a free entry from the fifo */
293 entry = &(table->entries[table->fifo_head]);
294 UNPROTECT(table);
295 if (entry->next_in_fifo == -1)
296 table->fifo_head = table->fifo_tail = -1;
297 else
298 table->fifo_head = entry->next_in_fifo;
299 table->free_entries--;
300 }
301
302 return entry;
303}
304
305static inline _Eo_Id_Entry *
306_search_tables(void)
307{
308 _Eo_Ids_Table *table;
309 _Eo_Id_Entry *entry;
310
311 for (Table_Index mid_table_id = 0; mid_table_id < MAX_MID_TABLE_ID; mid_table_id++)
312 {
313 if (!_eo_ids_tables[mid_table_id])
314 {
315 /* Allocate a new intermediate table */
316 _eo_ids_tables[mid_table_id] = _eo_id_mem_calloc(MAX_TABLE_ID, sizeof(_Eo_Ids_Table*));
317 }
318
319 for (Table_Index table_id = 0; table_id < MAX_TABLE_ID; table_id++)
320 {
321 table = TABLE_FROM_IDS;
322
323 if (!table)
324 {
325 if (_empty_table)
326 {
327 /* Recycle the available empty table */
328 table = _empty_table;
329 _empty_table = NULL;
330 UNPROTECT(table);
331 }
332 else
333 {
334 /* Allocate a new table */
335 table = _eo_id_mem_calloc(1, sizeof(_Eo_Ids_Table));
336 }
337 /* Initialize the table and reserve the first entry */
338 table->start = 1;
339 table->free_entries = MAX_ENTRY_ID - 1;
340 table->fifo_head = table->fifo_tail = -1;
341 table->partial_id = EO_COMPOSE_PARTIAL_ID(mid_table_id, table_id);
342 entry = &(table->entries[0]);
343 UNPROTECT(_eo_ids_tables[mid_table_id]);
344 TABLE_FROM_IDS = table;
345 PROTECT(_eo_ids_tables[mid_table_id]);
346 }
347 else
348 entry = _get_available_entry(table);
349
350 if (entry)
351 {
352 /* Store table info into current table */
353 _current_table = table;
354 return entry;
355 }
356 }
357 }
358
359 ERR("no more available entries to store eo objects");
360 _current_table = NULL;
361 return NULL;
362}
363
364static inline Eo_Id
365_eo_id_allocate(const _Eo *obj)
366{
367#ifdef HAVE_EO_ID
368 _Eo_Id_Entry *entry = NULL;
369
370 if (_current_table)
371 entry = _get_available_entry(_current_table);
372
373 if (!entry)
374 {
375 entry = _search_tables();
376 if (!entry)
377 return 0;
378 }
379
380 /* [1;max-1] thus we never generate an Eo_Id equal to 0 */
381 _eo_generation_counter++;
382 if (_eo_generation_counter == MAX_GENERATIONS)
383 _eo_generation_counter = 1;
384 /* Fill the entry and return it's Eo Id */
385 entry->ptr = (_Eo *)obj;
386 entry->active = 1;
387 entry->generation = _eo_generation_counter;
388 PROTECT(_current_table);
389 return EO_COMPOSE_FINAL_ID(_current_table->partial_id,
390 (entry - _current_table->entries),
391 entry->generation);
392#else
393 return (Eo_Id)obj;
394#endif
395}
396
397static inline void
398_eo_id_release(const Eo_Id obj_id)
399{
400#ifdef HAVE_EO_ID
401 _Eo_Ids_Table *table;
402 _Eo_Id_Entry *entry;
403 Generation_Counter generation;
404 Table_Index mid_table_id, table_id, entry_id;
405 EO_DECOMPOSE_ID(obj_id, mid_table_id, table_id, entry_id, generation);
406
407 /* Check the validity of the entry */
408 if (_eo_ids_tables[mid_table_id] && (table = TABLE_FROM_IDS))
409 {
410 entry = &(table->entries[entry_id]);
411 if (entry && entry->active && (entry->generation == generation))
412 {
413 UNPROTECT(table);
414 table->free_entries++;
415 /* Disable the entry */
416 entry->active = 0;
417 entry->next_in_fifo = -1;
418 /* Push the entry into the fifo */
419 if (table->fifo_tail == -1)
420 {
421 table->fifo_head = table->fifo_tail = entry_id;
422 }
423 else
424 {
425 table->entries[table->fifo_tail].next_in_fifo = entry_id;
426 table->fifo_tail = entry_id;
427 }
428 PROTECT(table);
429 if (table->free_entries == MAX_ENTRY_ID)
430 {
431 UNPROTECT(_eo_ids_tables[mid_table_id]);
432 TABLE_FROM_IDS = NULL;
433 PROTECT(_eo_ids_tables[mid_table_id]);
434 /* Recycle or free the empty table */
435 if (!_empty_table)
436 _empty_table = table;
437 else
438 _eo_id_mem_free(table);
439 if (_current_table == table)
440 _current_table = NULL;
441 }
442 return;
443 }
444 }
445
446 ERR("obj_id %p is not pointing to a valid object. Maybe it has already been freed.", (void *)obj_id);
447#else
448 (void) obj_id;
449#endif
450}
451
452static inline void
453_eo_free_ids_tables(void)
454{
455 for (Table_Index mid_table_id = 0; mid_table_id < MAX_MID_TABLE_ID; mid_table_id++)
456 {
457 if (_eo_ids_tables[mid_table_id])
458 {
459 for (Table_Index table_id = 0; table_id < MAX_TABLE_ID; table_id++)
460 {
461 if (TABLE_FROM_IDS)
462 {
463 _eo_id_mem_free(TABLE_FROM_IDS);
464 }
465 }
466 _eo_id_mem_free(_eo_ids_tables[mid_table_id]);
467 }
468 _eo_ids_tables[mid_table_id] = NULL;
469 }
470 if (_empty_table) _eo_id_mem_free(_empty_table);
471 _empty_table = _current_table = NULL;
472}
473
474#ifdef EFL_DEBUG
475static inline void
476_eo_print(void)
477{
478 _Eo_Id_Entry *entry;
479 unsigned long obj_number = 0;
480 for (Table_Index mid_table_id = 0; mid_table_id < MAX_MID_TABLE_ID; mid_table_id++)
481 {
482 if (_eo_ids_tables[mid_table_id])
483 {
484 for (Table_Index table_id = 0; table_id < MAX_TABLE_ID; table_id++)
485 {
486 if (TABLE_FROM_IDS)
487 {
488 for (Table_Index entry_id = 0; entry_id < MAX_ENTRY_ID; entry_id++)
489 {
490 entry = &(TABLE_FROM_IDS->entries[entry_id]);
491 if (entry->active)
492 {
493 printf("%ld: %p -> (%p, %p, %p, %p)\n", obj_number++,
494 entry->ptr,
495 (void *)mid_table_id, (void *)table_id, (void *)entry_id,
496 (void *)entry->generation);
497 }
498 }
499 }
500 }
501 }
502 }
503}
504#endif