src/director/user-directory.c

	user-directory.c revision afbc6221ea2dae6c86c04efbf443bd891cb61e45
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen/* Copyright (c) 2010-2016 Dovecot authors, see the included COPYING file */
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen#include "lib.h"
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen#include "ioloop.h"
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen#include "array.h"
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen#include "hash.h"
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen#include "llist.h"
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen#include "mail-user-hash.h"
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen#include "mail-host.h"
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen#include "user-directory.h"
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen/* n% of timeout_secs */
04c3ac276103b56185119bcff9a66de7a8bb0e68Timo Sirainen#define USER_NEAR_EXPIRING_PERCENTAGE 10
04c3ac276103b56185119bcff9a66de7a8bb0e68Timo Sirainen/* but min/max. of this many secs */
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen#define USER_NEAR_EXPIRING_MIN 3
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen#define USER_NEAR_EXPIRING_MAX 30
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainenstruct user_directory_iter {
de62ce819d59a529530da4b57be1b8d6dad13d6bTimo Sirainen    struct user_directory *dir;
9865d9e7c5713e41db939222ed9c0225a11fb99eTimo Sirainen    struct user *pos;
9865d9e7c5713e41db939222ed9c0225a11fb99eTimo Sirainen};
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainenstruct user_directory {
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    /* unsigned int username_hash => user */
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    HASH_TABLE(void *, struct user *) hash;
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    /* sorted by time */
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    struct user *head, *tail;
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    struct user *prev_insert_pos;
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
c18ff860dc22960fd37c272d929f889c7939a2c8Timo Sirainen    ARRAY(struct user_directory_iter *) iters;
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
4ee00532a265bdfb38539d811fcd12d51210ac35Timo Sirainen    char *username_hash_fmt;
04c3ac276103b56185119bcff9a66de7a8bb0e68Timo Sirainen    unsigned int timeout_secs;
1dd054126238349e1a7d3d1ffe7f8bc5fdbacb7aTimo Sirainen    /* If user's expire time is less than this many seconds away,
5fb3f13537dffd15a31e997da133a721c0728af8Timo Sirainen       don't assume that other directors haven't yet expired it */
5fb3f13537dffd15a31e997da133a721c0728af8Timo Sirainen    unsigned int user_near_expiring_secs;
5fb3f13537dffd15a31e997da133a721c0728af8Timo Sirainen};
5b62dea2f88165f3f4d87bba9011343f3ff415ffTimo Sirainen
5b62dea2f88165f3f4d87bba9011343f3ff415ffTimo Sirainenstatic void user_move_iters(struct user_directory *dir, struct user *user)
5b62dea2f88165f3f4d87bba9011343f3ff415ffTimo Sirainen{
5b62dea2f88165f3f4d87bba9011343f3ff415ffTimo Sirainen    struct user_directory_iter *const *iterp;
5b62dea2f88165f3f4d87bba9011343f3ff415ffTimo Sirainen
1dd054126238349e1a7d3d1ffe7f8bc5fdbacb7aTimo Sirainen    array_foreach(&dir->iters, iterp) {
f6aaada6101dd43cd80fe965ff1ab9bfaf776252Timo Sirainen        if ((*iterp)->pos == user)
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen            (*iterp)->pos = user->next;
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    }
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    if (dir->prev_insert_pos == user)
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen        dir->prev_insert_pos = user->next;
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen}
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainenstatic void user_free(struct user_directory *dir, struct user *user)
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen{
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    i_assert(user->host->user_count > 0);
d22301419109ed4a38351715e6760011421dadecTimo Sirainen    user->host->user_count--;
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    if (user->to_move != NULL) {
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen        /* director_user_expire is very short. user expired before
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen           moving the user finished or timed out. */
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen        timeout_remove(&user->to_move);
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    }
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    user_move_iters(dir, user);
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    hash_table_remove(dir->hash, POINTER_CAST(user->username_hash));
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    DLLIST2_REMOVE(&dir->head, &dir->tail, user);
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    i_free(user);
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen}
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainenstatic bool user_directory_user_has_connections(struct user_directory *dir,
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen                        struct user *user)
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen{
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    time_t expire_timestamp = user->timestamp + dir->timeout_secs;
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
9865d9e7c5713e41db939222ed9c0225a11fb99eTimo Sirainen    if (expire_timestamp > ioloop_time)
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen        return TRUE;
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
a10ed8c47534b4c6b6bf2711ccfe577e720a47b4Timo Sirainen    if (user->kill_state != USER_KILL_STATE_NONE) {
f605df8a4c15cc7a11e16fdde994d51473700890Timo Sirainen        /* don't free this user until the kill is finished */
f605df8a4c15cc7a11e16fdde994d51473700890Timo Sirainen        return TRUE;
f605df8a4c15cc7a11e16fdde994d51473700890Timo Sirainen    }
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    if (user->weak) {
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen        if (expire_timestamp + USER_NEAR_EXPIRING_MAX >= ioloop_time)
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen            return TRUE;
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen        i_warning("User %u weakness appears to be stuck, removing it",
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen              user->username_hash);
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    }
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen    return FALSE;
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen}
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainenstatic void user_directory_drop_expired(struct user_directory *dir)
9f19a50d5966643c4d1c5ca06868ac2ad31bc4d5Timo Sirainen{
9f19a50d5966643c4d1c5ca06868ac2ad31bc4d5Timo Sirainen    while (dir->head != NULL &&
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen           !user_directory_user_has_connections(dir, dir->head))
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen        user_free(dir, dir->head);
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen}
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainen
5fb3f13537dffd15a31e997da133a721c0728af8Timo Sirainenunsigned int user_directory_count(struct user_directory *dir)
5fb3f13537dffd15a31e997da133a721c0728af8Timo Sirainen{
5fb3f13537dffd15a31e997da133a721c0728af8Timo Sirainen    return hash_table_count(dir->hash);
5b62dea2f88165f3f4d87bba9011343f3ff415ffTimo Sirainen}
5b62dea2f88165f3f4d87bba9011343f3ff415ffTimo Sirainen
1ac7c8e9040e0d0b7e9f849e45b94bfe919595a9Timo Sirainenstruct user *user_directory_lookup(struct user_directory *dir,
                   unsigned int username_hash)
{
    struct user *user;

    user_directory_drop_expired(dir);
    user = hash_table_lookup(dir->hash, POINTER_CAST(username_hash));
    if (user != NULL && !user_directory_user_has_connections(dir, user)) {
        user_free(dir, user);
        user = NULL;
    }
    return user;
}

static void
user_directory_insert_backwards(struct user_directory *dir,
                struct user *pos, struct user *user)
{
    for (; pos != NULL; pos = pos->prev) {
        if (pos->timestamp <= user->timestamp)
            break;
    }
    if (pos == NULL)
        DLLIST2_PREPEND(&dir->head, &dir->tail, user);
    else {
        user->prev = pos;
        user->next = pos->next;
        user->prev->next = user;
        if (user->next != NULL)
            user->next->prev = user;
        else
            dir->tail = user;
    }
}

static void
user_directory_insert_forwards(struct user_directory *dir,
                   struct user *pos, struct user *user)
{
    for (; pos != NULL; pos = pos->next) {
        if (pos->timestamp >= user->timestamp)
            break;
    }
    if (pos == NULL)
        DLLIST2_APPEND(&dir->head, &dir->tail, user);
    else {
        user->prev = pos->prev;
        user->next = pos;
        if (user->prev != NULL)
            user->prev->next = user;
        else
            dir->head = user;
        user->next->prev = user;
    }
}

struct user *
user_directory_add(struct user_directory *dir, unsigned int username_hash,
           struct mail_host *host, time_t timestamp)
{
    struct user *user;

    /* make sure we don't add timestamps higher than ioloop time */
    if (timestamp > ioloop_time)
        timestamp = ioloop_time;

    user = i_new(struct user, 1);
    user->username_hash = username_hash;
    user->host = host;
    user->host->user_count++;
    user->timestamp = timestamp;

    if (dir->tail == NULL || (time_t)dir->tail->timestamp <= timestamp)
        DLLIST2_APPEND(&dir->head, &dir->tail, user);
    else {
        /* need to insert to correct position. we should get here
           only when handshaking. the handshaking USER requests should
           come sorted by timestamp. so keep track of the previous
           insert position, the next USER should be inserted after
           it. */
        if (dir->prev_insert_pos == NULL) {
            /* find the position starting from tail */
            user_directory_insert_backwards(dir, dir->tail, user);
        } else if (timestamp < (time_t)dir->prev_insert_pos->timestamp) {
            user_directory_insert_backwards(dir, dir->prev_insert_pos,
                            user);
        } else {
            user_directory_insert_forwards(dir, dir->prev_insert_pos,
                               user);
        }
    }

    dir->prev_insert_pos = user;
    hash_table_insert(dir->hash, POINTER_CAST(user->username_hash), user);
    return user;
}

void user_directory_refresh(struct user_directory *dir, struct user *user)
{
    user_move_iters(dir, user);

    user->timestamp = ioloop_time;
    DLLIST2_REMOVE(&dir->head, &dir->tail, user);
    DLLIST2_APPEND(&dir->head, &dir->tail, user);
}

void user_directory_remove_host(struct user_directory *dir,
                struct mail_host *host)
{
    struct user *user, *next;

    for (user = dir->head; user != NULL; user = next) {
        next = user->next;

        if (user->host == host)
            user_free(dir, user);
    }
}

static int user_timestamp_cmp(struct user *const *user1,
                  struct user *const *user2)
{
    if ((*user1)->timestamp < (*user2)->timestamp)
        return -1;
    if ((*user1)->timestamp > (*user2)->timestamp)
        return 1;
    return 0;
}

void user_directory_sort(struct user_directory *dir)
{
    ARRAY(struct user *) users;
    struct user *user, *const *userp;
    unsigned int i, users_count = hash_table_count(dir->hash);

    if (users_count == 0) {
        i_assert(dir->head == NULL);
        return;
    }

    /* place all users into array and sort it */
    i_array_init(&users, users_count);
    user = dir->head;
    for (i = 0; i < users_count; i++, user = user->next)
        array_append(&users, &user, 1);
    i_assert(user == NULL);
    array_sort(&users, user_timestamp_cmp);

    /* recreate the linked list */
    dir->head = dir->tail = NULL;
    array_foreach(&users, userp)
        DLLIST2_APPEND(&dir->head, &dir->tail, *userp);
    i_assert(dir->head != NULL &&
         dir->head->timestamp <= dir->tail->timestamp);
    array_free(&users);
}

unsigned int user_directory_get_username_hash(struct user_directory *dir,
                          const char *username)
{
    return mail_user_hash(username, dir->username_hash_fmt);
}

bool user_directory_user_is_recently_updated(struct user_directory *dir,
                         struct user *user)
{
    return (time_t)(user->timestamp + dir->timeout_secs/2) >= ioloop_time;
}

bool user_directory_user_is_near_expiring(struct user_directory *dir,
                      struct user *user)
{
    time_t expire_timestamp;

    expire_timestamp = user->timestamp +
        (dir->timeout_secs - dir->user_near_expiring_secs);
    return expire_timestamp < ioloop_time;
}

struct user_directory *
user_directory_init(unsigned int timeout_secs, const char *username_hash_fmt)
{
    struct user_directory *dir;

    i_assert(timeout_secs > USER_NEAR_EXPIRING_MIN);

    dir = i_new(struct user_directory, 1);
    dir->timeout_secs = timeout_secs;
    dir->user_near_expiring_secs =
        timeout_secs * USER_NEAR_EXPIRING_PERCENTAGE / 100;
    dir->user_near_expiring_secs =
        I_MIN(dir->user_near_expiring_secs, USER_NEAR_EXPIRING_MAX);
    dir->user_near_expiring_secs =
        I_MAX(dir->user_near_expiring_secs, USER_NEAR_EXPIRING_MIN);
    i_assert(dir->timeout_secs/2 > dir->user_near_expiring_secs);

    dir->username_hash_fmt = i_strdup(username_hash_fmt);
    hash_table_create_direct(&dir->hash, default_pool, 0);
    i_array_init(&dir->iters, 8);
    return dir;
}

void user_directory_deinit(struct user_directory **_dir)
{
    struct user_directory *dir = *_dir;

    *_dir = NULL;

    i_assert(array_count(&dir->iters) == 0);

    while (dir->head != NULL)
        user_free(dir, dir->head);
    hash_table_destroy(&dir->hash);
    array_free(&dir->iters);
    i_free(dir->username_hash_fmt);
    i_free(dir);
}

struct user_directory_iter *
user_directory_iter_init(struct user_directory *dir)
{
    struct user_directory_iter *iter;

    iter = i_new(struct user_directory_iter, 1);
    iter->dir = dir;
    iter->pos = dir->head;
    array_append(&dir->iters, &iter, 1);
    user_directory_drop_expired(dir);
    return iter;
}

struct user *user_directory_iter_next(struct user_directory_iter *iter)
{
    struct user *user;

    user = iter->pos;
    if (user == NULL)
        return NULL;

    iter->pos = user->next;
    return user;
}

void user_directory_iter_deinit(struct user_directory_iter **_iter)
{
    struct user_directory_iter *iter = *_iter;
    struct user_directory_iter *const *iters;
    unsigned int i, count;

    *_iter = NULL;

    iters = array_get(&iter->dir->iters, &count);
    for (i = 0; i < count; i++) {
        if (iters[i] == iter) {
            array_delete(&iter->dir->iters, i, 1);
            break;
        }
    }
    i_free(iter);
}