/*      $NetBSD: vfs_dirhash.c,v 1.18 2025/12/28 21:27:55 andvar Exp $  */

/*
 * Copyright (c) 2008, 2025 Reinoud Zandijk
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD: vfs_dirhash.c,v 1.18 2025/12/28 21:27:55 andvar Exp $");

/* CLEAN UP! */
#include <sys/param.h>
#include <sys/types.h>

#include <sys/buf.h>
#include <sys/dirent.h>
#include <sys/dirhash.h>
#include <sys/hash.h>
#include <sys/kernel.h>
#include <sys/mutex.h>
#include <sys/pool.h>
#include <sys/queue.h>
#include <sys/sysctl.h>
#include <sys/vnode.h>

#if 1
#       define DPRINTF(a) __nothing
#else
#       define DPRINTF(a) printf a
#endif

/*
 * defaults for dirhash cache sizes:
 *  - use up to 1/64th of system memory.
 *  - cap maximum size of the default dirhash cache at 32mb.
 */
#define DIRHASH_DEFAULT_DIVIDER 64
#define MIN_DEFAULT_DIRHASH_MEM (1024*1024)
#define MAX_DEFAULT_DIRHASH_MEM (32*1024*1024)
#define DIRHASH_PURGE_BLOCK     (16*1024)

/*
 * The locking protocol of the dirhash structures is fairly simple:
 *
 * The global dirhash_queue is protected by the dirhashmutex. This lock is
 * internal only and is FS/mountpoint/vnode independent. On exit of the
 * exported functions this mutex is not held.
 *
 * The dirhash structure is considered part of the vnode/inode structure and
 * will thus use the lock that protects that vnode/inode.
 *
 * The dirhash entries are considered part of the dirhash structure and thus
 * are on the same lock.
 */

static struct sysctllog *sysctl_log;
static struct pool dirhash_pool;
static struct pool dirhash_entry_pool;

static kmutex_t dirhashmutex;
static uint32_t maxdirhashsize = MIN_DEFAULT_DIRHASH_MEM;
static uint32_t dirhashsize    = 0;
static TAILQ_HEAD(_dirhash, dirhash) dirhash_queue;


void
dirhash_init(void)
{
        const struct sysctlnode *rnode, *cnode;
        size_t sz;
        uint64_t physmem_bytes;
        uint32_t max_entries;

        /* initialise dirhash queue */
        TAILQ_INIT(&dirhash_queue);

        /* init dirhash pools */
        sz = sizeof(struct dirhash);
        pool_init(&dirhash_pool, sz, 0, 0, 0,
            "dirhpl", NULL, IPL_NONE);

        sz = sizeof(struct dirhash_entry);
        pool_init(&dirhash_entry_pool, sz, 0, 0, 0,
            "dirhepl", NULL, IPL_NONE);

        /* calculate the default maximum dirhashsize */
        physmem_bytes = ctob((uint64_t) physmem);
        maxdirhashsize = physmem_bytes / DIRHASH_DEFAULT_DIVIDER;
        if (maxdirhashsize < MIN_DEFAULT_DIRHASH_MEM)
                maxdirhashsize = MIN_DEFAULT_DIRHASH_MEM;
        if (maxdirhashsize > MAX_DEFAULT_DIRHASH_MEM)
                maxdirhashsize = MAX_DEFAULT_DIRHASH_MEM;

        mutex_init(&dirhashmutex, MUTEX_DEFAULT, IPL_NONE);
        max_entries = maxdirhashsize / sz;
        pool_sethiwat(&dirhash_entry_pool, max_entries);
        dirhashsize = 0;

        /* create sysctl knobs and dials */
        sysctl_log = NULL;
        sysctl_createv(&sysctl_log, 0, NULL, &rnode,
            CTLFLAG_PERMANENT,
            CTLTYPE_NODE, "dirhash", NULL,
            NULL, 0, NULL, 0,
            CTL_VFS, VFS_GENERIC, CTL_CREATE, CTL_EOL);
        sysctl_createv(&sysctl_log, 0, &rnode, &cnode,
            CTLFLAG_PERMANENT,
            CTLTYPE_INT, "memused",
            SYSCTL_DESCR("current dirhash memory usage"),
            NULL, 0, &dirhashsize, 0,
            CTL_CREATE, CTL_EOL);
        sysctl_createv(&sysctl_log, 0, &rnode, &cnode,
            CTLFLAG_PERMANENT | CTLFLAG_READWRITE,
            CTLTYPE_INT, "maxmem",
            SYSCTL_DESCR("maximum dirhash memory usage"),
            NULL, 0, &maxdirhashsize, 0,
            CTL_CREATE, CTL_EOL);
}


#if 0
void
dirhash_finish(void)
{
        pool_destroy(&dirhash_pool);
        pool_destroy(&dirhash_entry_pool);

        mutex_destroy(&dirhashmutex);

        /* sysctl_teardown(&sysctl_log); */
}
#endif

/*
 * generic dirhash implementation
 */

void
dirhash_purge_entries(struct dirhash *dirh)
{
        struct dirhash_entry *dirh_e;
        uint32_t hashline;

        if (dirh == NULL)
                return;

        if (dirh->size == 0)
                return;

        for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) {
                while ((dirh_e = LIST_FIRST(&dirh->entries[hashline]))
                    != NULL) {
                        LIST_REMOVE(dirh_e, next);
                        pool_put(&dirhash_entry_pool, dirh_e);
                }
        }

        while ((dirh_e = LIST_FIRST(&dirh->free_entries)) != NULL) {
                LIST_REMOVE(dirh_e, next);
                pool_put(&dirhash_entry_pool, dirh_e);
        }

        dirh->flags &= ~DIRH_COMPLETE;
        dirh->flags |=  DIRH_PURGED;
        dirh->num_files = 0;

        dirhashsize -= dirh->size;
        dirh->size = 0;
}

void
dirhash_purge(struct dirhash **dirhp)
{
        struct dirhash *dirh = *dirhp;

        if (dirh == NULL)
                return;

        /* purge its entries */
        dirhash_purge_entries(dirh);

        /* recycle */
        mutex_enter(&dirhashmutex);
        TAILQ_REMOVE(&dirhash_queue, dirh, next);
        mutex_exit(&dirhashmutex);

        pool_put(&dirhash_pool, dirh);
        *dirhp = NULL;
}

void
dirhash_get(struct dirhash **dirhp)
{
        struct dirhash *dirh;
        uint32_t hashline;

        /* protect against concurrent VOP_LOOKUP calls */
        mutex_enter(&dirhashmutex);

        /* if no dirhash was given, allocate one */
        dirh = *dirhp;
        if (dirh == NULL) {
                dirh = pool_get(&dirhash_pool, PR_WAITOK | PR_ZERO);
                for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) {
                        LIST_INIT(&dirh->entries[hashline]);
                }
        }

        /* implement LRU on the dirhash queue */
        if (*dirhp) {
                /* remove from queue to be requeued */
                TAILQ_REMOVE(&dirhash_queue, dirh, next);
        }
        dirh->refcnt++;
        TAILQ_INSERT_HEAD(&dirhash_queue, dirh, next);
        mutex_exit(&dirhashmutex);

        *dirhp = dirh;
}

void
dirhash_put(struct dirhash *dirh)
{

        mutex_enter(&dirhashmutex);
        dirh->refcnt--;
        mutex_exit(&dirhashmutex);
}

void
dirhash_enter(struct dirhash *dirh,
    struct dirent *dirent, uint64_t offset, uint32_t entry_size, int new_p)
{
        struct dirhash *p_dirh;
        struct dirhash_entry *dirh_e;
        uint32_t hashvalue, hashline;
        int entrysize;

        /* make sure we have a dirhash to work on */
        KASSERT(dirh);
        KASSERT(dirh->refcnt > 0);

        /* are we trying to re-enter an entry? */
        if (!new_p && (dirh->flags & DIRH_COMPLETE))
                return;

        /* calculate our hash */
        hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen,
            HASH32_STR_INIT);
        hashline  = hashvalue & DIRHASH_HASHMASK;

        /* lookup and insert entry if not there yet */
        LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) {
                /* check for hash collision */
                if (dirh_e->hashvalue != hashvalue)
                        continue;
                if (dirh_e->offset != offset)
                        continue;
                /* got it already */
                KASSERT(dirh_e->d_namlen == dirent->d_namlen);
                KASSERT(dirh_e->entry_size == entry_size);
                return;
        }

        DPRINTF(("dirhash enter %"PRIu64", %d, %d for `%*.*s`\n",
                offset, entry_size, dirent->d_namlen,
                dirent->d_namlen, dirent->d_namlen, dirent->d_name));

        /* check if entry is in free space list */
        LIST_FOREACH(dirh_e, &dirh->free_entries, next) {
                if (dirh_e->offset == offset) {
                        DPRINTF(("\tremoving free entry\n"));
                        LIST_REMOVE(dirh_e, next);
                        pool_put(&dirhash_entry_pool, dirh_e);
                        break;
                }
        }

        /* ensure we are not passing the dirhash limit */
        entrysize = sizeof(struct dirhash_entry);
        if (dirhashsize + entrysize > maxdirhashsize) {
                /* we walk the dirhash_queue, so need to lock it */
                mutex_enter(&dirhashmutex);
                TAILQ_FOREACH_REVERSE(p_dirh, &dirhash_queue, _dirhash, next) {
                        /* satisfied? */
                        if (dirhashsize + entrysize <
                                        maxdirhashsize - DIRHASH_PURGE_BLOCK)
                                break;
                        if (p_dirh->refcnt)
                                continue;

                        /* this can't be ourselves */
                        KASSERT(p_dirh != dirh);
                        dirhash_purge_entries(p_dirh);
                }
                /* if not enough is cleaned, we just give up */
                mutex_exit(&dirhashmutex);
        }

        /* add to the hashline */
        dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK | PR_ZERO);

        dirh_e->hashvalue = hashvalue;
        dirh_e->offset    = offset;
        dirh_e->d_namlen  = dirent->d_namlen;
        dirh_e->entry_size  = entry_size;

        dirh->size  += sizeof(struct dirhash_entry);
        dirh->num_files++;
        dirhashsize += sizeof(struct dirhash_entry);
        LIST_INSERT_HEAD(&dirh->entries[hashline], dirh_e, next);
}

void
dirhash_enter_freed(struct dirhash *dirh, uint64_t offset, uint32_t entry_size)
{
        struct dirhash_entry *dirh_e;

        /* make sure we have a dirhash to work on */
        KASSERT(dirh);
        KASSERT(dirh->refcnt > 0);

        /* check for double entry of free space */
        LIST_FOREACH(dirh_e, &dirh->free_entries, next) {
                KASSERT(dirh_e->offset != offset);
        }

        DPRINTF(("dirhash enter FREED %"PRIu64", %d\n",
                offset, entry_size));
        dirh_e = pool_get(&dirhash_entry_pool, PR_WAITOK | PR_ZERO);

        dirh_e->hashvalue = 0;          /* not relevant */
        dirh_e->offset    = offset;
        dirh_e->d_namlen  = 0;          /* not relevant */
        dirh_e->entry_size  = entry_size;

        /* XXX it might be preferable to append them at the tail */
        LIST_INSERT_HEAD(&dirh->free_entries, dirh_e, next);
        dirh->size  += sizeof(struct dirhash_entry);
        dirhashsize += sizeof(struct dirhash_entry);
}

void
dirhash_remove(struct dirhash *dirh, struct dirent *dirent,
    uint64_t offset, uint32_t entry_size)
{
        struct dirhash_entry *dirh_e;
        uint32_t hashvalue, hashline;

        DPRINTF(("dirhash remove %"PRIu64", %d for `%*.*s`\n",
                offset, entry_size,
                dirent->d_namlen, dirent->d_namlen, dirent->d_name));

        /* make sure we have a dirhash to work on */
        KASSERT(dirh);
        KASSERT(dirh->refcnt > 0);

        /* calculate our hash */
        hashvalue = hash32_strn(dirent->d_name, dirent->d_namlen,
            HASH32_STR_INIT);
        hashline  = hashvalue & DIRHASH_HASHMASK;

        /* lookup entry */
        LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) {
                /* check for hash collision */
                if (dirh_e->hashvalue != hashvalue)
                        continue;
                if (dirh_e->offset != offset)
                        continue;

                /* got it! */
                KASSERT(dirh_e->d_namlen == dirent->d_namlen);
                KASSERT(dirh_e->entry_size == entry_size);
                LIST_REMOVE(dirh_e, next);
                dirh->size -= sizeof(struct dirhash_entry);
                KASSERT(dirh->num_files > 0);
                dirh->num_files--;
                dirhashsize -= sizeof(struct dirhash_entry);

                dirhash_enter_freed(dirh, offset, entry_size);
                return;
        }

        /* not found! */
        panic("dirhash_remove couldn't find entry in hash table\n");
}

/*
 * BUGALERT: don't use result longer than needed, never past the node lock.
 * Call with NULL *result initially and it will return nonzero if again.
 */
int
dirhash_lookup(struct dirhash *dirh, const char *d_name, int d_namlen,
    struct dirhash_entry **result)
{
        struct dirhash_entry *dirh_e;
        uint32_t hashvalue, hashline;

        /* make sure we have a dirhash to work on */
        KASSERT(dirh);
        KASSERT(dirh->refcnt > 0);

        /* start where we were */
        if (*result) {
                dirh_e = *result;

                /* retrieve information to avoid recalculation and advance */
                hashvalue = dirh_e->hashvalue;
                dirh_e = LIST_NEXT(*result, next);
        } else {
                /* calculate our hash and lookup all entries in hashline */
                hashvalue = hash32_strn(d_name, d_namlen, HASH32_STR_INIT);
                hashline  = hashvalue & DIRHASH_HASHMASK;
                dirh_e = LIST_FIRST(&dirh->entries[hashline]);
        }

        for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) {
                /* check for hash collision */
                if (dirh_e->hashvalue != hashvalue)
                        continue;
                if (dirh_e->d_namlen != d_namlen)
                        continue;
                /* might have an entry in the cache */
                *result = dirh_e;
                return 1;
        }

        *result = NULL;
        return 0;
}

/*
 * BUGALERT: don't use result longer than needed, never past the node lock.
 * Call with NULL *result initially and it will return nonzero if again.
 */
int
dirhash_lookup_freed(struct dirhash *dirh, uint32_t min_entrysize,
    struct dirhash_entry **result)
{
        struct dirhash_entry *dirh_e;

        /* make sure we have a dirhash to work on */
        KASSERT(dirh);
        KASSERT(dirh->refcnt > 0);

        /* start where we were */
        if (*result) {
                dirh_e = LIST_NEXT(*result, next);
        } else {
                /* lookup all entries that match */
                dirh_e = LIST_FIRST(&dirh->free_entries);
        }

        for (; dirh_e; dirh_e = LIST_NEXT(dirh_e, next)) {
                /* check for minimum size */
                if (dirh_e->entry_size < min_entrysize)
                        continue;
                /* might be a candidate */
                *result = dirh_e;
                return 1;
        }

        *result = NULL;
        return 0;
}

bool
dirhash_dir_isempty(struct dirhash *dirh)
{
#ifdef DEBUG
        struct dirhash_entry *dirh_e;
        int hashline, num;

        num = 0;
        for (hashline = 0; hashline < DIRHASH_HASHSIZE; hashline++) {
                LIST_FOREACH(dirh_e, &dirh->entries[hashline], next) {
                        num++;
                }
        }

        if (dirh->num_files != num) {
                printf("dirhash_dir_isempty: dirhash_counter failed: "
                    "dirh->num_files = %d, counted %d\n",
                    dirh->num_files, num);
                assert(dirh->num_files == num);
        }
#endif
        /* assert the directory hash info is valid */
        KASSERT(dirh->flags & DIRH_COMPLETE);

        /* the directory is empty when only '..' lifes in it or is absent */
        return (dirh->num_files <= 1);
}