diff options
Diffstat (limited to 'src/filedb.c')
-rw-r--r-- | src/filedb.c | 412 |
1 files changed, 268 insertions, 144 deletions
diff --git a/src/filedb.c b/src/filedb.c index ce37ad1..9a57a68 100644 --- a/src/filedb.c +++ b/src/filedb.c @@ -14,6 +14,11 @@ * See the License for the specific language governing permissions and * limitations under the License. */ +/******************************************************************************/ +/******************************************************************************/ +/* IMPLEMENTATION OF DATABASE WITH FILE BACKEND */ +/******************************************************************************/ +/******************************************************************************/ #include <assert.h> #include <stdlib.h> @@ -31,8 +36,6 @@ #include "fbuf.h" #include "filedb.h" -#define MAX_NAME_LENGTH 32768 - /* * for the first version, save enougth time up to 4149 * 4149 = 1970 + (4294967296 * 16) / (365 * 24 * 60 * 60) @@ -125,11 +128,16 @@ struct filedb bool has_backup; /** the anydb interface */ - anydb_t db; + anydb_t anydb; }; typedef struct filedb filedb_t; -/** return the name of 'index' */ +/** + * Return the name of the given index + * @param filedb the database handler + * @param index index of the string MUST be valid + * @return the name for the index + */ static const char* name_at( @@ -153,57 +161,62 @@ cmpnames( return strcmp(name_at(filedb, a), name_at(filedb, b)); } -/** initialize names */ +/** + * Initialize the fields 'names_sorted' and 'names_count' for the + * current database. + * @param filedb the database handler + * @return 0 in case of success or -ENOMEM or -ENOEXEC + */ static int init_names( filedb_t *filedb ) { - uint32_t pos, len, *ns, *p, all, nc; + uint32_t pos, length, *sorted, *p, allocated, name_count; - all = 0; - nc = 0; - ns = NULL; + allocated = 0; + name_count = 0; + sorted = NULL; /* iterate over names */ pos = uuidlen; while (pos < filedb->fnames.used) { /* get name length */ - len = (uint32_t)strlen(name_at(filedb, pos)); - if (pos + len <= pos || pos + len > filedb->fnames.used) { - free(ns); - goto bad_file; + length = (uint32_t)strlen(name_at(filedb, pos)); + if (pos + length <= pos || pos + length > filedb->fnames.used) { + /* overflow */ + free(sorted); + fprintf(stderr, "bad file %s\n", filedb->fnames.name); + return -ENOEXEC; } /* store the position */ - if (all <= nc) { - all += 1024; - p = realloc(ns, all * sizeof *ns); + if (allocated <= name_count) { + allocated += 1024; + p = realloc(sorted, allocated * sizeof *sorted); if (p == NULL) { - free(ns); + free(sorted); fprintf(stderr, "out of memory\n"); - goto error; + return -ENOMEM; } - ns = p; + sorted = p; } - ns[nc++] = pos; + sorted[name_count++] = pos; /* next */ - pos += len + 1; + pos += length + 1; } /* sort and record */ - qsort_r(ns, nc, sizeof *ns, cmpnames, filedb); - filedb->names_sorted = ns; - filedb->names_count = nc; + qsort_r(sorted, name_count, sizeof *sorted, cmpnames, filedb); + filedb->names_sorted = sorted; + filedb->names_count = name_count; return 0; - -bad_file: - fprintf(stderr, "bad file %s\n", filedb->fnames.name); - errno = ENOEXEC; -error: - return -1; } -/** init the rules from the file */ +/** + * Initialize the fields 'rules' and 'rules_count' for the + * current database. + * @param filedb the database handler + */ static void init_rules( @@ -213,7 +226,21 @@ init_rules( filedb->rules_count = (filedb->frules.used - uuidlen) / sizeof *filedb->rules; } -/** open a fbuf */ +/** + * Open the fbuf 'fb' in the directory, the name and the extension. + * Check that the identifier prefix matches or if the file doesn't exist + * create the prefix. + * @param fb the buffer to open + * @param directory the directory containing the file + * @param name the basename for the file + * @param extension the extension of the file + * @param id the identifier prefix + * @param idlen the length of the identifier prefix + * @return 0 in case of success + * -ENOMEM if out of memory + * -ENOKEY if identification failed + * a negative -errno code + */ static int open_identify( @@ -224,25 +251,38 @@ open_identify( const char *id, uint32_t idlen ) { - char *file, *backup, *p; + char *file, *p; size_t ldir, lext, lname; + /* compute sizes */ ldir = strlen(directory); lname = strlen(name); lext = strlen(extension); - file = alloca(((ldir + lname + lext) << 1) + 7); + + /* allocate memory for file */ + file = alloca((ldir + lname + lext) + 3); + + /* make the file's name: directory/name.extension */ p = mempcpy(file, directory, ldir); *p++ = '/'; p = mempcpy(p, name, lname); *p++ = '.'; - backup = mempcpy(p, extension, lext + 1); - p = mempcpy(backup, file, ldir + lname + lext + 2); - *p++ = '~'; - *p = 0; - return fbuf_open_identify(fb, file, backup, id, idlen); + mempcpy(p, extension, lext + 1); + + /* open the fbuf now */ + return fbuf_open_identify(fb, file, NULL, id, idlen); } -/** open the database for files 'names' and 'rules' (can be NULL) */ +/** + * Open the database of 'name' in 'directory' + * @param filedb the database handler to open + * @param directory the directory containing the database (or null for default) + * @param name the basename for the file + * @return 0 in case of success + * -ENOMEM if out of memory + * -ENOKEY if identification failed + * a negative -errno code + */ static int opendb( @@ -262,26 +302,27 @@ opendb( /* open the names */ rc = open_identify(&filedb->fnames, directory, name, "names", uuid_names_v2, uuidlen); - if (rc < 0) - goto error; - - /* open the rules */ - rc = open_identify(&filedb->frules, directory, name, "rules", uuid_rules_v2, uuidlen); - if (rc < 0) - goto error; - - /* connect internals */ - rc = init_names(filedb); - if (rc < 0) - goto error; - - init_rules(filedb); - return 0; -error: - return -1; + if (rc == 0) { + /* open the rules */ + rc = open_identify(&filedb->frules, directory, name, "rules", uuid_rules_v2, uuidlen); + if (rc == 0) { + /* connect internals */ + rc = init_names(filedb); + if (rc == 0) { + init_rules(filedb); + return 0; + } + fbuf_close(&filedb->frules); + } + fbuf_close(&filedb->fnames); + } + return rc; } -/** close the database */ +/** + * Close the database + * @param filedb database to close + */ static void closedb( @@ -292,7 +333,12 @@ closedb( fbuf_close(&filedb->frules); } -/** synchronize db on files */ +/** + * Synchronize database and its files (write it to the filesystem) + * @param filedb database to synchronize + * @return 0 in case of success + * a negative -errno code + */ static int syncdb( @@ -302,10 +348,12 @@ syncdb( assert(filedb->fnames.name && filedb->frules.name); if (!filedb->is_changed) - rc = 0; + rc = 0; /* unchanged */ else { + /* sync the names */ rc = fbuf_sync(&filedb->fnames); if (rc == 0) { + /* sync the rules */ rc = fbuf_sync(&filedb->frules); if (rc == 0) { filedb->is_changed = false; @@ -316,7 +364,12 @@ syncdb( return rc; } -/** make a backup of the database */ +/** + * Creates backups of the database + * @param filedb the database to backup + * @return 0 in case of success + * a negative -errno code + */ static int backupdb( @@ -326,21 +379,26 @@ backupdb( assert(filedb->fnames.name && filedb->frules.name); if (filedb->has_backup) - rc = 0; + rc = 0; /* already backuped */ else { + /* backup names */ rc = fbuf_backup(&filedb->fnames); if (rc == 0) { + /* backup rules */ rc = fbuf_backup(&filedb->frules); - if (rc == 0) { + if (rc == 0) filedb->has_backup = true; - filedb->is_changed = false; - } } } return rc; } -/** recover the database from latest backup */ +/** + * recover the database from latest backup + * @param filedb database to recover + * @return 0 in case of success + * a negative -errno code + */ static int recoverdb( @@ -352,14 +410,17 @@ recoverdb( if (!filedb->is_changed || !filedb->has_backup) rc = 0; else { + /* recover names */ rc = fbuf_recover(&filedb->fnames); if (rc < 0) goto error; + /* recover rules */ rc = fbuf_recover(&filedb->frules); if (rc < 0) goto error; + /* init names */ rc = init_names(filedb); if (rc < 0) goto error; @@ -375,6 +436,7 @@ error: return rc; } +/** implementation of anydb_itf.index */ static int index_itf( @@ -446,6 +508,7 @@ index_itf( return 0; } +/** implementation of anydb_itf.string */ static const char * string_itf( @@ -454,14 +517,16 @@ string_itf( ) { filedb_t *filedb = clodb; + assert(idx < filedb->fnames.used); return name_at(filedb, idx); } +/** implementation of anydb_itf.apply */ static void apply_itf( void *clodb, - anydb_action_t (*oper)(void *closure, const anydb_key_t *key, anydb_value_t *value), + anydb_applycb_t *oper, void *closure ) { filedb_t *filedb = clodb; @@ -469,7 +534,7 @@ apply_itf( rule_t *rule; anydb_key_t key; anydb_value_t value; - uint32_t i; + uint32_t i, saved; key.session = AnyIdx_Wide; i = 0; @@ -481,29 +546,30 @@ apply_itf( value.value = rule->value; value.expire = exp2time(rule->expire); a = oper(closure, &key, &value); - switch (a) { - case Anydb_Action_Stop: - return; - case Anydb_Action_Continue: - i++; - break; - case Anydb_Action_Update_And_Stop: - rule->value = value.value; - rule->expire = time2exp(value.expire); - filedb->need_cleanup = true; - filedb->is_changed = true; - filedb->frules.saved = (uint32_t)((void*)rule - filedb->frules.buffer); - return; - case Anydb_Action_Remove_And_Continue: + if (a & Anydb_Action_Remove) { *rule = filedb->rules[--filedb->rules_count]; filedb->is_changed = true; filedb->need_cleanup = true; + saved = (uint32_t)((void*)rule - filedb->frules.buffer); + if (saved < filedb->frules.saved) + filedb->frules.saved = saved; filedb->frules.used -= (uint32_t)sizeof *rule; - break; + } else if (a & Anydb_Action_Update) { + rule->value = value.value; + rule->expire = time2exp(value.expire); + filedb->need_cleanup = true; + filedb->is_changed = true; + saved = (uint32_t)((void*)rule - filedb->frules.buffer); + if (saved < filedb->frules.saved) + filedb->frules.saved = saved; } + if (a & Anydb_Action_Stop) + return; + i += !(a & Anydb_Action_Remove); } } +/** implementation of anydb_itf.transaction */ static int transaction_itf( @@ -531,6 +597,7 @@ transaction_itf( return rc; } +/** implementation of anydb_itf.add */ static int add_itf( @@ -562,6 +629,16 @@ add_itf( return 0; } +/** + * Search (dig) dichotomically in 'array' of 'count' elements the index of + * 'item'. Store '*index' either the index of the found item or the index + * where inserting the item. Return true if found of false otherwise. + * @param array array to dig + * @param count count of elements in array + * @param item item to dig + * @param index where to store the found index + * @return true if found of false otherwise. + */ static bool gc_dig( @@ -593,6 +670,13 @@ gc_dig( return false; } +/** + * Add dichotomically the 'item' in the 'array' of 'count' elements + * @param array array to alter + * @param count count of element in the input array + * @param item the item to add + * @return the new count of elements + */ static uint32_t gc_add( @@ -602,18 +686,29 @@ gc_add( ) { uint32_t index, i; + /* search the item */ if (gc_dig(array, count, item, &index)) - return count; + return count; /* already in */ + /* shift the elemetns above index */ i = count; while (i > index) { array[i] = array[i - 1]; i = i - 1; } + + /* add the item */ array[i] = item; return count + 1; } +/** + * Mark in 'array' of 'count' elements the 'item' + * @param array the sorted array of marked items + * @param count the count of marked items + * @param item the item to mark + * @return the new count of marked items + */ static uint32_t gc_mark( @@ -624,30 +719,60 @@ gc_mark( return item > AnyIdx_Max ? count : gc_add(array, count, item); } +/** + * Test if 'item' is marked in 'array' of 'count' marked elements + * @param array the sorted array of marked items + * @param count the count of marked items + * @param item the item to search + * @param index where to store the index of the item if found + * @return true is found (marked) or false otherwise (not marked) + */ static bool -gc_new( +gc_is_marked( uint32_t *array, uint32_t count, uint32_t item, uint32_t *index ) { - return item > AnyIdx_Max ? false : gc_dig(array, count, item, index); + return item <= AnyIdx_Max && gc_dig(array, count, item, index); +} + +/** + * Translate the item pointed by 'item' to its new value after renumeration + * @param marked the sorted array of marked items + * @param renum the renumerotation of the marked items + * @param count the count of marked items + * @param item the pointer to the item to modify + */ +static +void +gc_renum( + uint32_t *marked, + uint32_t *renum, + uint32_t count, + uint32_t *item +) { + uint32_t index; + + if (gc_is_marked(marked, count, *item, &index)) + *item = renum[index]; } +/** implementation of anydb_itf.gc */ static void gc_itf( void *clodb ) { filedb_t *filedb = clodb; - uint32_t nr; - uint32_t nn; + uint32_t rule_count; + uint32_t name_count; struct rule *rules; - uint32_t *used; - uint32_t *sorted; + uint32_t *marked; + uint32_t *renum; char *strings; - uint32_t ir, nu, idx, is, ios, lenz; + uint32_t irule, new_count, imarked, istr_before, istr_after, lenz; /* check cleanup required */ if (!filedb->need_cleanup) @@ -655,60 +780,57 @@ gc_itf( filedb->need_cleanup = false; /* mark items */ - nr = filedb->rules_count; - nn = filedb->names_count; + rule_count = filedb->rules_count; + name_count = filedb->names_count; rules = filedb->rules; - used = alloca(nn * sizeof *used); - nu = 0; - for (ir = 0 ; ir < nr ; ir++) { - nu = gc_mark(used, nu, rules[ir].client); - nu = gc_mark(used, nu, rules[ir].user); - nu = gc_mark(used, nu, rules[ir].permission); - nu = gc_mark(used, nu, rules[ir].value); + marked = alloca(name_count * sizeof *marked); + new_count = 0; + for (irule = 0 ; irule < rule_count ; irule++) { + new_count = gc_mark(marked, new_count, rules[irule].client); + new_count = gc_mark(marked, new_count, rules[irule].user); + new_count = gc_mark(marked, new_count, rules[irule].permission); + new_count = gc_mark(marked, new_count, rules[irule].value); } /* pack if too much unused */ - if (nu + (nu >> 2) <= nn) + if (new_count + (new_count >> 2) >= name_count) return; - /* pack the names */ + /* pack the names by removing the unused strings */ strings = (char*)filedb->fnames.buffer; - sorted = filedb->names_sorted; - is = ios = uuidlen; - while (is < filedb->fnames.used) { + renum = filedb->names_sorted; + istr_before = istr_after = uuidlen; + while (istr_before < filedb->fnames.used) { /* get name length */ - lenz = 1 + (uint32_t)strlen(strings + is); - if (gc_dig(used, nu, is, &idx)) { - sorted[idx] = ios; - if (is != ios) - memcpy(strings + ios, strings + is, lenz); - ios += lenz; + lenz = 1 + (uint32_t)strlen(strings + istr_before); + if (gc_is_marked(marked, new_count, istr_before, &imarked)) { + renum[imarked] = istr_after; + if (istr_before != istr_after) + memcpy(strings + istr_after, strings + istr_before, lenz); + istr_after += lenz; } /* next */ - is += lenz; + istr_before += lenz; } /* renum the rules */ - for (ir = 0 ; ir < nr ; ir++) { - if (gc_new(used, nu, rules[ir].client, &idx)) - rules[ir].client = sorted[idx]; - if (gc_new(used, nu, rules[ir].user, &idx)) - rules[ir].user = sorted[idx]; - if (gc_new(used, nu, rules[ir].permission, &idx)) - rules[ir].permission = sorted[idx]; - if (gc_new(used, nu, rules[ir].value, &idx)) - rules[ir].value = sorted[idx]; + for (irule = 0 ; irule < rule_count ; irule++) { + gc_renum(marked, renum, new_count, &rules[irule].client); + gc_renum(marked, renum, new_count, &rules[irule].user); + gc_renum(marked, renum, new_count, &rules[irule].permission); + gc_renum(marked, renum, new_count, &rules[irule].value); } /* record and sort */ - filedb->names_count = nu; - filedb->fnames.used = ios; - qsort_r(sorted, nu, sizeof *sorted, cmpnames, filedb); + filedb->names_count = new_count; + filedb->fnames.used = istr_after; + qsort_r(renum, new_count, sizeof *renum, cmpnames, filedb); /* set as changed */ filedb->is_changed = true; } +/** implementation of anydb_itf.sync */ static int sync_itf( @@ -718,6 +840,7 @@ sync_itf( return syncdb(filedb); } +/** implementation of anydb_itf.destroy */ static void destroy_itf( @@ -731,23 +854,28 @@ destroy_itf( } } +/** + * Initialize the anydb interface of filedb + * @param filedb the structure to initialize + */ static void -init( +init_anydb_itf( filedb_t *filedb ) { - filedb->db.clodb = filedb; - - filedb->db.itf.index = index_itf; - filedb->db.itf.string = string_itf; - filedb->db.itf.transaction = transaction_itf; - filedb->db.itf.apply = apply_itf; - filedb->db.itf.add = add_itf; - filedb->db.itf.gc = gc_itf; - filedb->db.itf.sync = sync_itf; - filedb->db.itf.destroy = destroy_itf; + filedb->anydb.clodb = filedb; + + filedb->anydb.itf.index = index_itf; + filedb->anydb.itf.string = string_itf; + filedb->anydb.itf.transaction = transaction_itf; + filedb->anydb.itf.apply = apply_itf; + filedb->anydb.itf.add = add_itf; + filedb->anydb.itf.gc = gc_itf; + filedb->anydb.itf.sync = sync_itf; + filedb->anydb.itf.destroy = destroy_itf; } +/* see filedb.h */ int filedb_create( anydb_t **adb, @@ -757,25 +885,21 @@ filedb_create( int rc; filedb_t *filedb; + /* allocates */ *adb = NULL; filedb = calloc(1, sizeof *filedb); if (!filedb) return -ENOMEM; - init(filedb); + /* init anydb interface */ + init_anydb_itf(filedb); + /* open the database file */ rc = opendb(filedb, directory, basename); if (rc) free(filedb); else - *adb = &filedb->db; + *adb = &filedb->anydb; return rc; } -/** synchronize database */ -int -anydb_sync( - anydb_t *db -) { - return db->itf.sync ? db->itf.sync(db->clodb) : 0; -} |