diff options
| -rw-r--r-- | src/CMakeLists.txt | 3 | ||||
| -rw-r--r-- | src/anydb.c | 490 | ||||
| -rw-r--r-- | src/anydb.h | 142 | ||||
| -rw-r--r-- | src/cyn.c | 4 | ||||
| -rw-r--r-- | src/data.h | 6 | ||||
| -rw-r--r-- | src/db.c | 803 | ||||
| -rw-r--r-- | src/db.h | 9 | ||||
| -rw-r--r-- | src/fdb.c | 865 | ||||
| -rw-r--r-- | src/fdb.h | 99 | ||||
| -rw-r--r-- | src/memdb.c | 279 | ||||
| -rw-r--r-- | src/memdb.h | 24 |
11 files changed, 1950 insertions, 774 deletions
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index cacd659..319ece1 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -17,12 +17,15 @@ ########################################################################### set(SERVER_SOURCES + anydb.c cyn.c db.c dbinit.c expire.c fbuf.c + fdb.c main-cynarad.c + memdb.c pollitem.c prot.c queue.c diff --git a/src/anydb.c b/src/anydb.c new file mode 100644 index 0000000..d284610 --- /dev/null +++ b/src/anydb.c @@ -0,0 +1,490 @@ +/* + * Copyright (C) 2018 "IoT.bzh" + * Author José Bollo <jose.bollo@iot.bzh> + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <stdlib.h> +#include <stdint.h> +#include <stdbool.h> +#include <time.h> +#include <string.h> +#include <errno.h> + +#include "data.h" +#include "anydb.h" + + +#define CLIENT_MATCH_SCORE 1 +#define SESSION_MATCH_SCORE 1 +#define USER_MATCH_SCORE 1 +#define PERMISSION_MATCH_SCORE 1 + +/******************************************************************************/ +/******************************************************************************/ +/*** UTILITIES ***/ +/******************************************************************************/ +/******************************************************************************/ + +/** check whether the 'text' fit String_Any, NULL or "" */ +static +bool +is_any( + const char *text +) { + return text == NULL || text[0] == 0 || (!text[1] && text[0] == Data_Any_Char); +} + +/** check whether the 'text' fit String_Any, String_Wide, NULL or "" */ +static +bool +is_any_or_wide( + const char *text +) { + return text == NULL || text[0] == 0 + || (!text[1] && (text[0] == Data_Any_Char || text[0] == Data_Wide_Char)); +} + +/** return the name of 'index' */ +static +const char* +string( + anydb_t *db, + anydb_idx_t idx +) { + if (idx == AnyIdx_Any) + return Data_Any_String; + if (idx == AnyIdx_Wide) + return Data_Wide_String; + return db->itf.string(db->clodb, idx); +} + +/** search the index of 'name' and create it if 'create' */ +static +int +idx( + anydb_t *db, + anydb_idx_t *idx, + const char *name, + bool create +) { + /* special names */ + if (!name || !name[0]) { + *idx = AnyIdx_Any; + return 0; + } + if (!name[1]) { + if (name[0] == Data_Any_Char) { + *idx = AnyIdx_Any; + return 0; + } + if (name[0] == Data_Wide_Char) { + *idx = AnyIdx_Wide; + return 0; + } + } + + /* other case */ + return db->itf.index(db->clodb, idx, name, create); +} + +/** search the index of 'name' and create it if 'create' */ +static +int +idx_but_any( + anydb_t *db, + anydb_idx_t *idx, + const char *name, + bool create +) { + if (is_any_or_wide(name)) { + *idx = AnyIdx_Wide; + return 0; + } + + /* other case */ + return db->itf.index(db->clodb, idx, name, create); +} + +/** search the index of 'name' and create it if 'create' */ +static +anydb_idx_t +idx_or_none_but_any( + anydb_t *db, + const char *name, + bool create +) { + anydb_idx_t idx; + + if (idx_but_any(db, &idx, name, create)) + idx = AnyIdx_None; + return idx; +} + +/******************************************************************************/ +/******************************************************************************/ +/*** FOR ALL ***/ +/******************************************************************************/ +/******************************************************************************/ + +struct for_all_s +{ + anydb_t *db; + void *closure; + void (*callback)( + void *closure, + const data_key_t *key, + const data_value_t *value); + anydb_idx_t idxcli; + anydb_idx_t idxses; + anydb_idx_t idxusr; + const char *strperm; + time_t now; +}; + +static +anydb_action_t +for_all_cb( + void *closure, + const anydb_key_t *key, + anydb_value_t *value +) { + struct for_all_s *s = closure; + data_key_t k; + data_value_t v; + + if (value->expire && value->expire <= s->now) + return Anydb_Action_Remove_And_Continue; + + if ((s->idxcli == AnyIdx_Any || s->idxcli == key->client) + && (s->idxses == AnyIdx_Any || s->idxses == key->session) + && (s->idxusr == AnyIdx_Any || s->idxusr == key->user)) { + k.permission = string(s->db, key->permission); + if (!s->strperm || !strcasecmp(s->strperm, k.permission)) { + k.client = string(s->db, key->client); + k.session = string(s->db, key->session); + k.user = string(s->db, key->user); + v.value = string(s->db, value->value); + v.expire = value->expire; + s->callback(s->closure, &k, &v); + } + } + return Anydb_Action_Continue; +} + +/** enumerate */ +void +anydb_for_all( + anydb_t *db, + void *closure, + void (*callback)( + void *closure, + const data_key_t *key, + const data_value_t *value), + const data_key_t *key +) { + struct for_all_s s; + + s.db = db; + s.closure = closure; + s.callback = callback; + + if (idx(db, &s.idxcli, key->client, false) + || idx(db, &s.idxses, key->session, false) + || idx(db, &s.idxusr, key->user, false)) + return; /* nothing to do! because one of the idx doesn't exist */ + s.strperm = is_any(key->permission) ? NULL : key->permission; + + s.now = time(NULL); + db->itf.apply(db->clodb, for_all_cb, &s); +} + +/******************************************************************************/ +/******************************************************************************/ +/*** DROP ***/ +/******************************************************************************/ +/******************************************************************************/ + +struct drop_s +{ + anydb_t *db; + anydb_idx_t idxcli; + anydb_idx_t idxses; + anydb_idx_t idxusr; + const char *strperm; + time_t now; +}; + +static +anydb_action_t +drop_cb( + void *closure, + const anydb_key_t *key, + anydb_value_t *value +) { + struct drop_s *s = closure; + + if (value->expire && value->expire <= s->now) + return Anydb_Action_Remove_And_Continue; + + if ((s->idxcli == AnyIdx_Any || s->idxcli == key->client) + && (s->idxses == AnyIdx_Any || s->idxses == key->session) + && (s->idxusr == AnyIdx_Any || s->idxusr == key->user) + && (!s->strperm || !strcasecmp(s->strperm, string(s->db, key->permission)))) + return Anydb_Action_Remove_And_Continue; + + return Anydb_Action_Continue; +} + +/** drop rules */ +int +anydb_drop( + anydb_t *db, + const data_key_t *key +) { + struct drop_s s; + + s.db = db; + + if (idx(db, &s.idxcli, key->client, false) + || idx(db, &s.idxses, key->session, false) + || idx(db, &s.idxusr, key->user, false)) + return 0; /* nothing to do! because one of the idx doesn't exist */ + s.strperm = is_any(key->permission) ? NULL : key->permission; + + s.now = time(NULL); + db->itf.apply(db->clodb, drop_cb, &s); + return 0; +} + +/******************************************************************************/ +/******************************************************************************/ +/*** ADD ***/ +/******************************************************************************/ +/******************************************************************************/ + +struct set_s +{ + anydb_t *db; + anydb_idx_t idxcli; + anydb_idx_t idxses; + anydb_idx_t idxusr; + anydb_idx_t idxval; + time_t expire; + const char *strperm; + time_t now; +}; + +static +anydb_action_t +set_cb( + void *closure, + const anydb_key_t *key, + anydb_value_t *value +) { + struct set_s *s = closure; + + if (value->expire && value->expire <= s->now) + return Anydb_Action_Remove_And_Continue; + + if (s->idxcli == key->client + && s->idxses == key->session + && s->idxusr == key->user + && !strcasecmp(s->strperm, string(s->db, key->permission))) { + value->value = s->idxval; + value->expire = s->expire; + s->db = NULL; + return Anydb_Action_Update_And_Stop; + } + + return Anydb_Action_Continue; +} + +int +anydb_set( + anydb_t *db, + const data_key_t *key, + const data_value_t *value +) { + int rc; + struct set_s s; + anydb_key_t k; + anydb_value_t v; + + s.db = db; + s.strperm = key->permission; + s.expire = value->expire; + + rc = idx_but_any(db, &s.idxcli, key->client, true); + if (rc) + goto error; + rc = idx_but_any(db, &s.idxses, key->session, true); + if (rc) + goto error; + rc = idx_but_any(db, &s.idxusr, key->user, true); + if (rc) + goto error; + rc = idx(db, &s.idxval, value->value, true); + if (rc) + goto error; + + s.now = time(NULL); + db->itf.apply(db->clodb, set_cb, &s); + if (s.db) { + if (idx(db, &k.permission, s.strperm, true)) + goto error; + k.client = s.idxcli; + k.user = s.idxusr; + k.session = s.idxses; + v.value = s.idxval; + v.expire = s.expire; + rc = db->itf.add(db->clodb, &k, &v); + if (rc) + goto error; + } + return 0; +error: + return rc; +} + +/******************************************************************************/ +/******************************************************************************/ +/*** TEST ***/ +/******************************************************************************/ +/******************************************************************************/ + +struct test_s +{ + anydb_t *db; + anydb_idx_t idxcli; + anydb_idx_t idxses; + anydb_idx_t idxusr; + const char *strperm; + int score; + anydb_idx_t idxval; + time_t expire; + time_t now; +}; + +static +anydb_action_t +test_cb( + void *closure, + const anydb_key_t *key, + anydb_value_t *value +) { + struct test_s *s = closure; + int sc; + + if (value->expire && value->expire <= s->now) + return Anydb_Action_Remove_And_Continue; + + if ((s->idxcli == key->client || key->client == AnyIdx_Wide) + && (s->idxses == key->session || key->session == AnyIdx_Wide) + && (s->idxusr == key->user || key->user == AnyIdx_Wide) + && (AnyIdx_Wide == key->permission + || !strcasecmp(s->strperm, string(s->db, key->permission)))) { + sc = 1; + if (key->client != AnyIdx_Wide) + sc += CLIENT_MATCH_SCORE; + if (key->session != AnyIdx_Wide) + sc += SESSION_MATCH_SCORE; + if (key->user != AnyIdx_Wide) + sc += USER_MATCH_SCORE; + if (key->permission != AnyIdx_Wide) + sc += PERMISSION_MATCH_SCORE; + if (sc > s->score) { + s->score = sc; + s->idxval = value->value; + s->expire = value->expire; + } + } + return Anydb_Action_Continue; +} + +int +anydb_test( + anydb_t *db, + const data_key_t *key, + data_value_t *value +) { + struct test_s s; + + s.db = db; + s.now = time(NULL); + s.strperm = key->permission; + s.expire = value->expire; + + s.idxcli = idx_or_none_but_any(db, key->client, true); + s.idxses = idx_or_none_but_any(db, key->session, true); + s.idxusr = idx_or_none_but_any(db, key->user, true); + + s.expire = -1; + s.idxval = AnyIdx_Invalid; + s.score = 0; + + db->itf.apply(db->clodb, test_cb, &s); + + if (s.score) { + value->value = string(db, s.idxval); + value->expire = s.expire; + } else { + value->value = NULL; + value->expire = 0; + } + return s.score; +} + +/******************************************************************************/ +/******************************************************************************/ +/*** CLEANUP ***/ +/******************************************************************************/ +/******************************************************************************/ + +static +anydb_action_t +cleanup_cb( + void *closure, + const anydb_key_t *key, + anydb_value_t *value +) { + if (value->expire && value->expire <= *(time_t*)closure) + return Anydb_Action_Remove_And_Continue; + + return Anydb_Action_Continue; +} + +void +anydb_cleanup( + anydb_t *db +) { + time_t t; + + t = time(NULL); + db->itf.apply(db->clodb, cleanup_cb, &t); + db->itf.gc(db->clodb); +} + +/******************************************************************************/ +/******************************************************************************/ +/*** DESTROY ***/ +/******************************************************************************/ +/******************************************************************************/ + +void +anydb_destroy( + anydb_t *db +) { + db->itf.destroy(db->clodb); +} diff --git a/src/anydb.h b/src/anydb.h new file mode 100644 index 0000000..33f0447 --- /dev/null +++ b/src/anydb.h @@ -0,0 +1,142 @@ +/* + * Copyright (C) 2018 "IoT.bzh" + * Author José Bollo <jose.bollo@iot.bzh> + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#pragma once + +/** + * An index is an integer + */ +typedef uint32_t anydb_idx_t; + +#define AnyIdx_Invalid ((anydb_idx_t)0xffffffffu) +#define AnyIdx_Any ((anydb_idx_t)0xfffffffeu) +#define AnyIdx_Wide ((anydb_idx_t)0xfffffffdu) +#define AnyIdx_None ((anydb_idx_t)0xfffffffcu) +#define AnyIdx_Max ((anydb_idx_t)0xfffffff7u) + +/** + * A key is a set of index + */ +struct anydb_key { + /** client string id */ + anydb_idx_t client; + + /** session string id */ + anydb_idx_t session; + + /** user string id */ + anydb_idx_t user; + + /** permission string id */ + anydb_idx_t permission; +}; +typedef struct anydb_key anydb_key_t; + +/** + * A rule is a set of 32 bits integers + */ +struct anydb_value +{ + /** value string id */ + anydb_idx_t value; + + /** expiration */ + time_t expire; +}; +typedef struct anydb_value anydb_value_t; + +/** + */ +enum anydb_action +{ + Anydb_Action_Continue = 0, + Anydb_Action_Update_And_Stop = 1, + Anydb_Action_Remove_And_Continue = 2 +}; +typedef enum anydb_action anydb_action_t; + +struct anydb_itf +{ + int (*index)(void *clodb, anydb_idx_t *idx, const char *name, bool create); + const char *(*string)(void *clodb, anydb_idx_t idx); + void (*apply)(void *clodb, anydb_action_t (*oper)(void *closure, const anydb_key_t *key, anydb_value_t *value), void *closure); + int (*add)(void *clodb, const anydb_key_t *key, const anydb_value_t *value); + void (*gc)(void *clodb); + void (*destroy)(void *clodb); +}; +typedef struct anydb_itf anydb_itf_t; + +struct anydb +{ + void *clodb; + anydb_itf_t itf; +}; +typedef struct anydb anydb_t; + + +/** enumerate */ +extern +void +anydb_for_all( + anydb_t *db, + void *closure, + void (*callback)( + void *closure, + const data_key_t *key, + const data_value_t *value), + const data_key_t *key +); + +/** drop rules */ +extern +int +anydb_drop( + anydb_t *db, + const data_key_t *key +); + +/** set a rules */ +extern +int +anydb_set( + anydb_t *db, + const data_key_t *key, + const data_value_t *value +); + +/** test a rule, returns 0 or the score: count of exact keys */ +extern +int +anydb_test( + anydb_t *db, + const data_key_t *key, + data_value_t *value +); + +/** drop rules */ +extern +void +anydb_cleanup( + anydb_t *db +); + +/** destroy the database */ +extern +void +anydb_destroy( + anydb_t *db +); @@ -239,9 +239,7 @@ cyn_test( int rc; rc = db_test(key, value); - if (rc > 0) - rc = 0; - else { + if (rc <= 0) { value->value = DEFAULT; value->expire = 0; } @@ -22,6 +22,12 @@ #define ASK "ask" #define DEFAULT DENY +#define Data_Any_Char '#' +#define Data_Wide_Char '*' + +#define Data_Any_String "#" +#define Data_Wide_String "*" + typedef struct data_key data_key_t; typedef struct data_value data_value_t; @@ -27,392 +27,22 @@ #include <errno.h> #include "data.h" -#include "fbuf.h" -#include "db.h" -#include "rcyn-client.h" +#include "anydb.h" +#include "fdb.h" +#include "memdb.h" -#define NOEXPIRE 0 -#define NOIDX 0 +static anydb_t *memdb; -#define ANYIDX 40 -#define ANYSTR "#" - -#define WIDEIDX 42 -#define WIDESTR "*" - -/* - * for the first version, save enougth time up to 4149 - * 4149 = 1970 + (4294967296 * 16) / (365 * 24 * 60 * 60) - * - * in the next version, time will be relative to a stored base - */ -#define exp2time(x) (((time_t)(x)) << 4) -#define time2expl(x) ((uint32_t)((x) >> 4)) -#define time2exph(x) time2expl((x) + 15) - -/** - * A query is a set of 32 bits integers - */ -struct key_ids { - /** client string id */ - uint32_t client; - - /** user string id */ - uint32_t user; - - /** permission string id */ - uint32_t permission; -}; -typedef struct key_ids key_ids_t; - -/** - * A rule is a set of 32 bits integers - */ -struct rule -{ - /** key part */ - key_ids_t key; - - /** value string id */ - uint32_t value; - - /** expiration */ - uint32_t expire; -}; -typedef struct rule rule_t; - -/* - * The cynara-agl database is made of 2 memory mapped files: - * - names: the zero terminated names - * - rules: the rules based on name indexes as 32bits indexes - * These files are normally in /var/lib/cynara - */ -#if !defined(DEFAULT_DB_DIR) -# define DEFAULT_DB_DIR "/var/lib/cynara" -#endif -static const char db_default_directory[] = DEFAULT_DB_DIR; - -/** the file for the names */ -static fbuf_t fnames; - -/** the file for the rules */ -static fbuf_t frules; - -/** identification of names version 1 - * $> uuidgen --sha1 -n @url -N urn:AGL:cynara:db:names:1 - * $> uuid -v 5 urn:AGL:cynara:db:names:1 - */ -static const char uuid_names_v1[] = "e9481f9e-b2f4-5716-90cf-c286d98d1868\n--\n"; - -/** identification of rules version 1 - * $> uuidgen --sha1 -n @url -N urn:AGL:cynara:db:rules:1 - * $> uuid -v 5 ns:URL urn:AGL:cynara:db:rules:1 - */ -static const char uuid_rules_v1[] = "8f7a5b21-48b1-57af-96c9-d5d7192be370\n--\n"; - -/** length of the identification */ -static const int uuidlen = 40; - -/** count of names */ -static uint32_t names_count; - -/** the name indexes sorted */ -static uint32_t *names_sorted; - -/** count of rules */ -static uint32_t rules_count; - -/** the rules */ -static rule_t *rules; - -/** return the name of 'index' */ -static -const char* -name_at( - uint32_t index -) { - return (const char*)(fnames.buffer + index); -} - -/** compare names. used by qsort and bsearch */ -static -int -cmpnames( - const void *pa, - const void *pb -) { - uint32_t a = *(const uint32_t*)pa; - uint32_t b = *(const uint32_t*)pb; - return strcmp(name_at(a), name_at(b)); -} - -/** search the index of 'name' and create it if 'needed' */ -int -db_get_name_index( - uint32_t *index, - const char *name, - bool needed -) { - uint32_t lo, up, m, i, *p; - int c; - const char *n; - size_t len; - - /* special names */ - if (!name || !name[0]) - name = ANYSTR; - - /* dichotomic search */ - lo = 0; - up = names_count; - while(lo < up) { - m = (lo + up) >> 1; - i = names_sorted[m]; - n = name_at(i); - c = strcmp(n, name); - - if (c == 0) { - /* found */ - *index = i; - return 0; - } - - /* dichotomic iteration */ - if (c < 0) - lo = m + 1; - else - up = m; - } - - /* not found */ - if (!needed) { - errno = ENOENT; - return -1; - } - - /* check length */ - len = strnlen(name, MAX_NAME_LENGTH + 1); - if (len > MAX_NAME_LENGTH) { - errno = EINVAL; - return -1; - } - - /* add the name in the file */ - i = fnames.used; - c = fbuf_append(&fnames, name, 1 + (uint32_t)len); - if (c < 0) - return c; - - /* add the name in sorted array */ - up = names_count; - if (!(up & 1023)) { - p = realloc(names_sorted, (up + 1024) * sizeof *names_sorted); - if (p == NULL) { - fprintf(stderr, "out of memory"); - return -1; - } - names_sorted = p; - } - memmove(&names_sorted[lo + 1], &names_sorted[lo], (up - lo) * sizeof *names_sorted); - names_count = up + 1; - *index = names_sorted[lo] = i; - return 0; -} - -/** initialize names */ -static -int -init_names( -) { - int rc; - uint32_t pos, len, *ns, *p, all, nc; - - all = 0; - nc = 0; - ns = NULL; - - /* iterate over names */ - pos = uuidlen; - while (pos < fnames.used) { - /* get name length */ - len = (uint32_t)strlen(name_at(pos)); - if (pos + len <= pos || pos + len > fnames.used) { - free(ns); - goto bad_file; - } - /* store the position */ - if (all <= nc) { - all += 1024; - p = realloc(ns, all * sizeof *ns); - if (p == NULL) { - free(ns); - fprintf(stderr, "out of memory"); - goto error; - } - ns = p; - } - ns[nc++] = pos; - /* next */ - pos += len + 1; - } - - /* sort and record */ - qsort(ns, nc, sizeof *ns, cmpnames); - names_sorted = ns; - names_count = nc; - - /* predefined symbols */ - rc = db_get_name_index(&pos, ANYSTR, true); - if (rc < 0) - goto error; - if (pos != ANYIDX) - goto bad_file; - rc = db_get_name_index(&pos, WIDESTR, true); - if (rc < 0) - goto error; - if (pos != WIDEIDX) - goto bad_file; - - return 0; -bad_file: - fprintf(stderr, "bad file %s", fnames.name); - errno = ENOEXEC; -error: - return -1; -} - -/** check whether the 'text' fit ANYSTR, NULL or "" */ -static -bool -is_any( - const char *text -) { - return text == NULL || text[0] == 0 || 0 == strcmp(text, ANYSTR); -} - -/** check whether the 'text' fit ANYSTR, WIDESTR, NULL or "" */ +/** check whether the 'text' fit String_Any, String_Wide, NULL or "" */ static bool is_any_or_wide( const char *text ) { - return is_any(text) || 0 == strcmp(text, WIDESTR); -} - -/** set the 'value' to the rule at 'index' */ -static -void -touch_at( - uint32_t index -) { - uint32_t pos; - - pos = (uint32_t)(((void*)&rules[index]) - frules.buffer); - if (pos < frules.saved) - frules.saved = pos; + return text == NULL || text[0] == 0 + || (!text[1] && (text[0] == Data_Any_Char || text[0] == Data_Wide_Char)); } -/** set the 'value' to the rule at 'index' */ -static -void -set_at( - uint32_t index, - uint32_t value, - uint32_t expire -) { - assert(index < rules_count); - rules[index].value = value; - rules[index].expire = expire; - touch_at(index); -} - -/** drop the rule at 'index' */ -static -void -drop_at( - uint32_t index -) { - uint32_t pos; - - assert(index < rules_count); - if (index < --rules_count) - rules[index] = rules[rules_count]; - pos = (uint32_t)(((void*)&rules[rules_count]) - frules.buffer); - frules.used = pos; - touch_at(index); -} - -/** add the rule 'client' x 'user' x 'permission' x 'value' */ -static -int -add_rule( - uint32_t client, - uint32_t user, - uint32_t permission, - uint32_t value, - uint32_t expire -) { - int rc; - uint32_t c; - rule_t *rule; - - c = frules.used + (uint32_t)sizeof *rule; - rc = fbuf_ensure_capacity(&frules, c); - if (rc) - return rc; - rules = (rule_t*)(frules.buffer + uuidlen); - rule = &rules[rules_count++]; - rule->key.client = client; - rule->key.user = user; - rule->key.permission = permission; - rule->value = value; - rule->expire = expire; - frules.used = c; - return 0; -} - -/** init the rules from the file */ -static -void -init_rules( -) { - rules = (rule_t*)(frules.buffer + uuidlen); - rules_count = (frules.used - uuidlen) / sizeof *rules; -} - -/** open a fbuf */ -static -int -open_identify( - fbuf_t *fb, - const char *directory, - const char *name, - const char *id, - uint32_t idlen -) { - int rc; - char *file, *backup; - size_t sd, sn; - - sd = strlen(directory); - sn = strlen(name); - file = malloc(((sd + sn) << 1) + 5); - if (!file) - rc = -ENOMEM; - else { - - memcpy(file, directory, sd); - file[sd] = '/'; - memcpy(&file[sd + 1], name, sn + 1); - backup = &file[sd + sn + 2]; - memcpy(backup, file, sd + sn + 1); - backup[sd + sn + 1] = '~'; - backup[sd + sn + 2] = 0; - rc = fbuf_open_identify(fb, file, backup, id, idlen); - free(file); - } - return rc; -} /** open the database for files 'names' and 'rules' (can be NULL) */ int @@ -421,115 +51,49 @@ db_open( ) { int rc; - /* provide default directory */ - if (directory == NULL) - directory = db_default_directory; - - /* open the names */ - rc = open_identify(&fnames, directory, "cynara.names", uuid_names_v1, uuidlen); - if (rc < 0) - goto error; - - /* open the rules */ - rc = open_identify(&frules, directory, "cynara.rules", uuid_rules_v1, uuidlen); - if (rc < 0) - goto error; - - /* connect internals */ - rc = init_names(); - if (rc < 0) - goto error; - - init_rules(); - return 0; -error: - return -1; + rc = memdb_create(&memdb); + if (!rc) { + rc = fdb_open(directory); + if (rc) + anydb_destroy(memdb); + } + return rc; } /** close the database */ void db_close( ) { - assert(fnames.name && frules.name); - fbuf_close(&fnames); - fbuf_close(&frules); + fdb_close(); + anydb_destroy(memdb); } /** is the database empty */ bool db_is_empty( ) { - return !rules_count; + return fdb_is_empty(); } /** synchronize db on files */ int db_sync( ) { - int rc; - - assert(fnames.name && frules.name); - rc = fbuf_sync(&fnames); - if (rc == 0) - rc = fbuf_sync(&frules); - return rc; + return fdb_sync(); } /** make a backup of the database */ int db_backup( ) { - int rc; - - assert(fnames.name && frules.name); - rc = fbuf_backup(&fnames); - if (rc == 0) - rc = fbuf_backup(&frules); - return rc; + return fdb_backup(); } /** recover the database from latest backup */ int db_recover( ) { - int rc; - - assert(fnames.name && frules.name); - - rc = fbuf_recover(&fnames); - if (rc < 0) - goto error; - - rc = fbuf_recover(&frules); - if (rc < 0) - goto error; - - rc = init_names(); - if (rc < 0) - goto error; - - init_rules(); - return 0; -error: - fprintf(stderr, "db recovery impossible: %m"); - exit(5); - return rc; -} - -static int get_query_ids( - const data_key_t *in, - key_ids_t *out, - bool create -) { - int rc; - - rc = db_get_name_index(&out->client, in->client, create); - if (rc) goto end; - rc = db_get_name_index(&out->user, in->user, create); - if (rc) goto end; - rc = db_get_name_index(&out->permission, in->permission, create); -end: - return rc; + return fdb_recover(); } /** enumerate */ @@ -542,30 +106,8 @@ db_for_all( const data_value_t *value), const data_key_t *key ) { - uint32_t ucli, uusr, i; - int anyperm; - data_key_t k; - data_value_t v; - - if (!is_any_or_wide(key->session) - || db_get_name_index(&ucli, key->client, false) - || db_get_name_index(&uusr, key->user, false)) - return; /* nothing to do! */ - - anyperm = is_any(key->permission); - for (i = 0; i < rules_count; i++) { - if ((ucli == ANYIDX || ucli == rules[i].key.client) - && (uusr == ANYIDX || uusr == rules[i].key.user) - && (anyperm || !strcasecmp(key->permission, name_at(rules[i].key.permission)))) { - k.client = name_at(rules[i].key.client); - k.session = WIDESTR; - k.user = name_at(rules[i].key.user); - k.permission = name_at(rules[i].key.permission); - v.value = name_at(rules[i].value); - v.expire = exp2time(rules[i].expire); - callback(closure, &k, &v); - } - } + fdb_for_all(closure, callback, key); + anydb_for_all(memdb, closure, callback, key); } /** drop rules */ @@ -573,24 +115,8 @@ int db_drop( const data_key_t *key ) { - uint32_t ucli, uusr, i; - bool anyperm; - - if (!is_any_or_wide(key->session) - || db_get_name_index(&ucli, key->client, false) - || db_get_name_index(&uusr, key->user, false)) - return 0; /* nothing to do! */ - - anyperm = is_any(key->permission); - i = 0; - while (i < rules_count) { - if ((ucli == ANYIDX || ucli == rules[i].key.client) - && (uusr == ANYIDX || uusr == rules[i].key.user) - && (anyperm || !strcasecmp(key->permission, name_at(rules[i].key.permission)))) - drop_at(i); - else - i++; - } + fdb_drop(key); + anydb_drop(memdb, key); return 0; } @@ -600,52 +126,10 @@ db_set( const data_key_t *key, const data_value_t *value ) { - int rc; - uint32_t ucli, uusr, uperm, uval, i; - const char *perm; - - /* check the session */ - if (!is_any_or_wide(key->session)) { - errno = EINVAL; - rc = -1; - goto error; - } - - /* normalise the perm */ - perm = is_any_or_wide(key->permission) ? WIDESTR : key->permission; - - /* get/create strings */ - rc = db_get_name_index(&ucli, is_any_or_wide(key->client) ? WIDESTR : key->client, true); - if (rc) - goto error; - rc = db_get_name_index(&uusr, is_any_or_wide(key->user) ? WIDESTR : key->user, true); - if (rc) - goto error; - rc = db_get_name_index(&uval, value->value, true); - if (rc) - goto error; - - /* search the existing rule */ - for (i = 0; i < rules_count; i++) { - if (ucli == rules[i].key.client - && uusr == rules[i].key.user - && !strcasecmp(perm, name_at(rules[i].key.permission))) { - /* found */ - set_at(i, uval, time2exph(value->expire)); - return 0; - } - } - - /* create the rule */ - rc = db_get_name_index(&uperm, perm, true); - if (rc) - goto error; - - rc = add_rule(ucli, uusr, uperm, uval, time2exph(value->expire)); - - return 0; -error: - return rc; + if (is_any_or_wide(key->session)) + return fdb_set(key, value); + else + return anydb_set(memdb, key, value); } /** check rules */ @@ -654,230 +138,25 @@ db_test( const data_key_t *key, data_value_t *value ) { - const char *perm; - uint32_t ucli, uusr, i, score, sc, now; - rule_t *rule, *found; - - /* normalize the items */ - if (db_get_name_index(&ucli, is_any_or_wide(key->client) ? WIDESTR : key->client, false)) - ucli = NOIDX; - if (db_get_name_index(&uusr, is_any_or_wide(key->user) ? WIDESTR : key->user, false)) - uusr = NOIDX; - perm = is_any_or_wide(key->permission) ? WIDESTR : key->permission; - - /* search the existing rule */ - now = time2expl(time(NULL)); - found = NULL; - score = 0; - for (i = 0 ; i < rules_count ; i++) { - rule = &rules[i]; - if ((!rule->expire || rule->expire >= now) - && (ucli == rule->key.client || WIDEIDX == rule->key.client) - && (uusr == rule->key.user || WIDEIDX == rule->key.user) - && (WIDEIDX == rule->key.permission - || !strcasecmp(perm, name_at(rule->key.permission)))) { - /* found */ - sc = 1 + (rule->key.client != WIDEIDX) - + (rule->key.user != WIDEIDX) - + (rule->key.permission != WIDEIDX); - if (sc > score) { - score = sc; - found = rule; - } - } + int s1, s2; + data_value_t v1, v2; + + s1 = anydb_test(memdb, key, &v1); + s2 = fdb_test(key, &v2); + if (s2 > s1) { + *value = v2; + return s2; + } else { + *value = v1; + return s1; } - if (!found) { - value->value = NULL; - value->expire = 0; - return 0; - } - - value->value = name_at(found->value); - value->expire = exp2time(found->expire); - - return 1; -} - -typedef struct gc gc_t; -struct gc -{ - uint32_t *befores; - uint32_t *afters; -}; - -/** compare indexes. used by qsort and bsearch */ -static -int -cmpidxs( - const void *pa, - const void *pb -) { - uint32_t a = *(const uint32_t*)pa; - uint32_t b = *(const uint32_t*)pb; - return a < b ? -1 : a != b; -} - -static -uint32_t* -gc_after_ptr( - gc_t *gc, - uint32_t *idx -) { - uint32_t *p = bsearch(idx, gc->befores, names_count, sizeof *gc->befores, cmpidxs); - assert(p != NULL); - return &gc->afters[p - gc->befores]; -} - -static -void -gc_mark( - gc_t *gc, - uint32_t *idx -) { - *gc_after_ptr(gc, idx) = 1; -} - -static -void -gc_mark_id( - gc_t *gc, - uint32_t idx -) { - gc_mark(gc, &idx); -} - -static -int -gc_after( - gc_t *gc, - uint32_t *idx -) { - uint32_t idbef, idaft; - - idbef = *idx; - idaft = *gc_after_ptr(gc, idx); - *idx = idaft; - return (int)(idbef - idaft); -} - -static -int -gc_init( - gc_t *gc -) { - gc->befores = malloc((sizeof *gc->befores + sizeof *gc->afters) * names_count); - if (gc->befores == NULL) - return -ENOMEM; - - names_count = names_count; - memcpy(gc->befores, names_sorted, names_count * sizeof *gc->befores); - qsort(gc->befores, names_count, sizeof *gc->befores, cmpidxs); - gc->afters = &gc->befores[names_count]; - memset(gc->afters, 0, names_count * sizeof *gc->afters); - - gc_mark_id(gc, ANYIDX); - gc_mark_id(gc, WIDEIDX); - return 0; -} - -static -void -gc_end( - gc_t *gc -) { - free(gc->befores); -} - -static -int -gc_pack( - gc_t *gc -) { - uint32_t i, j, n, next, prev; - char *strings; - - /* skip the unchanged initial part */ - n = names_count; - i = 0; - while (i < n && gc->afters[i]) - i++; - - /* at end means no change */ - if (i == n) - return 0; - - /* pack the strings */ - strings = fnames.buffer; - j = i; - memcpy(gc->afters, gc->befores, j * sizeof *gc->afters); - next = gc->befores[i++]; - fnames.saved = next; - while (i < n) { - if (gc->afters[i]) { - gc->befores[j] = prev = gc->befores[i]; - gc->afters[j++] = next; - while ((strings[next++] = strings[prev++])); - } - i++; - } - fnames.used = next; - names_count = j; - memcpy(names_sorted, gc->afters, j * sizeof *gc->afters); - qsort(names_sorted, j, sizeof *names_sorted, cmpnames); - - return 1; } int db_cleanup( ) { - int rc, chg; - uint32_t i, now; - gc_t gc; - rule_t *rule; - - /* init garbage collector */ - rc= gc_init(&gc); - if (rc < 0) - return rc; - - /* default now */ - now = time2expl(time(NULL)); - - /* remove expired entries and mark string ids of remaining ones */ - i = 0; - while (i < rules_count) { - rule = &rules[i]; - if (rule->expire && now >= rule->expire) - drop_at(i); - else { - gc_mark(&gc, &rule->key.client); - gc_mark(&gc, &rule->key.user); - gc_mark(&gc, &rule->key.permission); - gc_mark(&gc, &rule->value); - i++; - } - } - - /* pack the strings */ - if (gc_pack(&gc)) { - /* replace the ids if changed */ - i = 0; - while (i < rules_count) { - rule = &rules[i]; - chg = gc_after(&gc, &rule->key.client); - chg |= gc_after(&gc, &rule->key.user); - chg |= gc_after(&gc, &rule->key.permission); - chg |= gc_after(&gc, &rule->value); - if (chg) - touch_at(i); - i++; - } - } - - /* terminate */ - gc_end(&gc); - + fdb_cleanup(); + anydb_cleanup(memdb); return 0; } @@ -44,15 +44,6 @@ int db_sync( ); -/** get an index for a name */ -extern -int -db_get_name_index( - uint32_t *index, - const char *name, - bool needed -); - /** make a backup of the database */ extern int diff --git a/src/fdb.c b/src/fdb.c new file mode 100644 index 0000000..d13325a --- /dev/null +++ b/src/fdb.c @@ -0,0 +1,865 @@ +/* + * Copyright (C) 2018 "IoT.bzh" + * Author José Bollo <jose.bollo@iot.bzh> + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <assert.h> +#include <stdlib.h> +#include <stdint.h> +#include <stdbool.h> +#include <stdalign.h> +#include <stdio.h> +#include <string.h> +#include <ctype.h> +#include <time.h> +#include <errno.h> + +#include "data.h" +#include "fbuf.h" +#include "fdb.h" + +#define NOEXPIRE 0 +#define NOIDX 0 + +#define ANYIDX 40 +#define ANYSTR "#" + +#define WIDEIDX 42 +#define WIDESTR "*" + +/* + * for the first version, save enougth time up to 4149 + * 4149 = 1970 + (4294967296 * 16) / (365 * 24 * 60 * 60) + * + * in the next version, time will be relative to a stored base + */ +#define exp2time(x) (((time_t)(x)) << 4) +#define time2expl(x) ((uint32_t)((x) >> 4)) +#define time2exph(x) time2expl((x) + 15) + +/** + * A query is a set of 32 bits integers + */ +struct key_ids { + /** client string id */ + uint32_t client; + + /** user string id */ + uint32_t user; + + /** permission string id */ + uint32_t permission; +}; +typedef struct key_ids key_ids_t; + +/** + * A rule is a set of 32 bits integers + */ +struct rule +{ + /** key part */ + key_ids_t key; + + /** value string id */ + uint32_t value; + + /** expiration */ + uint32_t expire; +}; +typedef struct rule rule_t; + +/* + * The cynara-agl database is made of 2 memory mapped files: + * - names: the zero terminated names + * - rules: the rules based on name indexes as 32bits indexes + * These files are normally in /var/lib/cynara + */ +#if !defined(DEFAULT_DB_DIR) +# define DEFAULT_DB_DIR "/var/lib/cynara" +#endif +static const char fdb_default_directory[] = DEFAULT_DB_DIR; + +/** the file for the names */ +static fbuf_t fnames; + +/** the file for the rules */ +static fbuf_t frules; + +/** identification of names version 1 + * $> uuidgen --sha1 -n @url -N urn:AGL:cynara:db:names:1 + * $> uuid -v 5 urn:AGL:cynara:db:names:1 + */ +static const char uuid_names_v1[] = "e9481f9e-b2f4-5716-90cf-c286d98d1868\n--\n"; + +/** identification of rules version 1 + * $> uuidgen --sha1 -n @url -N urn:AGL:cynara:db:rules:1 + * $> uuid -v 5 ns:URL urn:AGL:cynara:db:rules:1 + */ +static const char uuid_rules_v1[] = "8f7a5b21-48b1-57af-96c9-d5d7192be370\n--\n"; + +/** length of the identification */ +static const int uuidlen = 40; + +/** count of names */ +static uint32_t names_count; + +/** the name indexes sorted */ +static uint32_t *names_sorted; + +/** count of rules */ +static uint32_t rules_count; + +/** the rules */ +static rule_t *rules; + +/** return the name of 'index' */ +static +const char* +name_at( + uint32_t index +) { + return (const char*)(fnames.buffer + index); +} + +/** compare names. used by qsort and bsearch */ +static +int +cmpnames( + const void *pa, + const void *pb +) { + uint32_t a = *(const uint32_t*)pa; + uint32_t b = *(const uint32_t*)pb; + return strcmp(name_at(a), name_at(b)); +} + +/** search the index of 'name' and create it if 'create' */ +int +fdb_get_name_index( + uint32_t *index, + const char *name, + bool create +) { + uint32_t lo, up, m, i, *p; + int c; + const char *n; + size_t len; + + /* special names */ + if (!name || !name[0]) + name = ANYSTR; + + /* dichotomic search */ + lo = 0; + up = names_count; + while(lo < up) { + m = (lo + up) >> 1; + i = names_sorted[m]; + n = name_at(i); + c = strcmp(n, name); + + if (c == 0) { + /* found */ + *index = i; + return 0; + } + + /* dichotomic iteration */ + if (c < 0) + lo = m + 1; + else + up = m; + } + + /* not found */ + if (!create) { + errno = ENOENT; + return -1; + } + + /* check length */ + len = strnlen(name, MAX_NAME_LENGTH + 1); + if (len > MAX_NAME_LENGTH) { + errno = EINVAL; + return -1; + } + + /* add the name in the file */ + i = fnames.used; + c = fbuf_append(&fnames, name, 1 + (uint32_t)len); + if (c < 0) + return c; + + /* add the name in sorted array */ + up = names_count; + if (!(up & 1023)) { + p = realloc(names_sorted, (up + 1024) * sizeof *names_sorted); + if (p == NULL) { + fprintf(stderr, "out of memory"); + return -1; + } + names_sorted = p; + } + memmove(&names_sorted[lo + 1], &names_sorted[lo], (up - lo) * sizeof *names_sorted); + names_count = up + 1; + *index = names_sorted[lo] = i; + return 0; +} + +/** initialize names */ +static +int +init_names( +) { + int rc; + uint32_t pos, len, *ns, *p, all, nc; + + all = 0; + nc = 0; + ns = NULL; + + /* iterate over names */ + pos = uuidlen; + while (pos < fnames.used) { + /* get name length */ + len = (uint32_t)strlen(name_at(pos)); + if (pos + len <= pos || pos + len > fnames.used) { + free(ns); + goto bad_file; + } + /* store the position */ + if (all <= nc) { + all += 1024; + p = realloc(ns, all * sizeof *ns); + if (p == NULL) { + free(ns); + fprintf(stderr, "out of memory"); + goto error; + } + ns = p; + } + ns[nc++] = pos; + /* next */ + pos += len + 1; + } + + /* sort and record */ + qsort(ns, nc, sizeof *ns, cmpnames); + names_sorted = ns; + names_count = nc; + + /* predefined symbols */ + rc = fdb_get_name_index(&pos, ANYSTR, true); + if (rc < 0) + goto error; + if (pos != ANYIDX) + goto bad_file; + rc = fdb_get_name_index(&pos, WIDESTR, true); + if (rc < 0) + goto error; + if (pos != WIDEIDX) + goto bad_file; + + return 0; +bad_file: + fprintf(stderr, "bad file %s", fnames.name); + errno = ENOEXEC; +error: + return -1; +} + +/** check whether the 'text' fit ANYSTR, NULL or "" */ +static +bool +is_any( + const char *text +) { + return text == NULL || text[0] == 0 || 0 == strcmp(text, ANYSTR); +} + +/** check whether the 'text' fit ANYSTR, WIDESTR, NULL or "" */ +static +bool +is_any_or_wide( + const char *text +) { + return is_any(text) || 0 == strcmp(text, WIDESTR); +} + +/** set the 'value' to the rule at 'index' */ +static +void +touch_at( + uint32_t index +) { + uint32_t pos; + + pos = (uint32_t)(((void*)&rules[index]) - frules.buffer); + if (pos < frules.saved) + frules.saved = pos; +} + +/** set the 'value' to the rule at 'index' */ +static +void +set_at( + uint32_t index, + uint32_t value, + uint32_t expire +) { + assert(index < rules_count); + rules[index].value = value; + rules[index].expire = expire; + touch_at(index); +} + +/** drop the rule at 'index' */ +static +void +drop_at( + uint32_t index +) { + uint32_t pos; + + assert(index < rules_count); + if (index < --rules_count) + rules[index] = rules[rules_count]; + pos = (uint32_t)(((void*)&rules[rules_count]) - frules.buffer); + frules.used = pos; + touch_at(index); +} + +/** add the rule 'client' x 'user' x 'permission' x 'value' */ +static +int +add_rule( + uint32_t client, + uint32_t user, + uint32_t permission, + uint32_t value, + uint32_t expire +) { + int rc; + uint32_t c; + rule_t *rule; + + c = frules.used + (uint32_t)sizeof *rule; + rc = fbuf_ensure_capacity(&frules, c); + if (rc) + return rc; + rules = (rule_t*)(frules.buffer + uuidlen); + rule = &rules[rules_count++]; + rule->key.client = client; + rule->key.user = user; + rule->key.permission = permission; + rule->value = value; + rule->expire = expire; + frules.used = c; + return 0; +} + +/** init the rules from the file */ +static +void +init_rules( +) { + rules = (rule_t*)(frules.buffer + uuidlen); + rules_count = (frules.used - uuidlen) / sizeof *rules; +} + +/** open a fbuf */ +static +int +open_identify( + fbuf_t *fb, + const char *directory, + const char *name, + const char *id, + uint32_t idlen +) { + int rc; + char *file, *backup; + size_t sd, sn; + + sd = strlen(directory); + sn = strlen(name); + file = malloc(((sd + sn) << 1) + 5); + if (!file) + rc = -ENOMEM; + else { + + memcpy(file, directory, sd); + file[sd] = '/'; + memcpy(&file[sd + 1], name, sn + 1); + backup = &file[sd + sn + 2]; + memcpy(backup, file, sd + sn + 1); + backup[sd + sn + 1] = '~'; + backup[sd + sn + 2] = 0; + rc = fbuf_open_identify(fb, file, backup, id, idlen); + free(file); + } + return rc; +} + +/** open the database for files 'names' and 'rules' (can be NULL) */ +int +fdb_open( + const char *directory +) { + int rc; + + /* provide default directory */ + if (directory == NULL) + directory = fdb_default_directory; + + /* open the names */ + rc = open_identify(&fnames, directory, "cynara.names", uuid_names_v1, uuidlen); + if (rc < 0) + goto error; + + /* open the rules */ + rc = open_identify(&frules, directory, "cynara.rules", uuid_rules_v1, uuidlen); + if (rc < 0) + goto error; + + /* connect internals */ + rc = init_names(); + if (rc < 0) + goto error; + + init_rules(); + return 0; +error: + return -1; +} + +/** close the database */ +void +fdb_close( +) { + assert(fnames.name && frules.name); + fbuf_close(&fnames); + fbuf_close(&frules); +} + +/** is the database empty */ +bool +fdb_is_empty( +) { + return !rules_count; +} + +/** synchronize db on files */ +int +fdb_sync( +) { + int rc; + + assert(fnames.name && frules.name); + rc = fbuf_sync(&fnames); + if (rc == 0) + rc = fbuf_sync(&frules); + return rc; +} + +/** make a backup of the database */ +int +fdb_backup( +) { + int rc; + + assert(fnames.name && frules.name); + rc = fbuf_backup(&fnames); + if (rc == 0) + rc = fbuf_backup(&frules); + return rc; +} + +/** recover the database from latest backup */ +int +fdb_recover( +) { + int rc; + + assert(fnames.name && frules.name); + + rc = fbuf_recover(&fnames); + if (rc < 0) + goto error; + + rc = fbuf_recover(&frules); + if (rc < 0) + goto error; + + rc = init_names(); + if (rc < 0) + goto error; + + init_rules(); + return 0; +error: + fprintf(stderr, "db recovery impossible: %m"); + exit(5); + return rc; +} + +/** enumerate */ +void +fdb_for_all( + void *closure, + void (*callback)( + void *closure, + const data_key_t *key, + const data_value_t *value), + const data_key_t *key +) { + uint32_t ucli, uusr, i; + int anyperm; + data_key_t k; + data_value_t v; + + if (!is_any_or_wide(key->session) + || fdb_get_name_index(&ucli, key->client, false) + || fdb_get_name_index(&uusr, key->user, false)) + return; /* nothing to do! */ + + anyperm = is_any(key->permission); + for (i = 0; i < rules_count; i++) { + if ((ucli == ANYIDX || ucli == rules[i].key.client) + && (uusr == ANYIDX || uusr == rules[i].key.user) + && (anyperm || !strcasecmp(key->permission, name_at(rules[i].key.permission)))) { + k.client = name_at(rules[i].key.client); + k.session = WIDESTR; + k.user = name_at(rules[i].key.user); + k.permission = name_at(rules[i].key.permission); + v.value = name_at(rules[i].value); + v.expire = exp2time(rules[i].expire); + callback(closure, &k, &v); + } + } +} + +/** drop rules */ +int +fdb_drop( + const data_key_t *key +) { + uint32_t ucli, uusr, i; + bool anyperm; + + if (!is_any_or_wide(key->session) + || fdb_get_name_index(&ucli, key->client, false) + || fdb_get_name_index(&uusr, key->user, false)) + return 0; /* nothing to do! */ + + anyperm = is_any(key->permission); + i = 0; + while (i < rules_count) { + if ((ucli == ANYIDX || ucli == rules[i].key.client) + && (uusr == ANYIDX || uusr == rules[i].key.user) + && (anyperm || !strcasecmp(key->permission, name_at(rules[i].key.permission)))) + drop_at(i); + else + i++; + } + return 0; +} + +/** set rules */ +int +fdb_set( + const data_key_t *key, + const data_value_t *value +) { + int rc; + uint32_t ucli, uusr, uperm, uval, i; + const char *perm; + + /* check the session */ + if (!is_any_or_wide(key->session)) { + errno = EINVAL; + rc = -1; + goto error; + } + + /* normalise the perm */ + perm = is_any_or_wide(key->permission) ? WIDESTR : key->permission; + + /* get/create strings */ + rc = fdb_get_name_index(&ucli, is_any_or_wide(key->client) ? WIDESTR : key->client, true); + if (rc) + goto error; + rc = fdb_get_name_index(&uusr, is_any_or_wide(key->user) ? WIDESTR : key->user, true); + if (rc) + goto error; + rc = fdb_get_name_index(&uval, value->value, true); + if (rc) + goto error; + + /* search the existing rule */ + for (i = 0; i < rules_count; i++) { + if (ucli == rules[i].key.client + && uusr == rules[i].key.user + && !strcasecmp(perm, name_at(rules[i].key.permission))) { + /* found */ + set_at(i, uval, time2exph(value->expire)); + return 0; + } + } + + /* create the rule */ + rc = fdb_get_name_index(&uperm, perm, true); + if (rc) + goto error; + + rc = add_rule(ucli, uusr, uperm, uval, time2exph(value->expire)); + + return 0; +error: + return rc; +} + +/** check rules */ +int +fdb_test( + const data_key_t *key, + data_value_t *value +) { + const char *perm; + uint32_t ucli, uusr, i, score, sc, now; + rule_t *rule, *found; + + /* normalize the items */ + if (fdb_get_name_index(&ucli, is_any_or_wide(key->client) ? WIDESTR : key->client, false)) + ucli = NOIDX; + if (fdb_get_name_index(&uusr, is_any_or_wide(key->user) ? WIDESTR : key->user, false)) + uusr = NOIDX; + perm = is_any_or_wide(key->permission) ? WIDESTR : key->permission; + + /* search the existing rule */ + now = time2expl(time(NULL)); + found = NULL; + score = 0; + for (i = 0 ; i < rules_count ; i++) { + rule = &rules[i]; + if ((!rule->expire || rule->expire >= now) + && (ucli == rule->key.client || WIDEIDX == rule->key.client) + && (uusr == rule->key.user || WIDEIDX == rule->key.user) + && (WIDEIDX == rule->key.permission + || !strcasecmp(perm, name_at(rule->key.permission)))) { + /* found */ + sc = 1 + (rule->key.client != WIDEIDX) + + (rule->key.user != WIDEIDX) + + (rule->key.permission != WIDEIDX); + if (sc > score) { + score = sc; + found = rule; + } + } + } + if (!found) { + value->value = NULL; + value->expire = 0; + return 0; + } + + value->value = name_at(found->value); + value->expire = exp2time(found->expire); + + return 1; +} + +typedef struct gc gc_t; +struct gc +{ + uint32_t *befores; + uint32_t *afters; +}; + +/** compare indexes. used by qsort and bsearch */ +static +int +cmpidxs( + const void *pa, + const void *pb +) { + uint32_t a = *(const uint32_t*)pa; + uint32_t b = *(const uint32_t*)pb; + return a < b ? -1 : a != b; +} + +static +uint32_t* +gc_after_ptr( + gc_t *gc, + uint32_t *idx +) { + uint32_t *p = bsearch(idx, gc->befores, names_count, sizeof *gc->befores, cmpidxs); + assert(p != NULL); + return &gc->afters[p - gc->befores]; +} + +static +void +gc_mark( + gc_t *gc, + uint32_t *idx +) { + *gc_after_ptr(gc, idx) = 1; +} + +static +void +gc_mark_id( + gc_t *gc, + uint32_t idx +) { + gc_mark(gc, &idx); +} + +static +int +gc_after( + gc_t *gc, + uint32_t *idx +) { + uint32_t idbef, idaft; + + idbef = *idx; + idaft = *gc_after_ptr(gc, idx); + *idx = idaft; + return (int)(idbef - idaft); +} + +static +int +gc_init( + gc_t *gc +) { + gc->befores = malloc((sizeof *gc->befores + sizeof *gc->afters) * names_count); + if (gc->befores == NULL) + return -ENOMEM; + + names_count = names_count; + memcpy(gc->befores, names_sorted, names_count * sizeof *gc->befores); + qsort(gc->befores, names_count, sizeof *gc->befores, cmpidxs); + gc->afters = &gc->befores[names_count]; + memset(gc->afters, 0, names_count * sizeof *gc->afters); + + gc_mark_id(gc, ANYIDX); + gc_mark_id(gc, WIDEIDX); + return 0; +} + +static +void +gc_end( + gc_t *gc +) { + free(gc->befores); +} + +static +int +gc_pack( + gc_t *gc +) { + uint32_t i, j, n, next, prev; + char *strings; + + /* skip the unchanged initial part */ + n = names_count; + i = 0; + while (i < n && gc->afters[i]) + i++; + + /* at end means no change */ + if (i == n) + return 0; + + /* pack the strings */ + strings = fnames.buffer; + j = i; + memcpy(gc->afters, gc->befores, j * sizeof *gc->afters); + next = gc->befores[i++]; + fnames.saved = next; + while (i < n) { + if (gc->afters[i]) { + gc->befores[j] = prev = gc->befores[i]; + gc->afters[j++] = next; + while ((strings[next++] = strings[prev++])); + } + i++; + } + fnames.used = next; + names_count = j; + memcpy(names_sorted, gc->afters, j * sizeof *gc->afters); + qsort(names_sorted, j, sizeof *names_sorted, cmpnames); + + return 1; +} + +int +fdb_cleanup( +) { + int rc, chg; + uint32_t i, now; + gc_t gc; + rule_t *rule; + + /* init garbage collector */ + rc= gc_init(&gc); + if (rc < 0) + return rc; + + /* default now */ + now = time2expl(time(NULL)); + + /* remove expired entries and mark string ids of remaining ones */ + i = 0; + while (i < rules_count) { + rule = &rules[i]; + if (rule->expire && now >= rule->expire) + drop_at(i); + else { + gc_mark(&gc, &rule->key.client); + gc_mark(&gc, &rule->key.user); + gc_mark(&gc, &rule->key.permission); + gc_mark(&gc, &rule->value); + i++; + } + } + + /* pack the strings */ + if (gc_pack(&gc)) { + /* replace the ids if changed */ + i = 0; + while (i < rules_count) { + rule = &rules[i]; + chg = gc_after(&gc, &rule->key.client); + chg |= gc_after(&gc, &rule->key.user); + chg |= gc_after(&gc, &rule->key.permission); + chg |= gc_after(&gc, &rule->value); + if (chg) + touch_at(i); + i++; + } + } + + /* terminate */ + gc_end(&gc); + + return 0; +} diff --git a/src/fdb.h b/src/fdb.h new file mode 100644 index 0000000..c3ae58b --- /dev/null +++ b/src/fdb.h @@ -0,0 +1,99 @@ +/* + * Copyright (C) 2018 "IoT.bzh" + * Author José Bollo <jose.bollo@iot.bzh> + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#pragma once + +#define MAX_NAME_LENGTH 32767 + +/** open the database for files 'names' and 'rules' (can be NULL) */ +extern +int +fdb_open( + const char *directory +); + +/** close the database */ +extern +void +fdb_close( +); + +/** is the database empty */ +extern +bool +fdb_is_empty( +); + +/** sync the database */ +extern +int +fdb_sync( +); + +/** make a backup of the database */ +extern +int +fdb_backup( +); + +/** recover the database from latest backup */ +extern +int +fdb_recover( +); + +/** enumerate */ +extern +void +fdb_for_all( + void *closure, + void (*callback)( + void *closure, + const data_key_t *key, + const data_value_t *value), + const data_key_t *key +); + +/** erase rules */ +extern +int +fdb_drop( + const data_key_t *key +); + +/** set rules */ +extern +int +fdb_set( + const data_key_t *key, + const data_value_t *value +); + +/** check rules */ +extern +int +fdb_test( + const data_key_t *key, + data_value_t *value +); + +/** cleanup the base */ +extern +int +fdb_cleanup( +); + diff --git a/src/memdb.c b/src/memdb.c new file mode 100644 index 0000000..0a1e044 --- /dev/null +++ b/src/memdb.c @@ -0,0 +1,279 @@ +/* + * Copyright (C) 2018 "IoT.bzh" + * Author José Bollo <jose.bollo@iot.bzh> + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <stdlib.h> +#include <stdint.h> +#include <stdbool.h> +#include <time.h> +#include <string.h> +#include <errno.h> + +#include "data.h" +#include "anydb.h" + +#define RBS 20 +#define SBS 30 + +struct rule +{ + anydb_key_t key; + anydb_value_t value; +}; + +struct memdb +{ + /* first for the fun */ + anydb_t db; + + /* strings */ + struct { + uint32_t alloc; + uint32_t count; + char **values; + } strings; + + /* rules */ + struct { + uint32_t alloc; + uint32_t count; + struct rule *values; + } rules; +}; +typedef struct memdb memdb_t; + +static +int +index_itf( + void *clodb, + anydb_idx_t *idx, + const char *name, + bool create +) { + memdb_t *memdb = clodb; + char *s, **strings = memdb->strings.values; + anydb_idx_t i; + + /* search */ + i = 0; + while (i < memdb->strings.count) { + if (!strcmp(name, strings[i])) { + *idx = i; + return 0; + } + i++; + } + + /* not found */ + if (!create) { + errno = ENOENT; + return -1; + } + + /* create */ + s = strdup(name); + if (s == NULL) + return -ENOMEM; + if (memdb->strings.count == memdb->strings.alloc) { + strings = realloc(strings, (memdb->strings.alloc + SBS) * sizeof *strings); + if (!strings) { + free(s); + return -ENOMEM; + } + memdb->strings.values = strings; + memdb->strings.alloc += SBS; + } + i = memdb->strings.count; + *idx = i; + strings[i] = s; + memdb->strings.count = i + 1; + return 0; +} + +static +const char * +string_itf( + void *clodb, + anydb_idx_t idx +) { + memdb_t *memdb = clodb; + + return memdb->strings.values[idx]; +} + +static +void +apply_itf( + void *clodb, + anydb_action_t (*oper)(void *closure, const anydb_key_t *key, anydb_value_t *value), + void *closure +) { + memdb_t *memdb = clodb; + struct rule *rules = memdb->rules.values; + uint32_t ir; + anydb_action_t a; + + ir = 0; + while (ir < memdb->rules.count) { + a = oper(closure, &rules[ir].key, &rules[ir].value); + switch (a) { + case Anydb_Action_Continue: + ir++; + break; + case Anydb_Action_Update_And_Stop: + return; + case Anydb_Action_Remove_And_Continue: + rules[ir] = rules[--memdb->rules.count]; + break; + } + } +} + +static +int +add_itf( + void *clodb, + const anydb_key_t *key, + const anydb_value_t *value +) { + memdb_t *memdb = clodb; + struct rule *rules = memdb->rules.values; + + if (memdb->rules.count == memdb->rules.alloc) { + rules = realloc(rules, (memdb->rules.alloc + RBS) * sizeof *rules); + if (!rules) + return -ENOMEM; + memdb->rules.alloc += RBS; + memdb->rules.values = rules; + } + rules[memdb->rules.count].key = *key; + rules[memdb->rules.count].value = *value; + memdb->rules.count++; + return 0; +} + +static +void +gc_itf( + void *clodb +) { + memdb_t *memdb = clodb; + uint32_t nr = memdb->rules.count; + uint32_t ns = memdb->strings.count; + char **strings = memdb->strings.values; + struct rule *rules = memdb->rules.values; + anydb_idx_t *renum = alloca(ns * sizeof *renum); + uint32_t i, j; + + for (i = 0 ; i < ns ; i++) + renum[i] = 0; + + for (i = 0 ; i < nr ; i++) { + renum[rules[i].key.client] = 1; + renum[rules[i].key.session] = 1; + renum[rules[i].key.user] = 1; + renum[rules[i].key.permission] = 1; + renum[rules[i].value.value] = 1; + } + + for (i = j = 0 ; i < ns ; i++) { + if (renum[i]) { + strings[j] = strings[i]; + renum[i] = j++; + } else { + free(strings[i]); + renum[i] = AnyIdx_Invalid; + } + } + if (ns != j) { + memdb->strings.count = ns = j; + for (i = 0 ; i < nr ; i++) { + rules[i].key.client = renum[rules[i].key.client]; + rules[i].key.session = renum[rules[i].key.session]; + rules[i].key.user = renum[rules[i].key.user]; + rules[i].key.permission = renum[rules[i].key.permission]; + rules[i].value.value = renum[rules[i].value.value]; + } + } + + i = memdb->strings.alloc; + while (ns + SBS > i) + i -= SBS; + if (i != memdb->strings.alloc) { + memdb->strings.alloc = i; + memdb->strings.values = realloc(strings, i * sizeof *strings); + } + + i = memdb->rules.alloc; + while (ns + RBS > i) + i -= RBS; + if (i != memdb->rules.alloc) { + memdb->rules.alloc = i; + memdb->rules.values = realloc(rules, i * sizeof *strings); + } +} + +static +void +destroy_itf( + void *clodb +) { + memdb_t *memdb = clodb; + if (memdb) { + free(memdb->strings.values); + free(memdb->rules.values); + free(memdb); + } +} + +static +void +init( + memdb_t *memdb +) { + memdb->db.clodb = memdb; + + memdb->db.itf.index = index_itf; + memdb->db.itf.string = string_itf; + memdb->db.itf.apply = apply_itf; + memdb->db.itf.add = add_itf; + memdb->db.itf.gc = gc_itf; + memdb->db.itf.destroy = destroy_itf; + + memdb->strings.alloc = 0; + memdb->strings.count = 0; + memdb->strings.values = NULL; + + memdb->rules.alloc = 0; + memdb->rules.count = 0; + memdb->rules.values = NULL; +} + +int +memdb_create( + anydb_t **memdb +) { + memdb_t *mdb; + + mdb = malloc(sizeof *mdb); + if (!mdb) { + *memdb = NULL; + return -ENOMEM; + } + init(mdb); + *memdb = &mdb->db; + return 0; +} diff --git a/src/memdb.h b/src/memdb.h new file mode 100644 index 0000000..0f1c9e7 --- /dev/null +++ b/src/memdb.h @@ -0,0 +1,24 @@ +/* + * Copyright (C) 2018 "IoT.bzh" + * Author José Bollo <jose.bollo@iot.bzh> + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#pragma once + +extern +int +memdb_create( + anydb_t **memdb +); |