mmap_cache.h

/*
 * AUTHOR
 *
 * Rob Mueller <cpan@robm.fastmail.fm>
 *
 * COPYRIGHT AND LICENSE
 *
 * Copyright (C) 2003 by FastMail IP Partners
 *
 * This library is free software; you can redistribute it and/or modify
 * it under the same terms as Perl itself. 
 * 
 * mmap_cache
 *
 * Uses an mmap'ed file to act as a shared memory interprocess cache
 * 
 * The C interface is quite explicit in it's use, in that you have to
 * call individual functions to hash a key, lock a page, and find a
 * value. This allows a simpler higher level interface to be written
 *
 *  #include <mmap_cache.h>
 *  
 *  mmap_cache * cache = mmc_new();
 *  cache->param = val;
 *  mmc_init(cache);
 *
 *  // Read a key
 *
 *  // Hash get to find page and slot
 *  mmc_hash(cache, (void *)key_ptr, (int)key_len, &hash_page, &hash_slot);
 *  // Lock page
 *  mmc_lock(cache, hash_page);
 *  // Get pointer to value data
 *  mmc_read(cache, hash_slot, (void *)key_ptr, (int)key_len, (void **)&val_ptr, (int *)val_len, &expire_time, &flags);
 *  // Unlock page
 *  mmc_unlock(cache);
 *
 *  // Write a key
 *
 *  // Hash get to find page and slot
 *  mmc_hash(cache, (void *)key_ptr, (int)key_len, &hash_page, &hash_slot);
 *  // Lock page
 *  mmc_lock(cache, hash_page);
 *  // Get pointer to value data
 *  mmc_write(cache, hash_slot, (void *)key_ptr, (int)key_len, (void *)val_ptr, (int)val_len, expire_time, flags);
 *  // Unlock page
 *  mmc_unlock(cache);
 *
 * DESCRIPTION
 * 
 * This class implements a shared memory cache through an mmap'ed file. It
 * uses locking to ensure multiple processes can safely access the cache
 * at the same time. It uses a basic LRU algorithm to keep the most used
 * entries in the cache.
 * 
 * It tries to be quite efficient through a number of means:
 * 
 * It uses multiple pages within a file, and uses Fcntl to only lock
 * a page at a time to reduce contention when multiple processes access
 * the cache.
 * 
 * It uses a dual level hashing system (hash to find page, then hash
 * within each page to find a slot) to make most I<read> calls O(1) and
 * fast
 * 
 * On each I<write>, if there are slots and page space available, only
 * the slot has to be updated and the data written at the end of the used
 * data space. If either runs out, a re-organisation of the page is
 * performed to create new slots/space which is done in an efficient way
 * 
 * The locking is explicitly done in the C interface, so you can create
 * a 'read_many' or 'write_many' function that reduces the number of
 * locks required
 * 
 * 
 * IMPLEMENTATION
 * 
 * Each file is made up of a number of 'pages'. The number of
 * pages and size of each page is specified when the class is
 * constructed. These values are stored in the cache class
 * and must be the same for each class connecting to the cache
 * file.
 * 
 * NumPages - Number of 'pages' in the cache
 * PageSize - Size of each 'page' in the cache
 * 
 * The layout of each page is:
 * 
 * - Magic (4 bytes) - 0x92f7e3b1 magic page start marker
 *
 * - NumSlots (4 bytes) - Number of hash slots in this page
 *
 * - FreeSlots (4 bytes) - Number of free slots left in this page.
 *   This includes all slots with a last access time of 0
 *   (empty and don't search past) or 1 (empty, but keep searching
 *   because deleted slot)
 * 
 * - OldSlots (4 bytes) - Of all the free slots, how many were in use
 *   and are now deleted. This is slots with a last access time of 1
 * 
 * - FreeData (4 bytes) - Offset to free data area to place next item
 * 
 * - FreeBytes (4 bytes) - Bytes left in free data area
 * 
 * - N Reads (4 bytes) - Number of reads performed on this page
 *
 * - N Read Hits (4 bytes) - Number of reads on this page that have hit
 *   something in the cache
 * 
 * - Slots (4 bytes * NumSlots) - Hash slots
 *
 * - Data (to end of page) - Key/value data
 * 
 * Each slot is made of:
 * 
 * - Offset (4 bytes) - offset from start of page to actual data. This
 *   is 0 if slot is empty, 1 if was used but now empty. This is needed
 *   so deletes don't require a complete rehash with the linear
 *   searching method we use
 *
 * Each data item is made of:
 *
 * - LastAccess (4 bytes) - Unix time data was last accessed
 * 
 * - ExpireTime (4 bytes) - Unix time data should expire. This is 0 if it
 *   should never expire
 * 
 * - HashValue (4 bytes) - Value key was hashed to, so we don't have to
 *   rehash on a re-organisation of the hash table
 *
 * - Flags (4 bytes) - Various flags
 * 
 * - KeyLen (4 bytes) - Length of key
 * 
 * - ValueLen (4 bytes) - Length of value
 * 
 * - Key (KeyLen bytes) - Key data
 * 
 * - Value (ValueLen bytes) - Value data
 * 
 * Each set/get/delete operation involves:
 * 
 * - Find the page for the key
 * - Lock the page
 * - Read the page header
 * - Find the hash slot for the key
 * 
 * For get's:
 * 
 * - Use linear probing to find correct key, or empty slot
 * 
 * For set's:
 * 
 * - Use linear probing to find empty slot
 * - If not enough free slots, do an 'expunge' run
 * - Store key/value at FreeData offset, update, and store in slot
 * - If not enough space at FreeData offset, do an 'expunge' run
 *    then store data
 * 
 * For delete's:
 * 
 * - Use linear probing to find correct key, or empty slot
 * - Set slot to empty (data cleaned up in expunge run)
 * 
 * An expunge run consists of:
 * 
 * - Scan slots to find used key/value parts. Remove older items
 * - If ratio used/free slots too high, increase slot count
 * - Compact key/value data into one memory block
 * - Restore and update offsets in slots
 * 
*/

#include <stdint.h>

/* Main cache structure passed as a pointer to each function */
typedef struct mmap_cache mmap_cache;

/* Iterator structure for iterating over items in cache */
typedef struct mmap_cache_it mmap_cache_it;

/* Unsigned 32 bit integer */
typedef uint32_t MU32;

/* Unsigned 64 bit integer */
typedef uint64_t MU64;

/* Magic value for no p_cur */
#define NOPAGE (~(MU32)0)

/* Allow overriding "time" for tests */
void mmc_set_time_override(MU32);

/* Initialisation/closing/error functions */
mmap_cache * mmc_new();
int mmc_init(mmap_cache *);
int mmc_set_param(mmap_cache *, char *, char *);
int mmc_get_param(mmap_cache *, char *);
int mmc_close(mmap_cache *);
char * mmc_error(mmap_cache *);

/* Functions for find/locking a page */
int mmc_hash(mmap_cache *, void *, int, MU32 *, MU32 *);
int mmc_lock(mmap_cache *, MU32);
int mmc_unlock(mmap_cache *);
int mmc_is_locked(mmap_cache *);

/* Functions for getting/setting/deleting values in current page */
int mmc_read(mmap_cache *, MU32, void *, int, void **, int *, MU32 *, MU32 *);
int mmc_write(mmap_cache *, MU32, void *, int, void *, int, MU32, MU32);
int mmc_delete(mmap_cache *, MU32, void *, int, MU32 *);

/* Functions of expunging values in current page */
int mmc_calc_expunge(mmap_cache *, int, int, MU32 *, MU32 ***);
int mmc_do_expunge(mmap_cache *, int, MU32, MU32 **);

/* Functions for iterating over items in a cache */
mmap_cache_it * mmc_iterate_new(mmap_cache *);
MU32 * mmc_iterate_next(mmap_cache_it *);
void mmc_iterate_close(mmap_cache_it *);

/* Retrieve details of a cache page/entry */
void mmc_get_details(mmap_cache *, MU32 *, void **, int *, void **, int *, MU32 *, MU32 *, MU32 *);
void mmc_get_page_details(mmap_cache * cache, MU32 * nreads, MU32 * nreadhits);
void mmc_reset_page_details(mmap_cache * cache);

/* Internal functions */
int _mmc_set_error(mmap_cache *, int, char *, ...);
void _mmc_init_page(mmap_cache *, MU32);

MU32 * _mmc_find_slot(mmap_cache * , MU32 , void *, int, int );
void _mmc_delete_slot(mmap_cache * , MU32 *);

int _mmc_check_expunge(mmap_cache * , int);

int  _mmc_test_page(mmap_cache *);
int  _mmc_dump_page(mmap_cache *);