Merge branch 'refs/heads/t/lopsub'
[osl.git] / osl_core.h
1 /*
2 * Copyright (C) 2007-2009 Andre Noll <maan@tuebingen.mpg.de>
3 *
4 * Licensed under the GPL v2. For licencing details see COPYING.
5 */
6
7 /** \file osl_core.h Object storage layer details, not visible to users. */
8
9 #include "rbtree.h"
10 #include "hash.h"
11
12 __must_check __printf_1_2 __malloc char *make_message(const char *fmt, ...);
13
14 /** Internal representation of a column of an osl table. */
15 struct osl_column {
16 /** The memory mapping of this comumn (only used for mapped columns). */
17 struct osl_object data_map;
18 /** The root of the rbtree (only used for columns with rbtrees). */
19 struct rb_root rbtree;
20 /** The index in the array of rb nodes (only used for columns with rbtrees). */
21 unsigned rbtree_num;
22 /** Index for volatile_objects of struct osl_row. */
23 unsigned volatile_num;
24 /**
25 * Starting point of the data for this column within the index
26 * (only used for mapped columns).
27 */
28 uint16_t index_offset;
29 /**
30 * The hash value of the name of this column.
31 *
32 * This is only used for mapped and disk storage columns).
33 */
34 HASH_TYPE name_hash[HASH_SIZE];
35 };
36
37 /** Internal representation of an osl table */
38 struct osl_table {
39 /** Pointer to the table description */
40 const struct osl_table_description *desc;
41 /** The size of the index header of this table. */
42 uint16_t index_header_size;
43 /** Contains the mapping of the table's index file */
44 struct osl_object index_map;
45 /** Total number of rows, including invalid rows. */
46 unsigned num_rows;
47 /** Keeps track of the number of invalid rows in the table. */
48 uint32_t num_invalid_rows;
49 /** Number of columns of type \p OSL_MAPPED_STORAGE. */
50 unsigned num_mapped_columns;
51 /** Number of columns of type \p OSL_NO_STORAGE. */
52 unsigned num_volatile_columns;
53 /** Number of columns of type \p OSL_DISK_STORAGE. */
54 unsigned num_disk_storage_columns;
55 /** Number of columns with associated rbtree. */
56 unsigned num_rbtrees;
57 /**
58 * The number of the column that determines the name of the disk
59 * storage objects.
60 */
61 unsigned disk_storage_name_column;
62 /** The number of bytes of an index entry of a row. */
63 unsigned row_index_size;
64 /** Pointer to the internal representation of the columns. */
65 struct osl_column *columns;
66 };
67
68 /** Internal representation of a row of an osl table */
69 struct osl_row {
70 /**
71 * The row number.
72 *
73 * It is only used if there is at least one mapped column.
74 */
75 off_t num;
76 /** Array of size \a num_volatile_columns. */
77 struct osl_object *volatile_objects;
78 };
79
80 int read_table_desc(struct osl_object *map, struct osl_table_description *desc);
81 int init_table_structure(const struct osl_table_description *desc,
82 struct osl_table **table_ptr);
83 int row_is_invalid(struct osl_table *t, uint32_t row_num);
84 int get_mapped_object(const struct osl_table *t, unsigned col_num,
85 uint32_t row_num, struct osl_object *obj);
86 int unmap_table(struct osl_table *t, enum osl_close_flags flags);
87 int init_rbtrees(struct osl_table *t);
88
89 /**
90 * Flags to be specified for map_table().
91 *
92 * \sa map_table().
93 */
94 enum map_table_flags {
95 /**
96 * Check whether the entries in the table index match the entries in
97 * the table description.
98 */
99 MAP_TBL_FL_VERIFY_INDEX = 1,
100 /** Do not complain even if the dirty flag is set. */
101 MAP_TBL_FL_IGNORE_DIRTY = 2,
102 /** Use read-only mappings. */
103 MAP_TBL_FL_MAP_RDONLY = 4
104 };
105
106 int map_table(struct osl_table *t, enum map_table_flags flags);
107 void clear_rbtrees(struct osl_table *t);
108 int mark_row_invalid(struct osl_table *t, uint32_t row_num);
109
110
111 /**
112 * Get the description of a column by column number
113 *
114 * \param d Pointer to the table description.
115 * \param col_num The number of the column to get the description for.
116 *
117 * \return The table description.
118 *
119 * \sa struct osl_column_description.
120 */
121 _static_inline_ struct osl_column_description *get_column_description(
122 const struct osl_table_description *d, unsigned col_num)
123 {
124 return &d->column_descriptions[col_num];
125 }
126
127 /**
128 * Format of the header of the index file of an osl table.
129 *
130 * Bytes 16-31 are currently unused.
131 *
132 * \sa enum index_column_desc_offsets, HASH_SIZE, osl_table_flags.
133 */
134 enum index_header_offsets {
135 /** Bytes 0-8: PARASLASH. */
136 IDX_OSL_MAGIC = 0,
137 /** Byte 9: Dirty flag (nonzero if table is mapped). */
138 IDX_DIRTY_FLAG = 9,
139 /** Byte 10: osl table version number. */
140 IDX_VERSION = 10,
141 /** Byte 11: Table flags.*/
142 IDX_TABLE_FLAGS = 11,
143 /** Byte 12,13: Number of columns. */
144 IDX_NUM_COLUMNS,
145 /** Byte 14,15 Size of the index header. */
146 IDX_HEADER_SIZE = 14,
147 /** Column descriptions start here. */
148 IDX_COLUMN_DESCRIPTIONS = 32
149 };
150
151 /**
152 * Format of the column description in the index header.
153 *
154 * \sa index_header_offsets.
155 */
156 enum index_column_desc_offsets {
157 /** Bytes 0,1: Storage_type. */
158 IDX_CD_STORAGE_TYPE = 0,
159 /** Bytes 2,3: Storage_flags. */
160 IDX_CD_STORAGE_FLAGS = 2,
161 /** Bytes 4 - 7: Data_size (only used for fixed size columns). */
162 IDX_CD_DATA_SIZE = 4,
163 /** Bytes 8 - ... Name of the column. */
164 IDX_CD_NAME = 8,
165 };
166
167 /** Magic string contained in the header of the index file of each osl table. */
168 #define OSL_MAGIC "PARASLASH"
169
170 /**
171 * The minimal number of bytes for a column in the index header.
172 *
173 * The column name starts at byte IDX_CD_NAME and must at least contain one
174 * character, plus the terminating NULL byte.
175 */
176 #define MIN_IDX_COLUMN_DESCRIPTION_SIZE (IDX_CD_NAME + 2)
177
178 /**
179 * Get the number of bytes used for a column in the index header.
180 *
181 * \param name The name of the column.
182 *
183 * The amount of space used for a column in the index header of a table depends
184 * on the (length of the) name of the column.
185 *
186 * \return The total number of bytes needed to store one column of this name.
187 */
188 _static_inline_ size_t index_column_description_size(const char *name)
189 {
190 return MIN_IDX_COLUMN_DESCRIPTION_SIZE + strlen(name) - 1;
191 }
192
193 /*
194 * The version used by this instance of the library. Written to the index of
195 * newly created tables.
196 */
197 #define CURRENT_TABLE_VERSION 1
198
199 /*
200 * The lowest library version that is able to use tables of version
201 * CURRENT_TABLE_VERSION. Also written to the index of new tables. If
202 * compat_version(table) > current_version(lib) the table can not be opened.
203 */
204 #define COMPAT_TABLE_VERSION 0
205
206 /*
207 * The lowest table version this library understands. On open, if
208 * current_version(table) < min_version(lib) the osl_open_table() call
209 * fails.
210 */
211 #define MIN_TABLE_VERSION 1
212
213
214 /** An index header must be at least that many bytes long. */
215 #define MIN_INDEX_HEADER_SIZE(num_cols) (MIN_IDX_COLUMN_DESCRIPTION_SIZE \
216 * num_cols + IDX_COLUMN_DESCRIPTIONS)
217
218 /**
219 * Get the number of rows from the size of the memory mapping.
220 *
221 * \param t Pointer to an open table.
222 *
223 * \return The number of rows, including invalid rows.
224 */
225 _static_inline_ unsigned table_num_rows(const struct osl_table *t)
226 {
227 return (t->index_map.size - t->index_header_size)
228 / t->row_index_size;
229 }
230
231 /**
232 * Get the path of the index file from a table description.
233 *
234 * \param d The table description.
235 *
236 * \return The full path of the index file. Result must be freed by
237 * the caller.
238 */
239 _static_inline_ char *index_filename(const struct osl_table_description *d)
240 {
241 return make_message("%s/%s/index", d->dir, d->name);
242 }
243
244 /**
245 * Get the path of storage of a column.
246 *
247 * \param t Pointer to an initialized table.
248 * \param col_num The number of the column to get the path for.
249 *
250 * \return The full path of the mapped data file (mapped storage) or the
251 * data directory (disk storage). Result must be freed by the caller.
252 *
253 * \sa osl_storage_type.
254 */
255 _static_inline_ char *column_filename(const struct osl_table *t, unsigned col_num)
256 {
257 char asc[2 * HASH_SIZE + 1];
258 hash_to_asc(t->columns[col_num].name_hash, asc);
259 return make_message("%s/%s/%s", t->desc->dir, t->desc->name, asc);
260 }
261
262 /**
263 * Get the start of an index entry
264 *
265 * \param t Pointer to a table which has been mapped.
266 * \param row_num The number of the row whose index entry should be retrieved.
267 * \param row_index Result pointer.
268 *
269 * \return Positive on success, \p -E_INDEX_CORRUPTION otherwise.
270 *
271 * \sa get_cell_index().
272 */
273 _static_inline_ int get_row_index(const struct osl_table *t, uint32_t row_num,
274 char **row_index)
275 {
276 uint32_t index_offset;
277 index_offset = t->index_header_size + t->row_index_size * row_num;
278 if (index_offset + 8 > t->index_map.size) {
279 *row_index = NULL;
280 return -E_OSL_INDEX_CORRUPTION;
281 }
282 *row_index = (char *)(t->index_map.data) + index_offset;
283 return 1;
284 }
285
286 /**
287 * Get the index entry of a row/column pair.
288 *
289 * \param t Pointer to a table which has been mapped.
290 * \param row_num The number of the row whose index entry should be retrieved.
291 * \param col_num The number of the column whose index entry should be retrieved.
292 * \param cell_index Result pointer.
293 *
294 * \return Positive on success, \p -E_INDEX_CORRUPTION otherwise.
295 *
296 * \sa get_row_index().
297 */
298 _static_inline_ int get_cell_index(const struct osl_table *t, uint32_t row_num,
299 uint32_t col_num, char **cell_index)
300 {
301 int ret = get_row_index(t, row_num, cell_index);
302 if (ret < 0)
303 return ret;
304 *cell_index += t->columns[col_num].index_offset;
305 return ret;
306 }
307
308 /**
309 * Change an index entry of a column after object was added.
310 *
311 * \param row_index Pointer to the index of the row to update.
312 * \param col Pointer to the column.
313 * \param map_size The new size of the data file.
314 * \param object_size The size of the object just appended to the data file.
315 *
316 * This is called right after an object was appended to the data file for a
317 * mapped column.
318 *
319 * \sa get_row_index().
320 */
321 _static_inline_ void update_cell_index(char *row_index, struct osl_column *col,
322 uint32_t map_size, uint32_t object_size)
323 {
324 write_u32(row_index + col->index_offset, map_size - object_size);
325 write_u32(row_index + col->index_offset + 4, object_size);
326 }
327
328 /**
329 * Get the full path of a disk storage object
330 *
331 * \param t Pointer to an initialized table.
332 * \param col_num The number of the column the disk storage object belongs to.
333 * \param ds_name The disk storage name of the object.
334 *
335 * \return Pointer to the full path which must be freed by the caller.
336 *
337 * \sa column_filename(), disk_storage_name_of_row().
338 */
339 _static_inline_ char *disk_storage_path(const struct osl_table *t,
340 unsigned col_num, const char *ds_name)
341 {
342 char *filename, *dirname = column_filename(t, col_num);
343
344 if (!dirname)
345 return NULL;
346 filename = make_message("%s/%s", dirname, ds_name);
347 free(dirname);
348 return filename;
349 }
350
351 /**
352 * Get the column description of the next column of a given type.
353 *
354 * \param type the desired storage type.
355 * \param col_num the column to start the search.
356 * \param t the osl table.
357 * \param cd result is returned here.
358 *
359 * \return On success, \a cd contains the column description of the next column
360 * of type \a type, and the number of that column is returned. Otherwise, \a
361 * cd is set to \p NULL and the function returns t->num_columns + 1.
362 *
363 * \sa FOR_EACH_COLUMN_OF_TYPE, FOR_EACH_MAPPED_COLUMN, FOR_EACH_RBTREE_COLUMN,
364 * FOR_EACH_DISK_STORAGE_COLUMN, FOR_EACH_VOLATILE_COLUMN, osl_storage_type.
365 */
366 _static_inline_ int next_column_of_type(enum osl_storage_type type, int col_num,
367 const struct osl_table *t,
368 const struct osl_column_description **cd)
369 {
370 *cd = NULL;
371 while (col_num < t->desc->num_columns) {
372 *cd = get_column_description(t->desc, col_num);
373 if ((*cd)->storage_type == type)
374 break;
375 col_num++;
376 }
377 return col_num;
378 }
379
380 /**
381 * Find the next column with an associated rbtree.
382 *
383 * \param col_num The column to start the search.
384 * \param t The osl table.
385 * \param cd Result is returned here.
386
387 * \return On success, \a cd contains the column description of the next column
388 * with associated rbtree, and the number of that column is returned.
389 * Otherwise, \a cd is set to \p NULL and the function returns t->num_columns +
390 * 1.
391 *
392 * \sa FOR_EACH_COLUMN_OF_TYPE, FOR_EACH_MAPPED_COLUMN, FOR_EACH_RBTREE_COLUMN,
393 * FOR_EACH_DISK_STORAGE_COLUMN, FOR_EACH_VOLATILE_COLUMN, osl_storage_flags.
394 */
395 _static_inline_ int next_rbtree_column(int col_num, const struct osl_table *t,
396 const struct osl_column_description **cd)
397 {
398 *cd = NULL;
399 while (col_num < t->desc->num_columns) {
400 *cd = get_column_description(t->desc, col_num);
401 if ((*cd)->storage_flags & OSL_RBTREE)
402 break;
403 col_num++;
404 }
405 return col_num;
406 }
407
408
409 /* quite some dirty hacks */
410
411 /** Round up size of struct osl_row to multiple of 8 */
412 #define RB_NODES_OFFSET ((sizeof(struct osl_row) + 7) / 8 * 8)
413
414 /**
415 * Allocate a new osl row.
416 *
417 * \param num_rbtrees The number of rbtrees for this row.
418 *
419 * \return A pointer to a zeroed-out area suitable for holding an osl row with
420 * \a num_rbtrees rbtree columns or \p NULL if no memory could be allocated.
421 */
422 _static_inline_ struct osl_row *allocate_row(unsigned num_rbtrees)
423 {
424 size_t s = RB_NODES_OFFSET + num_rbtrees * sizeof(struct rb_node);
425 return calloc(1, s);
426 }
427
428 /**
429 * Compute the pointer to a rbtree node embedded in a osl row.
430 *
431 * \param row The row to extract the rbtree pointer from.
432 * \param rbtree_num The number of the rbtree node to extract.
433 *
434 * \return A pointer to the \a rbtree_num th node contained in \a row.
435 */
436 _static_inline_ struct rb_node *get_rb_node_pointer(const struct osl_row *row, uint32_t rbtree_num)
437 {
438 return ((struct rb_node *)(((char *)row) + RB_NODES_OFFSET)) + rbtree_num;
439 }
440
441 /**
442 * Get a pointer to the struct containing the given rbtree node.
443 *
444 * \param node Pointer to the rbtree node.
445 * \param rbtree_num Number of \a node in the array of rbtree nodes.
446 *
447 * \return A pointer to the row containing \a node.
448 */
449 _static_inline_ struct osl_row *get_row_pointer(const struct rb_node *node,
450 unsigned rbtree_num)
451 {
452 node -= rbtree_num;
453 return (struct osl_row *)(((char *)node) - RB_NODES_OFFSET);
454 }
455
456 /**
457 * Compute a cryptographic hash of an osl object.
458 *
459 * \param obj the Object to compute the hash value from.
460 * \param hash Result is returned here.
461 */
462 _static_inline_ void hash_object(const struct osl_object *obj, HASH_TYPE *hash)
463 {
464 hash_function(obj->data, obj->size, hash);
465 }
466
467 /**
468 * Get the relative path of an object, given the hash value.
469 *
470 * \param t Pointer to an initialized osl table.
471 * \param hash An arbitrary hash value.
472 *
473 * This function is typically called with \a hash being the hash of the object
474 * stored in the disk storage name column of a row. If the OSL_LARGE_TABLE
475 * flag is set, the first two hex digits get separated with a slash from the
476 * remaining digits.
477 *
478 * \return The relative path for all disk storage objects corresponding to \a
479 * hash.
480 *
481 * \sa struct osl_table:disk_storage_name_column.
482 */
483 _static_inline_ char *disk_storage_name_of_hash(const struct osl_table *t, HASH_TYPE *hash)
484 {
485 char asc[2 * HASH_SIZE + 2];
486
487 hash_to_asc(hash, asc);
488 if (t->desc->flags & OSL_LARGE_TABLE)
489 return make_message("%.2s/%s", asc, asc + 2);
490 return strdup(asc);
491 }
492
493 /**
494 * Iterate over each column of an initialized table.
495 *
496 * \param col A pointer to a struct osl_column.
497 * \param desc Pointer to the table description.
498 * \param cd Pointer to struct osl_column_description.
499 *
500 * On each iteration, \a col will point to the next column of the table and \a
501 * cd will point to the column description of this column.
502 *
503 * \sa struct osl_column FOR_EACH_RBTREE_COLUMN, FOR_EACH_COLUMN_OF_TYPE,
504 * FOR_EACH_MAPPED_COLUMN, FOR_EACH_DISK_STORAGE_COLUMN,
505 * FOR_EACH_VOLATILE_COLUMN.
506 */
507 #define FOR_EACH_COLUMN(col, desc, cd) \
508 for (col = 0; col < (desc)->num_columns && \
509 (cd = get_column_description(desc, col)); col++)
510
511 /**
512 * Iterate over each column with associated rbtree.
513 *
514 * \param col Same meaning as in FOR_EACH_COLUMN().
515 * \param table Same meaning as in FOR_EACH_COLUMN().
516 * \param cd Same meaning as in FOR_EACH_COLUMN().
517 *
518 * \sa osl_storage_flags::OSL_RBTREE, FOR_EACH_COLUMN, FOR_EACH_COLUMN_OF_TYPE,
519 * FOR_EACH_MAPPED_COLUMN, FOR_EACH_DISK_STORAGE_COLUMN,
520 * FOR_EACH_VOLATILE_COLUMN.
521 */
522 #define FOR_EACH_RBTREE_COLUMN(col, table, cd) \
523 for (col = next_rbtree_column(0, table, &cd); \
524 col < table->desc->num_columns; \
525 col = next_rbtree_column(++col, table, &cd))
526
527 /**
528 * Iterate over each column of given storage type.
529 *
530 * \param type The osl_storage_type to iterate over.
531 * \param col Same meaning as in FOR_EACH_COLUMN().
532 * \param table Same meaning as in FOR_EACH_COLUMN().
533 * \param cd Same meaning as in FOR_EACH_COLUMN().
534 *
535 * \sa osl_storage_type, FOR_EACH_COLUMN, FOR_EACH_RBTREE_COLUMN,
536 * FOR_EACH_MAPPED_COLUMN, FOR_EACH_DISK_STORAGE_COLUMN,
537 * FOR_EACH_VOLATILE_COLUMN.
538 */
539 #define FOR_EACH_COLUMN_OF_TYPE(type, col, table, cd) \
540 for (col = next_column_of_type(type, 0, table, &cd); \
541 col < table->desc->num_columns; \
542 col = next_column_of_type(type, ++col, table, &cd))
543
544 /**
545 * Iterate over each mapped column.
546 *
547 * \param col Same meaning as in FOR_EACH_COLUMN().
548 * \param table Same meaning as in FOR_EACH_COLUMN().
549 * \param cd Same meaning as in FOR_EACH_COLUMN().
550 *
551 * Just like FOR_EACH_COLUMN(), but skip columns which are
552 * not of type \p OSL_MAPPED_STORAGE.
553 *
554 * \sa osl_storage_flags::OSL_MAPPED_STORAGE, FOR_EACH_COLUMN,
555 * FOR_EACH_RBTREE_COLUMN, FOR_EACH_COLUMN_OF_TYPE,
556 * FOR_EACH_DISK_STORAGE_COLUMN, FOR_EACH_VOLATILE_COLUMN.
557 */
558 #define FOR_EACH_MAPPED_COLUMN(col, table, cd) \
559 FOR_EACH_COLUMN_OF_TYPE(OSL_MAPPED_STORAGE, col, table, cd)
560
561 /**
562 * Iterate over each disk storage column.
563 *
564 * \param col Same meaning as in FOR_EACH_COLUMN().
565 * \param table Same meaning as in FOR_EACH_COLUMN().
566 * \param cd Same meaning as in FOR_EACH_COLUMN().
567 *
568 * Just like FOR_EACH_COLUMN(), but skip columns which are
569 * not of type \p OSL_DISK_STORAGE.
570 *
571 * \sa osl_storage_flags::OSL_DISK_STORAGE, FOR_EACH_COLUMN,
572 * FOR_EACH_RBTREE_COLUMN, FOR_EACH_COLUMN_OF_TYPE, FOR_EACH_MAPPED_COLUMN,
573 * FOR_EACH_VOLATILE_COLUMN.
574 */
575 #define FOR_EACH_DISK_STORAGE_COLUMN(col, table, cd) \
576 FOR_EACH_COLUMN_OF_TYPE(OSL_DISK_STORAGE, col, table, cd)
577
578 /**
579 * Iterate over each volatile column.
580 *
581 * \param col Same meaning as in FOR_EACH_COLUMN().
582 * \param table Same meaning as in FOR_EACH_COLUMN().
583 * \param cd Same meaning as in FOR_EACH_COLUMN().
584 *
585 * Just like FOR_EACH_COLUMN(), but skip columns which are
586 * not of type \p OSL_NO_STORAGE.
587 *
588 * \sa osl_storage_flags::OSL_NO_STORAGE, FOR_EACH_COLUMN,
589 * FOR_EACH_RBTREE_COLUMN, FOR_EACH_COLUMN_OF_TYPE, FOR_EACH_MAPPED_COLUMN,
590 * FOR_EACH_DISK_STORAGE_COLUMN.
591 */
592 #define FOR_EACH_VOLATILE_COLUMN(col, table, cd) \
593 FOR_EACH_COLUMN_OF_TYPE(OSL_NO_STORAGE, col, table, cd)