summaryrefslogtreecommitdiff
path: root/src/lib/eo/eo_ptr_indirection.c
diff options
context:
space:
mode:
authorJérémy Zurcher <jeremy@asynk.ch>2013-05-03 21:28:32 +0200
committerJérémy Zurcher <jeremy@asynk.ch>2013-05-03 21:28:32 +0200
commitf769128dcad91da002529ee9e2a27f82c828461d (patch)
treed5747d6a06965b5a513b5d282bcad1c093e6e0f6 /src/lib/eo/eo_ptr_indirection.c
parent88cf0cf460e35902f26c11c4229934559c9a8ecb (diff)
eo ptr ind: pack memory, use in mmap fifo as recycle trash
- pack active flag and generation nbr in an _Eo_Id_Entry struct - replace Eina_Trash with a fifo which lives in mmaped memory owned by eo_id. - fifo uses indexes instead of pointers to spare memory - never used entries are served first, then those in the fifo are reused, thus we ensure that a freed entry won't soon be reused.
Diffstat (limited to 'src/lib/eo/eo_ptr_indirection.c')
-rw-r--r--src/lib/eo/eo_ptr_indirection.c150
1 files changed, 92 insertions, 58 deletions
diff --git a/src/lib/eo/eo_ptr_indirection.c b/src/lib/eo/eo_ptr_indirection.c
index 32e3781..7b27cae 100644
--- a/src/lib/eo/eo_ptr_indirection.c
+++ b/src/lib/eo/eo_ptr_indirection.c
@@ -3,6 +3,7 @@
3#endif 3#endif
4 4
5#include "eo_ptr_indirection.h" 5#include "eo_ptr_indirection.h"
6#include <assert.h>
6#ifdef __linux__ 7#ifdef __linux__
7#include <sys/types.h> 8#include <sys/types.h>
8#include <sys/stat.h> 9#include <sys/stat.h>
@@ -32,22 +33,27 @@
32 * occur when accessing with the old id. 33 * occur when accessing with the old id.
33 * 34 *
34 * Each table is composed of: 35 * Each table is composed of:
35 * - entries composed of
36 * - a pointer to the object
37 * - a flag indicating if the entry is active
38 * - a generation assigned to the object
39 * - an index 'start' indicating which entry is the next one to use. 36 * - an index 'start' indicating which entry is the next one to use.
40 * - a queue that will help us to store the unused entries. It stores only the 37 * - 2 indexes 'queue_head' and 'queue_tail' defining a queue (fifo),
38 * 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 39 * entries that have been used at least one time. The entries that have
42 * never been used are "pointed" by the start parameter. 40 * never been used are "pointed" by the start parameter.
43 * When an entry is searched into a table, we first try to pop from the 41 * - entries composed of:
44 * queue. If a NULL value is returned, we have to use one of the entries that 42 * - a pointer to the object
45 * have never been used. If a such entry doesn't exist, we pass to the next 43 * - a flag indicating if the entry is active
46 * table. Otherwise, we reserve this entry to the object pointer and create 44 * - a generation assigned to the object
45 * - an index 'next_in_queue' used to chain the entries in the queue
46 * When an entry is searched into a table, we first use one of the entries that
47 * has never been used. If there is none, we try to pop from the queue.
48 * If a such entry doesn't exist, we pass to the next table.
49 * When an entry is found, we reserve it to the object pointer and create
47 * the id with the table id, the intermediate table id, the entry and a 50 * the id with the table id, the intermediate table id, the entry and a
48 * generation. 51 * generation.
49 * When an object is freed, the entry into the table is released by pushing 52 * When an object is freed, the entry into the table is released by appending
50 * it into the queue. 53 * it to the queue.
54 * Assigning all the entries of a table before trying to reuse them from
55 * the fifo ensures that we are not going to soon recycle a released entry,
56 * thus minimize the risks of an aggressive del() then use() on a single entry.
51 */ 57 */
52 58
53#if SIZEOF_UINTPTR_T == 4 59#if SIZEOF_UINTPTR_T == 4
@@ -56,16 +62,18 @@
56# define BITS_FOR_IDS_INTER_TABLE 5 62# define BITS_FOR_IDS_INTER_TABLE 5
57# define BITS_FOR_ID_IN_TABLE 12 63# define BITS_FOR_ID_IN_TABLE 12
58# define BITS_FOR_GENERATION_COUNTER 10 64# define BITS_FOR_GENERATION_COUNTER 10
65typedef int16_t Table_Index;
66typedef uint16_t Generation_Counter;
59#else 67#else
60/* 64 bits */ 68/* 64 bits */
61# define BITS_FOR_IDS_TABLE 11 69# define BITS_FOR_IDS_TABLE 11
62# define BITS_FOR_IDS_INTER_TABLE 11 70# define BITS_FOR_IDS_INTER_TABLE 11
63# define BITS_FOR_ID_IN_TABLE 12 71# define BITS_FOR_ID_IN_TABLE 12
64# define BITS_FOR_GENERATION_COUNTER 30 72# define BITS_FOR_GENERATION_COUNTER 30
73typedef int16_t Table_Index;
74typedef uint32_t Generation_Counter;
65#endif 75#endif
66 76
67typedef uintptr_t Table_Index;
68
69/* Shifts macros to manipulate the Eo id */ 77/* Shifts macros to manipulate the Eo id */
70#define SHIFT_FOR_IDS_TABLE \ 78#define SHIFT_FOR_IDS_TABLE \
71 (BITS_FOR_IDS_INTER_TABLE + BITS_FOR_ID_IN_TABLE + BITS_FOR_GENERATION_COUNTER) 79 (BITS_FOR_IDS_INTER_TABLE + BITS_FOR_ID_IN_TABLE + BITS_FOR_GENERATION_COUNTER)
@@ -152,6 +160,9 @@ typedef struct
152 unsigned int active : 1; 160 unsigned int active : 1;
153 /* Generation */ 161 /* Generation */
154 unsigned int generation : BITS_FOR_GENERATION_COUNTER; 162 unsigned int generation : BITS_FOR_GENERATION_COUNTER;
163 /* Indicates where to find the next entry to recycle */
164 Table_Index next_in_queue;
165
155} _Eo_Id_Entry; 166} _Eo_Id_Entry;
156 167
157/* Table */ 168/* Table */
@@ -159,31 +170,33 @@ typedef struct
159{ 170{
160 /* Entries of the table holding real pointers and generations */ 171 /* Entries of the table holding real pointers and generations */
161 _Eo_Id_Entry entries[MAX_IDS_PER_TABLE]; 172 _Eo_Id_Entry entries[MAX_IDS_PER_TABLE];
162 /* Queue to handle free entries */
163 Eina_Trash *queue;
164 /* Indicates where start the "never used" entries */ 173 /* Indicates where start the "never used" entries */
165 Table_Index start; 174 Table_Index start;
175 /* Indicates where to find the next entry to recycle */
176 Table_Index queue_head;
177 /* Indicates where to add an entry to recycle */
178 Table_Index queue_tail;
166} _Eo_Ids_Table; 179} _Eo_Ids_Table;
167 180
168/* Tables handling pointers indirection */ 181/* Tables handling pointers indirection */
169_Eo_Ids_Table **_eo_ids_tables[MAX_IDS_TABLES] = { NULL }; 182_Eo_Ids_Table **_eo_ids_tables[MAX_IDS_TABLES] = { NULL };
170 183
171/* Next generation to use when assigning a new entry to a Eo pointer */ 184/* Next generation to use when assigning a new entry to a Eo pointer */
172Table_Index _eo_generation_counter; 185Generation_Counter _eo_generation_counter;
173 186
174/* Macro used to compose an Eo id */ 187/* Macro used to compose an Eo id */
175#define EO_COMPOSE_ID(TABLE, INTER_TABLE, ENTRY, GENERATION) \ 188#define EO_COMPOSE_ID(TABLE, INTER_TABLE, ENTRY, GENERATION) \
176 (Eo_Id)(((TABLE & (MAX_IDS_TABLES - 1)) << SHIFT_FOR_IDS_TABLE) | \ 189 (((Eo_Id)(TABLE & (MAX_IDS_TABLES - 1)) << SHIFT_FOR_IDS_TABLE) | \
177 ((INTER_TABLE & (MAX_IDS_INTER_TABLES - 1)) << SHIFT_FOR_IDS_INTER_TABLE) |\ 190 ((Eo_Id)(INTER_TABLE & (MAX_IDS_INTER_TABLES - 1)) << SHIFT_FOR_IDS_INTER_TABLE) | \
178 ((ENTRY & (MAX_IDS_PER_TABLE - 1)) << SHIFT_FOR_ID_IN_TABLE) | \ 191 ((ENTRY & (MAX_IDS_PER_TABLE - 1)) << SHIFT_FOR_ID_IN_TABLE) | \
179 (GENERATION & (MAX_GENERATIONS - 1) )) 192 (GENERATION & (MAX_GENERATIONS - 1) ))
180 193
181/* Macro to extract from an Eo id the indexes of the tables */ 194/* Macro to extract from an Eo id the indexes of the tables */
182#define EO_DECOMPOSE_ID(ID, TABLE, INTER_TABLE, ENTRY, GENERATION) \ 195#define EO_DECOMPOSE_ID(ID, TABLE, INTER_TABLE, ENTRY, GENERATION) \
183 TABLE = (ID >> SHIFT_FOR_IDS_TABLE) & (MAX_IDS_TABLES - 1); \ 196 TABLE = (ID >> SHIFT_FOR_IDS_TABLE) & (MAX_IDS_TABLES - 1); \
184 INTER_TABLE = (ID >> SHIFT_FOR_IDS_INTER_TABLE) & (MAX_IDS_INTER_TABLES - 1); \ 197 INTER_TABLE = (ID >> SHIFT_FOR_IDS_INTER_TABLE) & (MAX_IDS_INTER_TABLES - 1); \
185 ENTRY = (ID >> SHIFT_FOR_ID_IN_TABLE) & (MAX_IDS_PER_TABLE - 1); \ 198 ENTRY = (ID >> SHIFT_FOR_ID_IN_TABLE) & (MAX_IDS_PER_TABLE - 1); \
186 GENERATION = ID & (MAX_GENERATIONS - 1); \ 199 GENERATION = ID & (MAX_GENERATIONS - 1); \
187 200
188/* Macro used for readability */ 201/* Macro used for readability */
189#define ID_TABLE _eo_ids_tables[table_id][int_table_id] 202#define ID_TABLE _eo_ids_tables[table_id][int_table_id]
@@ -193,9 +206,10 @@ _eo_obj_pointer_get(const Eo_Id obj_id)
193{ 206{
194#ifdef HAVE_EO_ID 207#ifdef HAVE_EO_ID
195 _Eo_Id_Entry *entry; 208 _Eo_Id_Entry *entry;
196 Table_Index table_id, int_table_id, entry_id, generation; 209 Generation_Counter generation;
210 Table_Index table_id, int_table_id, entry_id;
197 211
198 EO_DECOMPOSE_ID((Table_Index) obj_id, table_id, int_table_id, entry_id, generation); 212 EO_DECOMPOSE_ID(obj_id, table_id, int_table_id, entry_id, generation);
199 213
200 /* Checking the validity of the entry */ 214 /* Checking the validity of the entry */
201 if (_eo_ids_tables[table_id] && ID_TABLE) 215 if (_eo_ids_tables[table_id] && ID_TABLE)
@@ -218,50 +232,59 @@ Eo_Id
218_eo_id_allocate(const _Eo *obj) 232_eo_id_allocate(const _Eo *obj)
219{ 233{
220#ifdef HAVE_EO_ID 234#ifdef HAVE_EO_ID
235 _Eo_Ids_Table *table;
221 _Eo_Id_Entry *entry = NULL; 236 _Eo_Id_Entry *entry = NULL;
222 for (Table_Index table_id = 1; table_id < MAX_IDS_TABLES; table_id++) 237 for (Table_Index table_id = 1; table_id < MAX_IDS_TABLES; table_id++)
223 { 238 {
224 if (!_eo_ids_tables[table_id]) 239 if (!_eo_ids_tables[table_id])
225 { 240 {
226 /* We allocate a new table */ 241 /* We allocate a new intermediate table */
227 _eo_ids_tables[table_id] = _eo_id_mem_calloc(MAX_IDS_INTER_TABLES, sizeof(_Eo_Ids_Table*)); 242 _eo_ids_tables[table_id] = _eo_id_mem_calloc(MAX_IDS_INTER_TABLES, sizeof(_Eo_Ids_Table*));
228 } 243 }
229 for (Table_Index int_table_id = 0; int_table_id < MAX_IDS_INTER_TABLES; int_table_id++) 244 for (Table_Index int_table_id = 0; int_table_id < MAX_IDS_INTER_TABLES; int_table_id++)
230 { 245 {
231 if (!ID_TABLE) 246 table = ID_TABLE;
247 if (!table)
232 { 248 {
233 /* We allocate a new intermediate table */ 249 /* We allocate a new table */
234 ID_TABLE = _eo_id_mem_calloc(1, sizeof(_Eo_Ids_Table)); 250 table = _eo_id_mem_calloc(1, sizeof(_Eo_Ids_Table));
235 eina_trash_init(&(ID_TABLE->queue)); 251 table->start = 1;
252 table->queue_head = table->queue_tail = -1;
253 ID_TABLE = table;
236 /* We select directly the first entry of the new table */ 254 /* We select directly the first entry of the new table */
237 entry = &(ID_TABLE->entries[0]); 255 entry = &(table->entries[0]);
238 ID_TABLE->start = 1;
239 } 256 }
240 else 257 else if (table->start < MAX_IDS_PER_TABLE)
241 { 258 {
242 /* We try to pop from the queue an unused entry */ 259 /* We use an empty entries in the table */
243 entry = (_Eo_Id_Entry *)eina_trash_pop(&(ID_TABLE->queue)); 260 entry = &(table->entries[table->start]);
261 table->start++;
244 } 262 }
245 263 else if (table->queue_head != -1)
246 if (!entry && ID_TABLE->start < MAX_IDS_PER_TABLE)
247 { 264 {
248 /* No more unused entries in the trash but still empty entries in the table */ 265 /* We pop an unused entry from the queue */
249 entry = &(ID_TABLE->entries[ID_TABLE->start]); 266 entry = &(table->entries[table->queue_head]);
250 ID_TABLE->start++; 267 if (entry->next_in_queue == -1)
268 table->queue_head = table->queue_tail = -1;
269 else
270 table->queue_head = entry->next_in_queue;
251 } 271 }
252 272 else
253 if (entry)
254 { 273 {
255 /* An entry was found - need to find the entry id and fill it */ 274 /* Table is full of actives entries */
256 entry->ptr = (_Eo *)obj; 275 continue;
257 entry->active = 1;
258 entry->generation = _eo_generation_counter;
259 _eo_generation_counter++;
260 _eo_generation_counter %= MAX_GENERATIONS;
261 return EO_COMPOSE_ID(table_id, int_table_id,
262 (entry - ID_TABLE->entries),
263 entry->generation);
264 } 276 }
277
278 assert(entry);
279 /* An entry was found - need to find the entry id and fill it */
280 entry->ptr = (_Eo *)obj;
281 entry->active = 1;
282 entry->generation = _eo_generation_counter;
283 _eo_generation_counter++;
284 _eo_generation_counter %= MAX_GENERATIONS;
285 return EO_COMPOSE_ID(table_id, int_table_id,
286 (entry - table->entries),
287 entry->generation);
265 } 288 }
266 } 289 }
267 return 0; 290 return 0;
@@ -274,20 +297,31 @@ void
274_eo_id_release(const Eo_Id obj_id) 297_eo_id_release(const Eo_Id obj_id)
275{ 298{
276#ifdef HAVE_EO_ID 299#ifdef HAVE_EO_ID
300 _Eo_Ids_Table *table;
277 _Eo_Id_Entry *entry; 301 _Eo_Id_Entry *entry;
278 Table_Index table_id, int_table_id, entry_id, generation; 302 Generation_Counter generation;
279 EO_DECOMPOSE_ID((Table_Index) obj_id, table_id, int_table_id, entry_id, generation); 303 Table_Index table_id, int_table_id, entry_id;
304 EO_DECOMPOSE_ID(obj_id, table_id, int_table_id, entry_id, generation);
280 305
281 /* Checking the validity of the entry */ 306 /* Checking the validity of the entry */
282 if (_eo_ids_tables[table_id] && ID_TABLE) 307 if (_eo_ids_tables[table_id] && (table = ID_TABLE))
283 { 308 {
284 entry = &(ID_TABLE->entries[entry_id]); 309 entry = &(table->entries[entry_id]);
285 if (entry && entry->active && (entry->generation == generation)) 310 if (entry && entry->active && (entry->generation == generation))
286 { 311 {
287 /* Disable the entry */ 312 /* Disable the entry */
288 entry->active = 0; 313 entry->active = 0;
314 entry->next_in_queue = -1;
289 /* Push the entry into the queue */ 315 /* Push the entry into the queue */
290 eina_trash_push(&(ID_TABLE->queue), entry); 316 if (table->queue_tail == -1)
317 {
318 table->queue_head = table->queue_tail = entry_id;
319 }
320 else
321 {
322 table->entries[table->queue_tail].next_in_queue = entry_id;
323 table->queue_tail = entry_id;
324 }
291 return; 325 return;
292 } 326 }
293 } 327 }