osl_core.h

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