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

3 files changed, 287 insertions, 1 deletions

diff --git a/src/lib/idmap/sss_idmap.c b/src/lib/idmap/sss_idmap.c
index 1764b6f4b..24506c68f 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 ced7074a9..9204be0b6 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 bdb528951..1d3a36901 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;
 };