libsss_idmap: function to calculate range

Calculation of range for domains is moved from
sdap_idmap code to sss_idmap code. Some refactoring
have been done to allow this move.

https://fedorahosted.org/sssd/ticket/1844

6 files changed, 344 insertions, 118 deletions

diff --git a/Makefile.am b/Makefile.am
index c6dfcb2c..aadb2ff6 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -583,9 +583,10 @@ libipa_hbac_la_LDFLAGS = \
 dist_pkgconfig_DATA += src/lib/idmap/sss_idmap.pc
 libsss_idmap_la_SOURCES = \
     src/lib/idmap/sss_idmap.c \
-    src/lib/idmap/sss_idmap_conv.c
+    src/lib/idmap/sss_idmap_conv.c \
+    src/util/murmurhash3.c
 libsss_idmap_la_LDFLAGS = \
-    -version-info 0:1:0
+    -version-info 1:0:1
 
 
 include_HEADERS = \
diff --git a/src/lib/idmap/sss_idmap.c b/src/lib/idmap/sss_idmap.c
index 1764b6f4..24506c68 100644
--- a/src/lib/idmap/sss_idmap.c
+++ b/src/lib/idmap/sss_idmap.c
@@ -28,6 +28,7 @@
 
 #include "lib/idmap/sss_idmap.h"
 #include "lib/idmap/sss_idmap_private.h"
+#include "util/murmurhash3.h"
 
 #define SID_FMT "%s-%d"
 #define SID_STR_MAX_LEN 1024
@@ -198,6 +199,12 @@ enum idmap_error_code sss_idmap_init(idmap_alloc_func *alloc_func,
     ctx->alloc_pvt = alloc_pvt;
     ctx->free_func = (free_func == NULL) ? default_free : free_func;
 
+    /* Set default values. */
+    ctx->idmap_opts.autorid_mode = SSS_IDMAP_DEFAULT_AUTORID;
+    ctx->idmap_opts.idmap_lower = SSS_IDMAP_DEFAULT_LOWER;
+    ctx->idmap_opts.idmap_upper = SSS_IDMAP_DEFAULT_UPPER;
+    ctx->idmap_opts.rangesize = SSS_IDMAP_DEFAULT_RANGESIZE;
+
     *_ctx = ctx;
 
     return IDMAP_SUCCESS;
@@ -225,6 +232,104 @@ enum idmap_error_code sss_idmap_free(struct sss_idmap_ctx *ctx)
     return IDMAP_SUCCESS;
 }
 
+enum idmap_error_code sss_idmap_calculate_range(struct sss_idmap_ctx *ctx,
+                                                const char *dom_sid,
+                                                id_t *slice_num,
+                                                struct sss_idmap_range *_range)
+{
+    id_t max_slices;
+    id_t orig_slice;
+    id_t new_slice;
+    id_t min;
+    id_t max;
+    id_t idmap_lower;
+    id_t idmap_upper;
+    id_t rangesize;
+    bool autorid_mode;
+    uint32_t hash_val;
+    struct idmap_domain_info *dom;
+
+    CHECK_IDMAP_CTX(ctx, IDMAP_CONTEXT_INVALID);
+
+    idmap_lower = ctx->idmap_opts.idmap_lower;
+    idmap_upper = ctx->idmap_opts.idmap_upper;
+    rangesize = ctx->idmap_opts.rangesize;
+    autorid_mode = ctx->idmap_opts.autorid_mode;
+
+    max_slices = (idmap_upper - idmap_lower) / rangesize;
+
+    if (slice_num && *slice_num != -1) {
+        /* The slice is being set explicitly.
+         * This may happen at system startup when we're loading
+         * previously-determined slices. In the future, we may also
+         * permit configuration to select the slice for a domain
+         * explicitly.
+         */
+        new_slice = *slice_num;
+    } else {
+        /* If slice is -1, we're being asked to pick a new slice */
+
+        if (autorid_mode) {
+            /* In autorid compatibility mode, always start at 0 and find the
+             * first free value.
+             */
+            orig_slice = 0;
+        } else {
+            /* Hash the domain sid string */
+            hash_val = murmurhash3(dom_sid, strlen(dom_sid), 0xdeadbeef);
+
+            /* Now get take the modulus of the hash val and the max_slices
+             * to determine its optimal position in the range.
+             */
+            new_slice = hash_val % max_slices;
+            orig_slice = new_slice;
+        }
+
+        min = (rangesize * new_slice) + idmap_lower;
+        max = min + rangesize;
+        /* Verify that this slice is not already in use */
+        do {
+            for (dom = ctx->idmap_domain_info; dom != NULL; dom = dom->next) {
+                if ((dom->range->min <= min && dom->range->max >= max) ||
+                    (dom->range->min >= min && dom->range->min <= max) ||
+                    (dom->range->max >= min && dom->range->max <= max)) {
+                    /* This range overlaps one already registered
+                     * We'll try the next available slot
+                     */
+                    new_slice++;
+                    if (new_slice >= max_slices) {
+                        /* loop around to the beginning if necessary */
+                        new_slice = 0;
+                    }
+
+                    min = (rangesize * new_slice) + idmap_lower;
+                    max = min + rangesize;
+                    break;
+                }
+            }
+
+            /* Keep trying until dom is NULL (meaning we got to the end
+             * without matching) or we have run out of slices and gotten
+             * back to the first one we tried.
+             */
+        } while (dom && new_slice != orig_slice);
+
+        if (dom) {
+            /* We looped all the way through and found no empty slots */
+            return IDMAP_OUT_OF_SLICES;
+        }
+    }
+
+    _range->min = (rangesize * new_slice) + idmap_lower;
+    _range->max = _range->min + rangesize;
+
+    if (slice_num) {
+        *slice_num = new_slice;
+    }
+
+    return IDMAP_SUCCESS;
+}
+
 enum idmap_error_code sss_idmap_add_domain(struct sss_idmap_ctx *ctx,
                                            const char *domain_name,
                                            const char *domain_sid,
@@ -511,3 +616,67 @@ done:
     return err;
 
 }
+
+enum idmap_error_code
+sss_idmap_ctx_set_autorid(struct sss_idmap_ctx *ctx, bool use_autorid)
+{
+    CHECK_IDMAP_CTX(ctx, IDMAP_CONTEXT_INVALID);
+    ctx->idmap_opts.autorid_mode = use_autorid;
+    return IDMAP_SUCCESS;
+}
+
+enum idmap_error_code
+sss_idmap_ctx_set_lower(struct sss_idmap_ctx *ctx, id_t lower)
+{
+    CHECK_IDMAP_CTX(ctx, IDMAP_CONTEXT_INVALID);
+    ctx->idmap_opts.idmap_lower = lower;
+    return IDMAP_SUCCESS;
+}
+
+enum idmap_error_code
+sss_idmap_ctx_set_upper(struct sss_idmap_ctx *ctx, id_t upper)
+{
+    CHECK_IDMAP_CTX(ctx, IDMAP_CONTEXT_INVALID);
+    ctx->idmap_opts.idmap_upper = upper;
+    return IDMAP_SUCCESS;
+}
+
+enum idmap_error_code
+sss_idmap_ctx_set_rangesize(struct sss_idmap_ctx *ctx, id_t rangesize)
+{
+    CHECK_IDMAP_CTX(ctx, IDMAP_CONTEXT_INVALID);
+    ctx->idmap_opts.rangesize = rangesize;
+    return IDMAP_SUCCESS;
+}
+
+enum idmap_error_code
+sss_idmap_ctx_get_autorid(struct sss_idmap_ctx *ctx, bool *_autorid)
+{
+    CHECK_IDMAP_CTX(ctx, IDMAP_CONTEXT_INVALID);
+     *_autorid = ctx->idmap_opts.autorid_mode;
+     return IDMAP_SUCCESS;
+}
+
+enum idmap_error_code
+sss_idmap_ctx_get_lower(struct sss_idmap_ctx *ctx, id_t *_lower)
+{
+    CHECK_IDMAP_CTX(ctx, IDMAP_CONTEXT_INVALID);
+    *_lower = ctx->idmap_opts.idmap_lower;
+    return IDMAP_SUCCESS;
+}
+
+enum idmap_error_code
+sss_idmap_ctx_get_upper(struct sss_idmap_ctx *ctx, id_t *_upper)
+{
+    CHECK_IDMAP_CTX(ctx, IDMAP_CONTEXT_INVALID);
+    *_upper = ctx->idmap_opts.idmap_upper;
+    return IDMAP_SUCCESS;
+}
+
+enum idmap_error_code
+sss_idmap_ctx_get_rangesize(struct sss_idmap_ctx *ctx, id_t *_rangesize)
+{
+    CHECK_IDMAP_CTX(ctx, IDMAP_CONTEXT_INVALID);
+    *_rangesize =  ctx->idmap_opts.rangesize;
+    return IDMAP_SUCCESS;
+}
diff --git a/src/lib/idmap/sss_idmap.h b/src/lib/idmap/sss_idmap.h
index ced7074a..9204be0b 100644
--- a/src/lib/idmap/sss_idmap.h
+++ b/src/lib/idmap/sss_idmap.h
@@ -71,7 +71,10 @@ enum idmap_error_code {
     IDMAP_NO_RANGE,
 
     /** The provided SID is a built-in one */
-    IDMAP_BUILTIN_SID
+    IDMAP_BUILTIN_SID,
+
+    /* No more free slices */
+    IDMAP_OUT_OF_SLICES
 };
 
 /**
@@ -126,6 +129,100 @@ enum idmap_error_code sss_idmap_init(idmap_alloc_func *alloc_func,
                                      struct sss_idmap_ctx **ctx);
 
 /**
+ * @brief Set/unset autorid compatibility mode
+ *
+ * @param[in] ctx           idmap context
+ * @param[in] use_autorid   If true, autorid compatibility mode will be used
+ */
+enum idmap_error_code
+sss_idmap_ctx_set_autorid(struct sss_idmap_ctx *ctx, bool use_autorid);
+
+/**
+ * @brief Set the lower bound of the range of POSIX IDs
+ *
+ * @param[in] ctx           idmap context
+ * @param[in] lower         lower bound of the range
+ */
+enum idmap_error_code
+sss_idmap_ctx_set_lower(struct sss_idmap_ctx *ctx, id_t lower);
+
+/**
+ * @brief Set the upper bound of the range of POSIX IDs
+ *
+ * @param[in] ctx           idmap context
+ * @param[in] upper         upper bound of the range
+ */
+enum idmap_error_code
+sss_idmap_ctx_set_upper(struct sss_idmap_ctx *ctx, id_t upper);
+
+/**
+ * @brief Set the range size of POSIX IDs available for single domain
+ *
+ * @param[in] ctx           idmap context
+ * @param[in] rangesize     range size of IDs
+ */
+enum idmap_error_code
+sss_idmap_ctx_set_rangesize(struct sss_idmap_ctx *ctx, id_t rangesize);
+
+/**
+ * @brief Check if autorid compatibility mode is set
+ *
+ * @param[in] ctx           idmap context
+ * @param[out] _autorid     true if autorid is used
+ */
+enum idmap_error_code
+sss_idmap_ctx_get_autorid(struct sss_idmap_ctx *ctx, bool *_autorid);
+
+/**
+ * @brief Get the lower bound of the range of POSIX IDs
+ *
+ * @param[in] ctx           idmap context
+ * @param[out] _lower       returned lower bound
+ */
+enum idmap_error_code
+sss_idmap_ctx_get_lower(struct sss_idmap_ctx *ctx, id_t *_lower);
+
+/**
+ * @brief Get the upper bound of the range of POSIX IDs
+ *
+ * @param[in] ctx           idmap context
+ * @param[out] _upper       returned upper bound
+ */
+enum idmap_error_code
+sss_idmap_ctx_get_upper(struct sss_idmap_ctx *ctx, id_t *_upper);
+
+/**
+ * @brief Get the range size of POSIX IDs available for single domain
+ *
+ * @param[in] ctx           idmap context
+ * @param[out] _rangesize   returned range size
+ */
+enum idmap_error_code
+sss_idmap_ctx_get_rangesize(struct sss_idmap_ctx *ctx, id_t *rangesize);
+
+/**
+ * @brief Calculate new range of available POSIX IDs
+ *
+ * @param[in] ctx           Idmap context
+ * @param[in] dom_sid       Zero-terminated string representation of the domain
+ *                          SID (S-1-15-.....)
+ * @param[in/out] slice_num Slice number to be used. Set this pointer to NULL or
+ *                          the addressed value to -1 to calculate slice number
+ *                          automatically. The calculated value will be
+ *                          returned in this parameter.
+ * @param[out] range        Structure containing upper and lower bound of the
+ *                          range of POSIX IDs
+ *
+ * @return
+ *  - #IDMAP_OUT_OF_SLICES: Cannot calculate new range because all slices are
+ *                          used.
+ */
+enum idmap_error_code sss_idmap_calculate_range(struct sss_idmap_ctx *ctx,
+                                                const char *dom_sid,
+                                                id_t *slice_num,
+                                                struct sss_idmap_range *range);
+
+/**
  * @brief Add a domain to the idmap context
  *
  * @param[in] ctx         Idmap context
diff --git a/src/lib/idmap/sss_idmap_private.h b/src/lib/idmap/sss_idmap_private.h
index bdb52895..1d3a3690 100644
--- a/src/lib/idmap/sss_idmap_private.h
+++ b/src/lib/idmap/sss_idmap_private.h
@@ -25,16 +25,36 @@
 #ifndef SSS_IDMAP_PRIVATE_H_
 #define SSS_IDMAP_PRIVATE_H_
 
+#define SSS_IDMAP_DEFAULT_LOWER 200000
+#define SSS_IDMAP_DEFAULT_UPPER 2000200000
+#define SSS_IDMAP_DEFAULT_RANGESIZE 200000
+#define SSS_IDMAP_DEFAULT_AUTORID false
+
 #define CHECK_IDMAP_CTX(ctx, ret) do { \
     if (ctx == NULL || ctx->alloc_func == NULL || ctx->free_func == NULL) { \
         return ret; \
     } \
 } while(0)
 
+struct sss_idmap_opts {
+    /* true if autorid compatibility mode is used */
+    bool autorid_mode;
+
+    /* smallest available id (for all domains) */
+    id_t idmap_lower;
+
+    /* highest available id (for all domains) */
+    id_t idmap_upper;
+
+    /* number of available UIDs (for single domain) */
+    id_t rangesize;
+};
+
 struct sss_idmap_ctx {
     idmap_alloc_func *alloc_func;
     void *alloc_pvt;
     idmap_free_func *free_func;
+    struct sss_idmap_opts idmap_opts;
     struct idmap_domain_info *idmap_domain_info;
 };
 
diff --git a/src/providers/ldap/sdap_idmap.c b/src/providers/ldap/sdap_idmap.c
index 0db3265f..050b2c5a 100644
--- a/src/providers/ldap/sdap_idmap.c
+++ b/src/providers/ldap/sdap_idmap.c
@@ -50,6 +50,10 @@ sdap_idmap_init(TALLOC_CTX *mem_ctx,
     const char *dom_name;
     const char *sid_str;
     id_t slice_num;
+    id_t idmap_lower;
+    id_t idmap_upper;
+    id_t rangesize;
+    bool autorid_mode;
     struct sdap_idmap_ctx *idmap_ctx = NULL;
     struct sysdb_ctx *sysdb = id_ctx->be->domain->sysdb;
 
@@ -63,6 +67,32 @@ sdap_idmap_init(TALLOC_CTX *mem_ctx,
     }
     idmap_ctx->id_ctx = id_ctx;
 
+    idmap_lower = dp_opt_get_int(idmap_ctx->id_ctx->opts->basic,
+                                 SDAP_IDMAP_LOWER);
+    idmap_upper = dp_opt_get_int(idmap_ctx->id_ctx->opts->basic,
+                                 SDAP_IDMAP_UPPER);
+    rangesize = dp_opt_get_int(idmap_ctx->id_ctx->opts->basic,
+                               SDAP_IDMAP_RANGESIZE);
+    autorid_mode = dp_opt_get_bool(idmap_ctx->id_ctx->opts->basic,
+                                   SDAP_IDMAP_AUTORID_COMPAT);
+
+    /* Validate that the values make sense */
+    if (rangesize <= 0
+            || idmap_upper <= idmap_lower
+            || (idmap_upper-idmap_lower) < rangesize)
+    {
+        DEBUG(SSSDBG_CRIT_FAILURE,
+              ("Invalid settings for range selection: [%d][%d][%d]\n",
+               idmap_lower, idmap_upper, rangesize));
+        ret = EINVAL;
+    }
+
+    if (((idmap_upper - idmap_lower) % rangesize) != 0) {
+        DEBUG(SSSDBG_CONF_SETTINGS,
+              ("Range size does not divide evenly. Uppermost range will "
+               "not be used\n"));
+    }
+
     /* Initialize the map */
     err = sss_idmap_init(sdap_idmap_talloc, idmap_ctx,
                          sdap_idmap_talloc_free,
@@ -79,6 +109,16 @@ sdap_idmap_init(TALLOC_CTX *mem_ctx,
         goto done;
     }
 
+    err = sss_idmap_ctx_set_autorid(idmap_ctx->map, autorid_mode);
+    err |= sss_idmap_ctx_set_lower(idmap_ctx->map, idmap_lower);
+    err |= sss_idmap_ctx_set_upper(idmap_ctx->map, idmap_upper);
+    err |= sss_idmap_ctx_set_rangesize(idmap_ctx->map, rangesize);
+    if (err != IDMAP_SUCCESS) {
+        /* This should never happen */
+        DEBUG(SSSDBG_CRIT_FAILURE, ("sss_idmap_ctx corrupted\n"));
+        return EIO;
+    }
+
     /* Read in any existing mappings from the cache */
     ret = sysdb_idmap_get_mappings(tmp_ctx, sysdb, id_ctx->be->domain, &res);
     if (ret != EOK && ret != ENOENT) {
@@ -182,117 +222,27 @@ sdap_idmap_add_domain(struct sdap_idmap_ctx *idmap_ctx,
                       id_t slice)
 {
     errno_t ret;
-    struct sdap_idmap_slice *new_slice;
-    id_t idmap_lower;
-    id_t idmap_upper;
-    id_t rangesize;
-    id_t max_slices;
-    id_t orig_slice;
-    uint32_t hash_val;
-    struct sdap_idmap_slice *s;
     struct sss_idmap_range range;
     enum idmap_error_code err;
+    id_t idmap_upper;
 
-    idmap_lower = dp_opt_get_int(idmap_ctx->id_ctx->opts->basic,
-                                 SDAP_IDMAP_LOWER);
-    idmap_upper = dp_opt_get_int(idmap_ctx->id_ctx->opts->basic,
-                                 SDAP_IDMAP_UPPER);
-    rangesize = dp_opt_get_int(idmap_ctx->id_ctx->opts->basic,
-                               SDAP_IDMAP_RANGESIZE);
-
-    /* Validate that the values make sense */
-    if (rangesize <= 0
-            || idmap_upper <= idmap_lower
-            || (idmap_upper-idmap_lower) < rangesize)
-    {
+    ret = sss_idmap_ctx_get_upper(idmap_ctx->map, &idmap_upper);
+    if (ret != IDMAP_SUCCESS) {
         DEBUG(SSSDBG_CRIT_FAILURE,
-              ("Invalid settings for range selection: [%d][%d][%d]\n",
-               idmap_lower, idmap_upper, rangesize));
-        return EINVAL;
-    }
-
-    max_slices = (idmap_upper - idmap_lower) / rangesize;
-    if (((idmap_upper - idmap_lower) % rangesize) != 0) {
-        DEBUG(SSSDBG_CONF_SETTINGS,
-              ("Range size does not divide evenly. Uppermost range will "
-               "not be used\n"));
+              ("Failed to get upper bound of available ID range.\n"));
+        ret = EIO;
+        goto done;
     }
 
-    new_slice = talloc_zero(idmap_ctx, struct sdap_idmap_slice);
-    if (!new_slice) return ENOMEM;
-
-    if (slice != -1) {
-        /* The slice is being set explicitly.
-         * This may happen at system startup when we're loading
-         * previously-determined slices. In the future, we may also
-         * permit configuration to select the slice for a domain
-         * explicitly.
-         */
-        new_slice->slice_num = slice;
-    } else {
-        /* If slice is -1, we're being asked to pick a new slice */
-
-        if (dp_opt_get_bool(idmap_ctx->id_ctx->opts->basic, SDAP_IDMAP_AUTORID_COMPAT)) {
-            /* In autorid compatibility mode, always start at 0 and find the first
-             * free value.
-             */
-            orig_slice = 0;
-        } else {
-            /* Hash the domain sid string */
-            hash_val = murmurhash3(dom_sid, strlen(dom_sid), 0xdeadbeef);
-
-            /* Now get take the modulus of the hash val and the max_slices
-             * to determine its optimal position in the range.
-             */
-            new_slice->slice_num = hash_val % max_slices;
-            orig_slice = new_slice->slice_num;
-        }
-        /* Verify that this slice is not already in use */
-        do {
-            DLIST_FOR_EACH(s, idmap_ctx->slices) {
-                if (s->slice_num == new_slice->slice_num) {
-                    /* This slice number matches one already registered
-                     * We'll try the next available slot
-                     */
-                    new_slice->slice_num++;
-                    if (new_slice->slice_num > max_slices) {
-                        /* loop around to the beginning if necessary */
-                        new_slice->slice_num = 0;
-                    }
-                    break;
-                }
-            }
-
-            /* Keep trying until s is NULL (meaning we got to the end
-             * without matching) or we have run out of slices and gotten
-             * back to the first one we tried.
-             */
-        } while (s && new_slice->slice_num != orig_slice);
-
-        if (s) {
-            /* We looped all the way through and found no empty slots */
-            DEBUG(SSSDBG_CRIT_FAILURE,
-                  ("Could not add domain [%s]: no free slices\n",
-                   dom_name));
-            ret = ENOSPC;
-            goto done;
-        }
+    ret = sss_idmap_calculate_range(idmap_ctx->map, dom_sid, &slice, &range);
+    if (ret != IDMAP_SUCCESS) {
+        DEBUG(SSSDBG_CRIT_FAILURE,
+              ("Failed to calculate range for domain [%s]: [%d]\n", dom_name,
+               ret));
+        ret = EIO;
+        goto done;
     }
 
-    DEBUG(SSSDBG_CONF_SETTINGS,
-          ("Adding domain [%s] as slice [%d]\n",
-           dom_name, new_slice->slice_num));
-
-    DLIST_ADD_END(idmap_ctx->slices, new_slice, struct sdap_idmap_slice *);
-    /* Not adding a destructor to remove from this list, because it
-     * should never be possible. Removal from this list can only
-     * destabilize the system.
-     */
-
-    /* Create a range object to add to the mapping */
-    range.min = (rangesize * new_slice->slice_num) + idmap_lower;
-    range.max = range.min + rangesize;
-
     if (range.max > idmap_upper) {
         /* This should never happen */
         DEBUG(SSSDBG_CRIT_FAILURE,
@@ -316,11 +266,8 @@ sdap_idmap_add_domain(struct sdap_idmap_ctx *idmap_ctx,
     ret = sysdb_idmap_store_mapping(idmap_ctx->id_ctx->be->domain->sysdb,
                                     idmap_ctx->id_ctx->be->domain,
                                     dom_name, dom_sid,
-                                    new_slice->slice_num);
+                                    slice);
 done:
-    if (ret != EOK) {
-        talloc_free(new_slice);
-    }
     return ret;
 }
 
diff --git a/src/providers/ldap/sdap_idmap.h b/src/providers/ldap/sdap_idmap.h
index 99f2ad9e..2e2123ff 100644
--- a/src/providers/ldap/sdap_idmap.h
+++ b/src/providers/ldap/sdap_idmap.h
@@ -26,16 +26,8 @@
 #include "src/providers/ldap/sdap.h"
 #include "src/providers/ldap/ldap_common.h"
 
-struct sdap_idmap_slice {
-    struct sdap_idmap_slice *prev;
-    struct sdap_idmap_slice *next;
-
-    id_t slice_num;
-};
-
 struct sdap_idmap_ctx {
     struct sss_idmap_ctx *map;
-    struct sdap_idmap_slice *slices;
 
     struct sdap_id_ctx *id_ctx;
 };