/*      $NetBSD: kern_history.c,v 1.21 2026/01/04 01:34:29 riastradh Exp $       */

/*
 * Copyright (c) 1997 Charles D. Cranor and Washington University.
 * 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.
 *
 * from: NetBSD: uvm_stat.c,v 1.36 2011/02/02 15:13:34 chuck Exp
 * from: Id: uvm_stat.c,v 1.1.2.3 1997/12/19 15:01:00 mrg Exp
 */

/*
 * subr_kernhist.c
 */

#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD: kern_history.c,v 1.21 2026/01/04 01:34:29 riastradh Exp $");

#include "opt_ddb.h"
#include "opt_kernhist.h"
#include "opt_syscall_debug.h"
#include "opt_usb.h"
#include "opt_uvmhist.h"
#include "opt_biohist.h"
#include "opt_sysctl.h"

#include <sys/param.h>
#include <sys/types.h>

#include <sys/atomic.h>
#include <sys/cpu.h>
#include <sys/kernhist.h>
#include <sys/kmem.h>
#include <sys/sdt.h>
#include <sys/sysctl.h>
#include <sys/systm.h>

#ifdef UVMHIST
#include <uvm/uvm.h>
#endif

#ifdef USB_DEBUG
#include <dev/usb/usbhist.h>
#endif

#ifdef BIOHIST
#include <sys/biohist.h>
#endif

#ifdef SYSCALL_DEBUG
KERNHIST_DECL(scdebughist);
#endif

struct addr_xlt {
        const char *addr;
        size_t len;
        uint32_t offset;
};

/*
 * globals
 */

struct kern_history_head kern_histories;
bool kernhist_sysctl_ready = 0;

int kernhist_print_enabled = 1;

int sysctl_hist_node;

static int sysctl_kernhist_helper(SYSCTLFN_PROTO);

#ifdef DDB

/*
 * prototypes
 */

void kernhist_dump(struct kern_history *, size_t count,
    void (*)(const char *, ...) __printflike(1, 2));
static void kernhist_info(struct kern_history *,
    void (*)(const char *, ...));
void kernhist_dumpmask(uint32_t);
static void kernhist_dump_histories(struct kern_history *[], size_t count,
    void (*)(const char *, ...) __printflike(1, 2));

/* display info about one kernhist */
static void
kernhist_info(struct kern_history *l, void (*pr)(const char *, ...))
{

        pr("kernhist '%s': at %p total %u next free %u\n",
            l->name, l, l->n, l->f);
}

/*
 * call this from ddb
 *
 * expects the system to be quiesced, no locking
 */
void
kernhist_dump(struct kern_history *l, size_t count,
    void (*pr)(const char *, ...))
{
        int lcv;

        lcv = l->f;
        if (count > l->n)
                pr("%s: count %zu > size %u\n", __func__, count, l->n);
        else if (count)
                lcv = (lcv - count) % l->n;

        do {
                if (l->e[lcv].fmt)
                        kernhist_entry_print(&l->e[lcv], pr);
                lcv = (lcv + 1) % l->n;
        } while (lcv != l->f);
}

/*
 * print a merged list of kern_history structures.  count is unused so far.
 */
static void
kernhist_dump_histories(struct kern_history *hists[], size_t count,
    void (*pr)(const char *, ...))
{
        struct bintime  bt;
        int     cur[MAXHISTS];
        int     lcv, hi;

        /* find the first of each list */
        for (lcv = 0; hists[lcv]; lcv++)
                 cur[lcv] = hists[lcv]->f;

        /*
         * here we loop "forever", finding the next earliest
         * history entry and printing it.  cur[X] is the current
         * entry to test for the history in hists[X].  if it is
         * -1, then this history is finished.
         */
        for (;;) {
                hi = -1;
                bt.sec = 0; bt.frac = 0;

                /* loop over each history */
                for (lcv = 0; hists[lcv]; lcv++) {
restart:
                        if (cur[lcv] == -1)
                                continue;
                        if (!hists[lcv]->e)
                                continue;

                        /*
                         * if the format is empty, go to the next entry
                         * and retry.
                         */
                        if (hists[lcv]->e[cur[lcv]].fmt == NULL) {
                                cur[lcv] = (cur[lcv] + 1) % (hists[lcv]->n);
                                if (cur[lcv] == hists[lcv]->f)
                                        cur[lcv] = -1;
                                goto restart;
                        }

                        /*
                         * if the time hasn't been set yet, or this entry is
                         * earlier than the current bt, set the time and history
                         * index.
                         */
                        if (bt.sec == 0 ||
                            bintimecmp(&hists[lcv]->e[cur[lcv]].bt, &bt, <)) {
                                bt = hists[lcv]->e[cur[lcv]].bt;
                                hi = lcv;
                        }
                }

                /* if we didn't find any entries, we must be done */
                if (hi == -1)
                        break;

                /* print and move to the next entry */
                kernhist_entry_print(&hists[hi]->e[cur[hi]], pr);

                cur[hi] = (cur[hi] + 1) % (hists[hi]->n);
                if (cur[hi] == hists[hi]->f)
                        cur[hi] = -1;
        }
}

/*
 * call this from ddb.  `bitmask' is from <sys/kernhist.h>.  it
 * merges the named histories.
 *
 * expects the system to be quiesced, no locking
 */
void
kernhist_dumpmask(uint32_t bitmask)     /* XXX only support 32 hists */
{
        struct kern_history *hists[MAXHISTS + 1];
        int i = 0;

#ifdef UVMHIST
        if ((bitmask & KERNHIST_UVMMAPHIST) || bitmask == 0)
                hists[i++] = &maphist;

        if ((bitmask & KERNHIST_UVMPDHIST) || bitmask == 0)
                hists[i++] = &pdhist;

        if ((bitmask & KERNHIST_UVMUBCHIST) || bitmask == 0)
                hists[i++] = &ubchist;

        if ((bitmask & KERNHIST_UVMLOANHIST) || bitmask == 0)
                hists[i++] = &loanhist;
#endif

#ifdef USB_DEBUG
        if ((bitmask & KERNHIST_USBHIST) || bitmask == 0)
                hists[i++] = &usbhist;
#endif

#ifdef SYSCALL_DEBUG
        if ((bitmask & KERNHIST_SCDEBUGHIST) || bitmask == 0)
                hists[i++] = &scdebughist;
#endif

#ifdef BIOHIST
        if ((bitmask & KERNHIST_BIOHIST) || bitmask == 0)
                hists[i++] = &biohist;
#endif

        hists[i] = NULL;

        kernhist_dump_histories(hists, 0, printf);
}

/*
 * kernhist_print: ddb hook to print kern history.
 */
void
kernhist_print(void *addr, size_t count, const char *modif,
    void (*pr)(const char *, ...) __printflike(1,2))
{
        struct kern_history *h;

        LIST_FOREACH(h, &kern_histories, list) {
                if (h == addr)
                        break;
        }

        if (h == NULL) {
                struct kern_history *hists[MAXHISTS + 1];
                int i = 0;
#ifdef UVMHIST
                hists[i++] = &maphist;
                hists[i++] = &pdhist;
                hists[i++] = &ubchist;
                hists[i++] = &loanhist;
#endif
#ifdef USB_DEBUG
                hists[i++] = &usbhist;
#endif

#ifdef SYSCALL_DEBUG
                hists[i++] = &scdebughist;
#endif
#ifdef BIOHIST
                hists[i++] = &biohist;
#endif
                hists[i] = NULL;

                if (*modif == 'i') {
                        int lcv;

                        for (lcv = 0; hists[lcv]; lcv++)
                                kernhist_info(hists[lcv], pr);
                } else {
                        kernhist_dump_histories(hists, count, pr);
                }
        } else {
                if (*modif == 'i')
                        kernhist_info(h, pr);
                else
                        kernhist_dump(h, count, pr);
        }
}

#endif

/*
 * sysctl interface
 */

/*
 * sysctl_kernhist_new()
 *
 *      If the specified history (or, if no history is specified, any
 *      history) does not already have a sysctl node (under kern.hist)
 *      we create a new one and record it's node number.
 */
void
sysctl_kernhist_new(struct kern_history *hist)
{
        int error;
        struct kern_history *h;
        const struct sysctlnode *rnode = NULL;

        membar_consumer();
        if (kernhist_sysctl_ready == 0)
                return;

        LIST_FOREACH(h, &kern_histories, list) {
                if (hist && h != hist)
                        continue;
                if (h->s != 0)
                        continue;
                error = sysctl_createv(NULL, 0, NULL, &rnode,
                            CTLFLAG_PERMANENT,
                            CTLTYPE_STRUCT, h->name,
                            SYSCTL_DESCR("history data"),
                            sysctl_kernhist_helper, 0, NULL, 0,
                            CTL_KERN, sysctl_hist_node, CTL_CREATE, CTL_EOL);
                if (error == 0)
                        h->s = rnode->sysctl_num;
                if (hist == h)
                        break;
        }
}

/*
 * sysctl_kerhnist_init()
 *
 *      Create the 2nd level "hw.hist" sysctl node
 */
void
sysctl_kernhist_init(void)
{
        const struct sysctlnode *rnode = NULL;

        sysctl_createv(NULL, 0, NULL, &rnode,
                        CTLFLAG_PERMANENT,
                        CTLTYPE_NODE, "hist",
                        SYSCTL_DESCR("kernel history tables"),
                        sysctl_kernhist_helper, 0, NULL, 0,
                        CTL_KERN, CTL_CREATE, CTL_EOL);
        sysctl_hist_node = rnode->sysctl_num;

        kernhist_sysctl_ready = 1;
        membar_producer();

        sysctl_kernhist_new(NULL);
}

/*
 * find_string()
 *
 *      Search the address-to-offset translation table for matching an
 *      address and len, and return the index of the entry we found.  If
 *      not found, returns index 0 which points to the "?" entry.  (We
 *      start matching at index 1, ignoring any matches of the "?" entry
 *      itself.)
 */
static int
find_string(struct addr_xlt table[], size_t *count, const char *string,
            size_t len)
{
        int i;

        for (i = 1; i < *count; i++)
                if (string == table[i].addr && len == table[i].len)
                        return i;

        return 0;
}

/*
 * add_string()
 *
 *      If the string and len are unique, add a new address-to-offset
 *      entry in the translation table and set the offset of the next
 *      entry.
 */
static void
add_string(struct addr_xlt table[], size_t *count, const char *string,
           size_t len)
{

        if (find_string(table, count, string, len) == 0) {
                table[*count].addr = string;
                table[*count].len = len;
                table[*count + 1].offset = table[*count].offset + len + 1;
                (*count)++;
        }
}

/*
 * sysctl_kernhist_helper
 *
 *      This helper routine is called for all accesses to the kern.hist
 *      hierarchy.
 */
static int
sysctl_kernhist_helper(SYSCTLFN_ARGS)
{
        struct kern_history *h;
        struct kern_history_ent *in_evt;
        struct sysctl_history_event *out_evt;
        struct sysctl_history *buf;
        struct addr_xlt *xlate_t, *xlt;
        size_t bufsize, xlate_s;
        size_t xlate_c;
        const char *strp __diagused;
        char *next;
        int i, j;
        int error;

        if (namelen == 1 && name[0] == CTL_QUERY)
                return sysctl_query(SYSCTLFN_CALL(rnode));

        /*
         * Disallow userland updates, verify that we arrived at a
         * valid history rnode
         */
        if (newp)
                return SET_ERROR(EPERM);
        if (namelen != 1 || name[0] != CTL_EOL)
                return SET_ERROR(EINVAL);

        /* Find the correct kernhist for this sysctl node */
        LIST_FOREACH(h, &kern_histories, list) {
                if (h->s == rnode->sysctl_num)
                        break;
        }
        if (h == NULL)
                return SET_ERROR(ENOENT);

        /*
         * Worst case is two string pointers per history entry, plus
         * two for the history name and "?" string; allocate an extra
         * entry since we pre-set the "next" entry's offset member.
         */
        xlate_s = sizeof(struct addr_xlt) * h->n * 2 + 3;
        xlate_t = kmem_alloc(xlate_s, KM_SLEEP);
        xlate_c = 0;

        /* offset 0 reserved for NULL pointer, ie unused history entry */
        xlate_t[0].offset = 1;

        /*
         * If the history gets updated and an unexpected string is
         * found later, we'll point it here.  Otherwise, we'd have to
         * repeat this process iteratively, and it could take multiple
         * iterations before terminating.
         */
        add_string(xlate_t, &xlate_c, "?", 0);

        /* Copy the history name itself to the export structure */
        add_string(xlate_t, &xlate_c, h->name, h->namelen);

        /*
         * Loop through all used history entries to find the unique
         * fn and fmt strings
         */
        for (i = 0, in_evt = h->e; i < h->n; i++, in_evt++) {
                if (in_evt->fn == NULL)
                        continue;
                add_string(xlate_t, &xlate_c, in_evt->fn, in_evt->fnlen);
                add_string(xlate_t, &xlate_c, in_evt->fmt, in_evt->fmtlen);
        }

        /* Total buffer size includes header, events, and string table */
        bufsize = sizeof(struct sysctl_history) +
            h->n * sizeof(struct sysctl_history_event) +
            xlate_t[xlate_c].offset;
        buf = kmem_alloc(bufsize, KM_SLEEP);

        /*
         * Copy history header info to the export structure
         */
        j = find_string(xlate_t, &xlate_c, h->name, h->namelen);
        buf->sh_nameoffset = xlate_t[j].offset;
        buf->sh_numentries = h->n;
        buf->sh_nextfree = h->f;

        /*
         * Loop through the history events again, copying the data to
         * the export structure
         */
        for (i = 0, in_evt = h->e, out_evt = buf->sh_events; i < h->n;
            i++, in_evt++, out_evt++) {
                if (in_evt->fn == NULL) {       /* skip unused entries */
                        out_evt->she_funcoffset = 0;
                        out_evt->she_fmtoffset = 0;
                        continue;
                }
                out_evt->she_bintime = in_evt->bt;
                out_evt->she_callnumber = in_evt->call;
                out_evt->she_cpunum = in_evt->cpunum;
                out_evt->she_values[0] = in_evt->v[0];
                out_evt->she_values[1] = in_evt->v[1];
                out_evt->she_values[2] = in_evt->v[2];
                out_evt->she_values[3] = in_evt->v[3];
                j = find_string(xlate_t, &xlate_c, in_evt->fn, in_evt->fnlen);
                out_evt->she_funcoffset = xlate_t[j].offset;
                j = find_string(xlate_t, &xlate_c, in_evt->fmt, in_evt->fmtlen);
                out_evt->she_fmtoffset = xlate_t[j].offset;
        }

        /*
         * Finally, fill the text string area with all the unique
         * strings we found earlier.
         *
         * Skip the initial byte, since we use an offset of 0 to mean
         * a NULL pointer (which means an unused history event).
         */
        strp = next = (char *)(&buf->sh_events[h->n]);
        *next++ = '\0';

        /*
         * Then copy each string into the export structure, making
         * sure to terminate each string with a '\0' character
         */
        for (i = 0, xlt = xlate_t; i < xlate_c; i++, xlt++) {
                KASSERTMSG((next - strp) == xlt->offset,
                    "entry %d at wrong offset %"PRIu32, i, xlt->offset);
                memcpy(next, xlt->addr, xlt->len);
                next += xlt->len;
                *next++ = '\0';
        }

        /* Copy data to userland */
        error = copyout(buf, oldp, uimin(bufsize, *oldlenp));

        /* If copyout was successful but only partial, report ENOMEM */
        if (error == 0 && *oldlenp < bufsize)
                error = SET_ERROR(ENOMEM);

        *oldlenp = bufsize;     /* inform userland of space requirements */

        /* Free up the stuff we allocated */
        kmem_free(buf, bufsize);
        kmem_free(xlate_t, xlate_s);

        return error;
}