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