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