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         /**
  42          * The CURRENT_TABLE_VERSION value of the library which created the
  43          * table. This value is stored in the index header at table creation
  44          * time. When the table is opened, the field is initialized from the
  45          * on-disk value.
  46          */
  47         uint8_t version;
  48         /** The size of the index header of this table. */
  49         uint16_t index_header_size;
  50         /** Contains the mapping of the table's index file */
  51         struct osl_object index_map;
  52         /** Total number of rows, including invalid rows. */
  53         unsigned num_rows;
  54         /** Keeps track of the number of invalid rows in the table. */
  55         uint32_t num_invalid_rows;
  56         /** Number of columns of type \p OSL_MAPPED_STORAGE. */
  57         unsigned num_mapped_columns;
  58         /** Number of columns of type \p OSL_NO_STORAGE. */
  59         unsigned num_volatile_columns;
  60         /** Number of columns of type \p OSL_DISK_STORAGE. */
  61         unsigned num_disk_storage_columns;
  62         /** Number of columns with associated rbtree. */
  63         unsigned num_rbtrees;
  64         /**
  65          * The number of the column that determines the name of the disk
  66          * storage objects.
  67          */
  68         unsigned disk_storage_name_column;
  69         /** The number of bytes of an index entry of a row. */
  70         unsigned row_index_size;
  71         /** Pointer to the internal representation of the columns. */
  72         struct osl_column *columns;
  73 };
  74
  75 /** Internal representation of a row of an osl table */
  76 struct osl_row {
  77         /**
  78          * The row number.
  79          *
  80          * It is only used if there is at least one mapped column.
  81          */
  82         off_t num;
  83         /** Array of size \a num_volatile_columns. */
  84         struct osl_object *volatile_objects;
  85 };
  86
  87 int read_table_desc(struct osl_object *map, struct osl_table_description *desc);
  88 int init_table_structure(const struct osl_table_description *desc,
  89                 struct osl_table **table_ptr);
  90 int row_is_invalid(struct osl_table *t, uint32_t row_num);
  91 int get_mapped_object(const struct osl_table *t, unsigned col_num,
  92         uint32_t row_num, struct osl_object *obj);
  93 int unmap_table(struct osl_table *t, enum osl_close_flags flags);
  94 int init_rbtrees(struct osl_table *t);
  95
  96 /**
  97  * Flags to be specified for map_table().
  98  *
  99  * \sa map_table().
 100  */
 101 enum map_table_flags {
 102         /**
 103          * Check whether the entries in the table index match the entries in
 104          * the table description.
 105          */
 106         MAP_TBL_FL_VERIFY_INDEX = 1,
 107         /** Do not complain even if the dirty flag is set. */
 108         MAP_TBL_FL_IGNORE_DIRTY = 2,
 109         /** Use read-only mappings. */
 110         MAP_TBL_FL_MAP_RDONLY = 4
 111 };
 112
 113 int map_table(struct osl_table *t, enum map_table_flags flags);
 114 void clear_rbtrees(struct osl_table *t);
 115 int mark_row_invalid(struct osl_table *t, uint32_t row_num);
 116
 117
 118 /**
 119  * Get the description of a column by column number
 120  *
 121  * \param d Pointer to the table description.
 122  * \param col_num The number of the column to get the description for.
 123  *
 124  * \return The table description.
 125  *
 126  * \sa struct osl_column_description.
 127  */
 128 _static_inline_ struct osl_column_description *get_column_description(
 129                 const struct osl_table_description *d, unsigned col_num)
 130 {
 131         return &d->column_descriptions[col_num];
 132 }
 133
 134 /**
 135  * Format of the header of the index file of an osl table.
 136  *
 137  * Bytes 16-31 are currently unused.
 138  *
 139  * \sa enum index_column_desc_offsets, HASH_SIZE, osl_table_flags.
 140  */
 141 enum index_header_offsets {
 142         /** Bytes 0-8: PARASLASH. */
 143         IDX_OSL_MAGIC = 0,
 144         /** Byte 9: Dirty flag (nonzero if table is mapped). */
 145         IDX_DIRTY_FLAG = 9,
 146         /** Byte 10: osl table version number. */
 147         IDX_VERSION = 10,
 148         /** Byte 11: Table flags.*/
 149         IDX_TABLE_FLAGS = 11,
 150         /** Byte 12,13: Number of columns. */
 151         IDX_NUM_COLUMNS,
 152         /** Byte 14,15 Size of the index header. */
 153         IDX_HEADER_SIZE = 14,
 154         /** Column descriptions start here. */
 155         IDX_COLUMN_DESCRIPTIONS = 32
 156 };
 157
 158 /**
 159  * Format of the column description in the index header.
 160  *
 161  * \sa index_header_offsets.
 162  */
 163 enum index_column_desc_offsets {
 164         /** Bytes 0,1: Storage_type. */
 165         IDX_CD_STORAGE_TYPE = 0,
 166         /** Bytes 2,3: Storage_flags. */
 167         IDX_CD_STORAGE_FLAGS = 2,
 168         /** Bytes 4 - 7: Data_size (only used for fixed size columns). */
 169         IDX_CD_DATA_SIZE = 4,
 170         /** Bytes 8 - ... Name of the column. */
 171         IDX_CD_NAME = 8,
 172 };
 173
 174 /** Magic string contained in the header of the index file of each osl table. */
 175 #define OSL_MAGIC "PARASLASH"
 176
 177 /**
 178  * The minimal number of bytes for a column in the index header.
 179  *
 180  * The column name starts at byte IDX_CD_NAME and must at least contain one
 181  * character, plus the terminating NULL byte.
 182   */
 183 #define MIN_IDX_COLUMN_DESCRIPTION_SIZE (IDX_CD_NAME + 2)
 184
 185 /**
 186  * Get the number of bytes used for a column in the index header.
 187  *
 188  * \param name The name of the column.
 189  *
 190  * The amount of space used for a column in the index header of a table depends
 191  * on the (length of the) name of the column.
 192  *
 193  * \return The total number of bytes needed to store one column of this name.
 194  */
 195 _static_inline_ size_t index_column_description_size(const char *name)
 196 {
 197         return MIN_IDX_COLUMN_DESCRIPTION_SIZE + strlen(name) - 1;
 198 }
 199
 200 /*
 201  * The version used by this instance of the library. Written to the index of
 202  * newly created tables.
 203  */
 204 #define CURRENT_TABLE_VERSION 1
 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 t Determines the hash function to use.
 460  * \param obj the Object to compute the hash value from.
 461  * \param hash Result is returned here.
 462  */
 463 _static_inline_ void hash_object(const struct osl_table *t,
 464                 const struct osl_object *obj, HASH_TYPE *hash)
 465 {
 466         hash_function(t->version, obj->data, obj->size, hash);
 467 }
 468
 469 /**
 470  * Get the relative path of an object, given the hash value.
 471  *
 472  * \param t Pointer to an initialized osl table.
 473  * \param hash An arbitrary hash value.
 474  *
 475  * This function is typically called with \a hash being the hash of the object
 476  * stored in the disk storage name column of a row.  If the OSL_LARGE_TABLE
 477  * flag is set, the first two hex digits get separated with a slash from the
 478  * remaining digits.
 479  *
 480  * \return The relative path for all disk storage objects corresponding to \a
 481  * hash.
 482  *
 483  * \sa struct osl_table:disk_storage_name_column.
 484  */
 485 _static_inline_ char *disk_storage_name_of_hash(const struct osl_table *t, HASH_TYPE *hash)
 486 {
 487         char asc[2 * HASH_SIZE + 2];
 488
 489         hash_to_asc(hash, asc);
 490         if (t->desc->flags & OSL_LARGE_TABLE)
 491                 return make_message("%.2s/%s", asc, asc + 2);
 492         return strdup(asc);
 493 }
 494
 495 /**
 496  * Iterate over each column of an initialized table.
 497  *
 498  * \param col A pointer to a struct osl_column.
 499  * \param desc Pointer to the table description.
 500  * \param cd Pointer to struct osl_column_description.
 501  *
 502  * On each iteration, \a col will point to the next column of the table and \a
 503  * cd will point to the column description of this column.
 504  *
 505  * \sa struct osl_column FOR_EACH_RBTREE_COLUMN, FOR_EACH_COLUMN_OF_TYPE,
 506  * FOR_EACH_MAPPED_COLUMN, FOR_EACH_DISK_STORAGE_COLUMN,
 507  * FOR_EACH_VOLATILE_COLUMN.
 508  */
 509 #define FOR_EACH_COLUMN(col, desc, cd) \
 510         for (col = 0; col < (desc)->num_columns && \
 511                 (cd = get_column_description(desc, col)); col++)
 512
 513 /**
 514  * Iterate over each column with associated rbtree.
 515  *
 516  * \param col Same meaning as in FOR_EACH_COLUMN().
 517  * \param table Same meaning as in FOR_EACH_COLUMN().
 518  * \param cd Same meaning as in FOR_EACH_COLUMN().
 519  *
 520  * \sa osl_storage_flags::OSL_RBTREE, FOR_EACH_COLUMN, FOR_EACH_COLUMN_OF_TYPE,
 521  * FOR_EACH_MAPPED_COLUMN, FOR_EACH_DISK_STORAGE_COLUMN,
 522  * FOR_EACH_VOLATILE_COLUMN.
 523  */
 524 #define FOR_EACH_RBTREE_COLUMN(col, table, cd) \
 525         for (col = next_rbtree_column(0, table, &cd); \
 526         col < table->desc->num_columns; \
 527         col = next_rbtree_column(++col, table, &cd))
 528
 529 /**
 530  * Iterate over each column of given storage type.
 531  *
 532  * \param type The osl_storage_type to iterate over.
 533  * \param col Same meaning as in FOR_EACH_COLUMN().
 534  * \param table Same meaning as in FOR_EACH_COLUMN().
 535  * \param cd Same meaning as in FOR_EACH_COLUMN().
 536  *
 537  * \sa osl_storage_type, FOR_EACH_COLUMN, FOR_EACH_RBTREE_COLUMN,
 538  * FOR_EACH_MAPPED_COLUMN, FOR_EACH_DISK_STORAGE_COLUMN,
 539  * FOR_EACH_VOLATILE_COLUMN.
 540  */
 541 #define FOR_EACH_COLUMN_OF_TYPE(type, col, table, cd) \
 542         for (col = next_column_of_type(type, 0, table, &cd); \
 543         col < table->desc->num_columns; \
 544         col = next_column_of_type(type, ++col, table, &cd))
 545
 546 /**
 547  * Iterate over each mapped column.
 548  *
 549  * \param col Same meaning as in FOR_EACH_COLUMN().
 550  * \param table Same meaning as in FOR_EACH_COLUMN().
 551  * \param cd Same meaning as in FOR_EACH_COLUMN().
 552  *
 553  * Just like FOR_EACH_COLUMN(), but skip columns which are
 554  * not of type \p OSL_MAPPED_STORAGE.
 555  *
 556  * \sa osl_storage_flags::OSL_MAPPED_STORAGE, FOR_EACH_COLUMN,
 557  * FOR_EACH_RBTREE_COLUMN, FOR_EACH_COLUMN_OF_TYPE,
 558  * FOR_EACH_DISK_STORAGE_COLUMN, FOR_EACH_VOLATILE_COLUMN.
 559  */
 560 #define FOR_EACH_MAPPED_COLUMN(col, table, cd) \
 561         FOR_EACH_COLUMN_OF_TYPE(OSL_MAPPED_STORAGE, col, table, cd)
 562
 563 /**
 564  * Iterate over each disk storage column.
 565  *
 566  * \param col Same meaning as in FOR_EACH_COLUMN().
 567  * \param table Same meaning as in FOR_EACH_COLUMN().
 568  * \param cd Same meaning as in FOR_EACH_COLUMN().
 569  *
 570  * Just like FOR_EACH_COLUMN(), but skip columns which are
 571  * not of type \p OSL_DISK_STORAGE.
 572  *
 573  * \sa osl_storage_flags::OSL_DISK_STORAGE, FOR_EACH_COLUMN,
 574  * FOR_EACH_RBTREE_COLUMN, FOR_EACH_COLUMN_OF_TYPE, FOR_EACH_MAPPED_COLUMN,
 575  * FOR_EACH_VOLATILE_COLUMN.
 576  */
 577 #define FOR_EACH_DISK_STORAGE_COLUMN(col, table, cd) \
 578         FOR_EACH_COLUMN_OF_TYPE(OSL_DISK_STORAGE, col, table, cd)
 579
 580 /**
 581  * Iterate over each volatile column.
 582  *
 583  * \param col Same meaning as in FOR_EACH_COLUMN().
 584  * \param table Same meaning as in FOR_EACH_COLUMN().
 585  * \param cd Same meaning as in FOR_EACH_COLUMN().
 586  *
 587  * Just like FOR_EACH_COLUMN(), but skip columns which are
 588  * not of type \p OSL_NO_STORAGE.
 589  *
 590  * \sa osl_storage_flags::OSL_NO_STORAGE, FOR_EACH_COLUMN,
 591  * FOR_EACH_RBTREE_COLUMN, FOR_EACH_COLUMN_OF_TYPE, FOR_EACH_MAPPED_COLUMN,
 592  * FOR_EACH_DISK_STORAGE_COLUMN.
 593  */
 594 #define FOR_EACH_VOLATILE_COLUMN(col, table, cd) \
 595         FOR_EACH_COLUMN_OF_TYPE(OSL_NO_STORAGE, col, table, cd)