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)