--- /dev/null
+/*
+ * Copyright (C) 2007 Andre Noll <maan@systemlinux.org>
+ *
+ * Licensed under the GPL v2. For licencing details see COPYING.
+ */
+
+/** \file osl_core.h Object storage layer details, not visible to users. */
+
+#include "rbtree.h"
+#include "osl.h"
+#include "string.h"
+#include "hash.h"
+
+/** Internal representation of a column of an osl table. */
+struct osl_column {
+ /** The memory mapping of this comumn (only used for mapped columns). */
+ struct osl_object data_map;
+ /** The root of the rbtree (only used for columns with rbtrees). */
+ struct rb_root rbtree;
+ /** The index in the array of rb nodes (only used for columns with rbtrees). */
+ unsigned rbtree_num;
+ /** Index for volatile_objects of struct osl_row. */
+ unsigned volatile_num;
+ /**
+ * Starting point of the data for this column within the index
+ * (only used for mapped columns).
+ */
+ uint16_t index_offset;
+ /**
+ * The hash value of the name of this column.
+ *
+ * This is only used for mapped and disk storage columns).
+ */
+ HASH_TYPE name_hash[HASH_SIZE];
+};
+
+/** Internal representation of an osl table */
+struct osl_table {
+ /** Pointer to the table description */
+ const struct osl_table_description *desc;
+ /** The size of the index header of this table. */
+ uint16_t index_header_size;
+ /** Contains the mapping of the table's index file */
+ struct osl_object index_map;
+ /** Total number of rows, including invalid rows. */
+ unsigned num_rows;
+ /** Keeps track of the number of invalid rows in the table. */
+ uint32_t num_invalid_rows;
+ /** Number of columns of type \p OSL_MAPPED_STORAGE. */
+ unsigned num_mapped_columns;
+ /** Number of columns of type \p OSL_NO_STORAGE. */
+ unsigned num_volatile_columns;
+ /** Number of columns of type \p OSL_DISK_STORAGE. */
+ unsigned num_disk_storage_columns;
+ /** Number of columns with associated rbtree. */
+ unsigned num_rbtrees;
+ /**
+ * The number of the column that determines the name of the disk
+ * storage objcts.
+ */
+ unsigned disk_storage_name_column;
+ /** The number of bytes of an index entry of a row. */
+ unsigned index_entry_size;
+ /** Pointer to the internal representation of the columns. */
+ struct osl_column *columns;
+};
+
+/** Internal representation of a row of an osl table */
+struct osl_row {
+ /** The row number only present if there is at least one mapped column. */
+ off_t id;
+ /** Array of size \a num_volatile_columns. */
+ struct osl_object *volatile_objects;
+};
+
+int read_table_desc(struct osl_object *map, struct osl_table_description *desc);
+int init_table_structure(const struct osl_table_description *desc,
+ struct osl_table **table_ptr);
+int row_is_invalid(struct osl_table *t, uint32_t id);
+int get_mapped_object(const struct osl_table *t, unsigned col_num,
+ uint32_t id, struct osl_object *obj);
+int para_truncate(const char *filename, off_t size);
+int unmap_table(struct osl_table *t, enum osl_close_flags flags);
+int init_rbtrees(struct osl_table *t);
+
+/**
+ * Flags to be specified for map_table().
+ *
+ * \sa map_table().
+ */
+enum map_table_flags {
+ /**
+ * Check whether the entries in the table index match the entries in
+ * the table desctiption.
+ */
+ MAP_TBL_FL_VERIFY_INDEX = 1,
+ /** Do not complain even if the dirty flag is set. */
+ MAP_TBL_FL_IGNORE_DIRTY = 2,
+ /** Use read-only mappings. */
+ MAP_TBL_FL_MAP_RDONLY = 4
+};
+
+int map_table(struct osl_table *t, enum map_table_flags flags);
+void clear_rbtrees(struct osl_table *t);
+int mark_row_invalid(struct osl_table *t, uint32_t row_num);
+
+
+/**
+ * Get the description of a column by column number
+ *
+ * \param d Pointer to the table description.
+ * \param col_num The number of the column to get the desctiption for.
+ *
+ * \return The table description.
+ *
+ * \sa struct osl_column_description.
+ */
+_static_inline_ struct osl_column_description *get_column_description(
+ const struct osl_table_description *d, unsigned col_num)
+{
+ return &d->column_descriptions[col_num];
+}
+
+/**
+ * Format of the header of the index file of an osl table.
+ *
+ * Bytes 16-31 are currently unused.
+ *
+ * \sa enum index_column_desc_offsets, HASH_SIZE, osl_table_flags.
+ */
+enum index_header_offsets {
+ /** Bytes 0-8: PARASLASH. */
+ IDX_PARA_MAGIC = 0,
+ /** Byte 9: Dirty flag (nonzero if table is mapped). */
+ IDX_DIRTY_FLAG = 9,
+ /** Byte 10: osl table version number. */
+ IDX_VERSION = 10,
+ /** Byte 11: Table flags.*/
+ IDX_TABLE_FLAGS = 11,
+ /** Byte 12,13: Number of columns. */
+ IDX_NUM_COLUMNS,
+ /** Byte 14,15 Size of the index header. */
+ IDX_HEADER_SIZE = 14,
+ /** Column descriptions start here. */
+ IDX_COLUMN_DESCRIPTIONS = 32
+};
+
+/**
+ * Format of the column description in the index header.
+ *
+ * \sa index_header_offsets.
+ */
+enum index_column_desc_offsets {
+ /** Bytes 0,1: Storage_type. */
+ IDX_CD_STORAGE_TYPE = 0,
+ /** Bytes 2,3: Storage_flags. */
+ IDX_CD_STORAGE_FLAGS = 2,
+ /** Bytes 4 - 7: Data_size (only used for fixed size columns). */
+ IDX_CD_DATA_SIZE = 4,
+ /** Bytes 8 - ... Name of the column. */
+ IDX_CD_NAME = 8,
+};
+
+/** Magic string contained in the header of the index file of each osl table. */
+#define PARA_MAGIC "PARASLASH"
+
+/**
+ * The minimal number of bytes for a column in the index header.
+ *
+ * The column name starts at byte IDX_CD_NAME and must at least contain one
+ * character, plus the terminating NULL byte.
+ */
+#define MIN_IDX_COLUMN_DESCRIPTION_SIZE (IDX_CD_NAME + 2)
+
+/**
+ * Get the number of bytes used for a column in the index header.
+ *
+ * \param name The name of the column.
+ *
+ * The amount of space used for a column in the index header of a table depends
+ * on the (length of the) name of the column.
+ *
+ * \return The total number of bytes needed to store one column of this name.
+ */
+_static_inline_ size_t index_column_description_size(const char *name)
+{
+ return MIN_IDX_COLUMN_DESCRIPTION_SIZE + strlen(name) - 1;
+}
+
+#define CURRENT_TABLE_VERSION 1
+#define MIN_TABLE_VERSION 1
+#define MAX_TABLE_VERSION 1
+/** An index header must be at least that many bytes long. */
+#define MIN_INDEX_HEADER_SIZE(num_cols) (MIN_IDX_COLUMN_DESCRIPTION_SIZE \
+ * num_cols + IDX_COLUMN_DESCRIPTIONS)
+
+/**
+ * Get the number of rows from the size of the memory mapping.
+ *
+ * \param t Pointer to an open table.
+ *
+ * \return The number of rows, including invalid rows.
+ */
+_static_inline_ unsigned table_num_rows(const struct osl_table *t)
+{
+ return (t->index_map.size - t->index_header_size)
+ / t->index_entry_size;
+}
+
+/**
+ * Get the path of the index file from a table description.
+ *
+ * \param d The table description.
+ *
+ * \return The full path of the index file. Result must be freed by
+ * the caller.
+ */
+_static_inline_ char *index_filename(const struct osl_table_description *d)
+{
+ return make_message("%s/%s/index", d->dir, d->name);
+}
+
+/**
+ * Get the path of storage of a column.
+ *
+ * \param t Pointer to an initialized table.
+ * \param col_num The number of the column to get the path for.
+ *
+ * \return The full path of the mapped data file (mapped storage) or the
+ * data directory (disk storage). Result must be freed by the caller.
+ *
+ * \sa osl_storage_type.
+ */
+_static_inline_ char *column_filename(const struct osl_table *t, unsigned col_num)
+{
+ char asc[2 * HASH_SIZE + 1];
+ hash_to_asc(t->columns[col_num].name_hash, asc);
+ return make_message("%s/%s/%s", t->desc->dir, t->desc->name, asc);
+}
+
+/**
+ * Get the start of an index entry
+ *
+ * \param t Pointer to a table which has been mapped.
+ * \param row_num The number of the row whose index entry should be retrieved.
+ * \param index_entry Result is returned here.
+ *
+ * \return Positive on success, \p -E_INDEX_CORRUPTION otherwise.
+ *
+ * \sa get_index_entry().
+ */
+_static_inline_ int get_index_entry_start(const struct osl_table *t, uint32_t row_num,
+ unsigned char **index_entry)
+{
+ uint32_t index_offset;
+ index_offset = t->index_header_size + t->index_entry_size * row_num;
+ if (index_offset + 8 > t->index_map.size) {
+ *index_entry = NULL;
+ return -E_INDEX_CORRUPTION;
+ }
+ *index_entry = (unsigned char *)(t->index_map.data) + index_offset;
+ return 1;
+}
+
+/**
+ * Get the index entry of a row/column pair.
+ *
+ * \param t Pointer to a table which has been mapped.
+ * \param row_num The number of the row whose index entry should be retrieved.
+ * \param col_num The number of the column whose index entry should be retrieved.
+ * \param index_entry Result pointer.
+ *
+ * \return Positive on success, \p -E_INDEX_CORRUPTION otherwise.
+ *
+ * \sa get_index_entry_start().
+ */
+_static_inline_ int get_index_entry(const struct osl_table *t, uint32_t row_num,
+ uint32_t col_num, unsigned char **index_entry)
+{
+ int ret = get_index_entry_start(t, row_num, index_entry);
+ if (ret < 0)
+ return ret;
+ *index_entry += t->columns[col_num].index_offset;
+ return ret;
+}
+
+/**
+ * Change an index entry of a column after object was added.
+ *
+ * \param index_entry_start This determines the row.
+ * \param col Pointer to the column.
+ * \param map_size The new size of the data file.
+ * \param object_size The size of the object just appended to the data file.
+ *
+ * This is called right after an object was appended to the data file for a
+ * mapped column.
+ *
+ * \sa get_index_entry_start().
+ */
+_static_inline_ void update_index_entry(char *index_entry_start, struct osl_column *col,
+ uint32_t map_size, uint32_t object_size)
+{
+ write_u32(index_entry_start + col->index_offset, map_size - object_size - 1);
+ write_u32(index_entry_start + col->index_offset + 4, object_size + 1);
+}
+
+/**
+ * Get the full path of a disk storage object
+ *
+ * \param t Pointer to an initialized table.
+ * \param col_num The number of the column the disk storage object belongs to.
+ * \param ds_name The disk storage name of the object.
+ *
+ * \return Pointer to the full path which must be freed by the caller.
+ *
+ * \sa column_filename(), disk_storage_name_of_row().
+ */
+_static_inline_ char *disk_storage_path(const struct osl_table *t,
+ unsigned col_num, const char *ds_name)
+{
+ char *dirname = column_filename(t, col_num);
+ char *filename = make_message("%s/%s", dirname, ds_name);
+ free(dirname);
+ return filename;
+}
+
+/**
+ * Get the column description of the next column of a given type.
+ *
+ * \param type the desired storage type.
+ * \param col_num the column to start the search.
+ * \param t the osl table.
+ * \param cd result is returned here.
+ *
+ * \return On success, \a cd contains the column description of the next column
+ * of type \a type, and the number of that column is returned. Otherwise, \a
+ * cd is set to \p NULL and the function returns t->num_columns + 1.
+ *
+ * \sa FOR_EACH_COLUMN_OF_TYPE, FOR_EACH_MAPPED_COLUMN, FOR_EACH_RBTREE_COLUMN,
+ * FOR_EACH_DISK_STORAGE_COLUMN, FOR_EACH_VOLATILE_COLUMN, osl_storage_type.
+ */
+_static_inline_ int next_column_of_type(enum osl_storage_type type, int col_num,
+ const struct osl_table *t,
+ const struct osl_column_description **cd)
+{
+ *cd = NULL;
+ while (col_num < t->desc->num_columns) {
+ *cd = get_column_description(t->desc, col_num);
+ if ((*cd)->storage_type == type)
+ break;
+ col_num++;
+ }
+ return col_num;
+}
+
+/**
+ * Find the next column with an associated rbtree.
+ *
+ * \param col_num The column to start the search.
+ * \param t The osl table.
+ * \param cd Result is returned here.
+
+ * \return On success, \a cd contains the column description of the next column
+ * with associated rbtree, and the number of that column is returned.
+ * Otherwise, \a cd is set to \p NULL and the function returns t->num_columns +
+ * 1.
+ *
+ * \sa FOR_EACH_COLUMN_OF_TYPE, FOR_EACH_MAPPED_COLUMN, FOR_EACH_RBTREE_COLUMN,
+ * FOR_EACH_DISK_STORAGE_COLUMN, FOR_EACH_VOLATILE_COLUMN, osl_storage_flags.
+ */
+_static_inline_ int next_rbtree_column(int col_num, const struct osl_table *t,
+ const struct osl_column_description **cd)
+{
+ *cd = NULL;
+ while (col_num < t->desc->num_columns) {
+ *cd = get_column_description(t->desc, col_num);
+ if ((*cd)->storage_flags & OSL_RBTREE)
+ break;
+ col_num++;
+ }
+ return col_num;
+}
+
+
+/* quite some dirty hacks */
+
+/** Round up size of struct osl_row to multiple of 8 */
+#define RB_NODES_OFFSET ((sizeof(struct osl_row) + 7) / 8 * 8)
+
+/**
+ * Allocate a new osl row.
+ *
+ * \param num_rbtrees The number of rbtrees for this row.
+ *
+ * \return A pointer to a zeroed-out area suitable for holding an osl row
+ * with \a num_rbtrees rbtree columns.
+ */
+_static_inline_ struct osl_row *allocate_row(unsigned num_rbtrees)
+{
+ size_t s = RB_NODES_OFFSET + num_rbtrees * sizeof(struct rb_node);
+ return para_calloc(s);
+}
+
+/**
+ * Compute the pointer to a rbtree node embedded in a osl row.
+ *
+ * \param row The row to extract the rbtree pointer from.
+ * \param rbtree_num The number of the rbtree node to extract.
+ *
+ * \return A pointer to the \a rbtree_num th node contained in \a row.
+ */
+_static_inline_ struct rb_node *get_rb_node_pointer(const struct osl_row *row, uint32_t rbtree_num)
+{
+ return ((struct rb_node *)(((char *)row) + RB_NODES_OFFSET)) + rbtree_num;
+}
+
+/**
+ * Get a pointer to the struct containing the given rbtree node.
+ *
+ * \param node Pointer to the rbtree node.
+ * \param rbtree_num Number of \a node in the array of rbtree nodes.
+ *
+ * \return A pointer to the row containing \a node.
+ */
+_static_inline_ struct osl_row *get_row_pointer(const struct rb_node *node,
+ unsigned rbtree_num)
+{
+ node -= rbtree_num;
+ return (struct osl_row *)(((char *)node) - RB_NODES_OFFSET);
+}
+
+/**
+ * Compute a cryptographic hash of an osl object.
+ *
+ * \param obj the Object to compute the hash value from.
+ * \param hash Result is returned here.
+ */
+static inline void hash_object(const struct osl_object *obj, HASH_TYPE *hash)
+{
+ return hash_function(obj->data, obj->size, hash);
+}
+
+/**
+ * Get the relative path of an object, given the hash value.
+ *
+ * \param t Pointer to an initialized osl table.
+ * \param hash An arbitrary hash value.
+ *
+ * This function is typically called with \a hash being the hash of the object
+ * stored in the disk storage name column of a row. If the OSL_LARGE_TABLE
+ * flag is set, the first two hex digits get separated with a slash from the
+ * remaining digits.
+ *
+ * \return The relative path for all disk storage objects corresponding to \a
+ * hash.
+ *
+ * \sa struct osl_table:disk_storage_name_column.
+ */
+static inline char *disk_storage_name_of_hash(const struct osl_table *t, HASH_TYPE *hash)
+{
+ char asc[2 * HASH_SIZE + 2];
+
+ hash_to_asc(hash, asc);
+ if (t->desc->flags & OSL_LARGE_TABLE)
+ return make_message("%.2s/%s", asc, asc + 2);
+ return para_strdup(asc);
+}
+
+/**
+ * A wrapper for rename(2).
+ *
+ * \param old_path The source path.
+ * \param new_path The destination path.
+ *
+ * \return positive in success, \p -E_RENAME on errors.
+ *
+ * \sa rename(2).
+ */
+static inline int para_rename(const char *old_path, const char *new_path)
+{
+ if (rename(old_path, new_path) < 0)
+ return -E_RENAME;
+ return 1;
+}
+
+/**
+ * Iterate over each column of an initialized table.
+ *
+ * \param col A pointer to a struct osl_column.
+ * \param desc Pointer to the table description.
+ * \param cd Pointer to struct osl_column_description.
+ *
+ * On each iteration, \a col will point to the next column of the table and \a
+ * cd will point to the column description of this column.
+ *
+ * \sa struct osl_column FOR_EACH_RBTREE_COLUMN, FOR_EACH_COLUMN_OF_TYPE,
+ * FOR_EACH_MAPPED_COLUMN, FOR_EACH_DISK_STORAGE_COLUMN,
+ * FOR_EACH_VOLATILE_COLUMN.
+ */
+#define FOR_EACH_COLUMN(col, desc, cd) \
+ for (col = 0; col < (desc)->num_columns && \
+ (cd = get_column_description(desc, col)); col++)
+
+/**
+ * Iterate over each column with associated rbtree.
+ *
+ * \param col Same meaning as in FOR_EACH_COLUMN().
+ * \param table Same meaning as in FOR_EACH_COLUMN().
+ * \param cd Same meaning as in FOR_EACH_COLUMN().
+ *
+ * \sa osl_storage_flags::OSL_RBTREE, FOR_EACH_COLUMN, FOR_EACH_COLUMN_OF_TYPE,
+ * FOR_EACH_MAPPED_COLUMN, FOR_EACH_DISK_STORAGE_COLUMN,
+ * FOR_EACH_VOLATILE_COLUMN.
+ */
+#define FOR_EACH_RBTREE_COLUMN(col, table, cd) \
+ for (col = next_rbtree_column(0, table, &cd); \
+ col < table->desc->num_columns; \
+ col = next_rbtree_column(++col, table, &cd))
+
+/**
+ * Iterate over each column of given storage type.
+ *
+ * \param type The osl_storage_type to iterate over.
+ * \param col Same meaning as in FOR_EACH_COLUMN().
+ * \param table Same meaning as in FOR_EACH_COLUMN().
+ * \param cd Same meaning as in FOR_EACH_COLUMN().
+ *
+ * \sa osl_storage_type, FOR_EACH_COLUMN, FOR_EACH_RBTREE_COLUMN,
+ * FOR_EACH_MAPPED_COLUMN, FOR_EACH_DISK_STORAGE_COLUMN,
+ * FOR_EACH_VOLATILE_COLUMN.
+ */
+#define FOR_EACH_COLUMN_OF_TYPE(type, col, table, cd) \
+ for (col = next_column_of_type(type, 0, table, &cd); \
+ col < table->desc->num_columns; \
+ col = next_column_of_type(type, ++col, table, &cd))
+
+/**
+ * Iterate over each mapped column.
+ *
+ * \param col Same meaning as in FOR_EACH_COLUMN().
+ * \param table Same meaning as in FOR_EACH_COLUMN().
+ * \param cd Same meaning as in FOR_EACH_COLUMN().
+ *
+ * Just like FOR_EACH_COLUMN(), but skip columns which are
+ * not of type \p OSL_MAPPED_STORAGE.
+ *
+ * \sa osl_storage_flags::OSL_MAPPED_STORAGE, FOR_EACH_COLUMN,
+ * FOR_EACH_RBTREE_COLUMN, FOR_EACH_COLUMN_OF_TYPE,
+ * FOR_EACH_DISK_STORAGE_COLUMN, FOR_EACH_VOLATILE_COLUMN.
+ */
+#define FOR_EACH_MAPPED_COLUMN(col, table, cd) \
+ FOR_EACH_COLUMN_OF_TYPE(OSL_MAPPED_STORAGE, col, table, cd)
+
+/**
+ * Iterate over each disk storage column.
+ *
+ * \param col Same meaning as in FOR_EACH_COLUMN().
+ * \param table Same meaning as in FOR_EACH_COLUMN().
+ * \param cd Same meaning as in FOR_EACH_COLUMN().
+ *
+ * Just like FOR_EACH_COLUMN(), but skip columns which are
+ * not of type \p OSL_DISK_STORAGE.
+ *
+ * \sa osl_storage_flags::OSL_DISK_STORAGE, FOR_EACH_COLUMN,
+ * FOR_EACH_RBTREE_COLUMN, FOR_EACH_COLUMN_OF_TYPE, FOR_EACH_MAPPED_COLUMN,
+ * FOR_EACH_VOLATILE_COLUMN.
+ */
+#define FOR_EACH_DISK_STORAGE_COLUMN(col, table, cd) \
+ FOR_EACH_COLUMN_OF_TYPE(OSL_DISK_STORAGE, col, table, cd)
+
+/**
+ * Iterate over each volatile column.
+ *
+ * \param col Same meaning as in FOR_EACH_COLUMN().
+ * \param table Same meaning as in FOR_EACH_COLUMN().
+ * \param cd Same meaning as in FOR_EACH_COLUMN().
+ *
+ * Just like FOR_EACH_COLUMN(), but skip columns which are
+ * not of type \p OSL_NO_STORAGE.
+ *
+ * \sa osl_storage_flags::OSL_NO_STORAGE, FOR_EACH_COLUMN,
+ * FOR_EACH_RBTREE_COLUMN, FOR_EACH_COLUMN_OF_TYPE, FOR_EACH_MAPPED_COLUMN,
+ * FOR_EACH_DISK_STORAGE_COLUMN.
+ */
+#define FOR_EACH_VOLATILE_COLUMN(col, table, cd) \
+ FOR_EACH_COLUMN_OF_TYPE(OSL_NO_STORAGE, col, table, cd)
projects / paraslash.git / blobdiff