xnu-1228.9.59.tar.gz

[apple/xnu.git] / bsd / kern / kern_credential.c

/*
 * Copyright (c) 2004-2007 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 * 
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */
/*
 * NOTICE: This file was modified by SPARTA, Inc. in 2005 to introduce
 * support for mandatory and extensible security protections.  This notice
 * is included in support of clause 2.2 (b) of the Apple Public License,
 * Version 2.0.
 */

/*
 * Kernel Authorization framework: Management of process/thread credentials
 * and identity information.
 */


#include <sys/param.h>  /* XXX trim includes */
#include <sys/acct.h>
#include <sys/systm.h>
#include <sys/ucred.h>
#include <sys/proc_internal.h>
#include <sys/user.h>
#include <sys/timeb.h>
#include <sys/times.h>
#include <sys/malloc.h>
#include <sys/kauth.h>
#include <sys/kernel.h>

#include <bsm/audit_kernel.h>

#include <sys/mount.h>
#include <sys/sysproto.h>
#include <mach/message.h>
#include <mach/host_security.h>

#include <libkern/OSAtomic.h>

#include <kern/task.h>
#include <kern/lock.h>
#ifdef MACH_ASSERT
# undef MACH_ASSERT
#endif
#define MACH_ASSERT 1   /* XXX so bogus */
#include <kern/assert.h>

#if CONFIG_MACF
#include <security/mac.h>
#include <security/mac_framework.h>
#endif

#define CRED_DIAGNOSTIC 0

# define NULLCRED_CHECK(_c)     do {if (!IS_VALID_CRED(_c)) panic("%s: bad credential %p", __FUNCTION__,_c);} while(0)

/*
 * Credential debugging; we can track entry into a function that might
 * change a credential, and we can track actual credential changes that
 * result.
 *
 * Note:        Does *NOT* currently include per-thread credential changes
 */

#if DEBUG_CRED
#define DEBUG_CRED_ENTER                printf
#define DEBUG_CRED_CHANGE               printf
extern void kauth_cred_print(kauth_cred_t cred);

#include <libkern/OSDebug.h>    /* needed for get_backtrace( ) */

int is_target_cred( kauth_cred_t the_cred );
void get_backtrace( void );

static int sysctl_dump_creds( __unused struct sysctl_oid *oidp, __unused void *arg1, 
                                                          __unused int arg2, struct sysctl_req *req );
static int
sysctl_dump_cred_backtraces( __unused struct sysctl_oid *oidp, __unused void *arg1, 
                                                         __unused int arg2, struct sysctl_req *req );

#define MAX_STACK_DEPTH 8
struct cred_backtrace {
        int                             depth;
        void *                  stack[ MAX_STACK_DEPTH ];
};
typedef struct cred_backtrace cred_backtrace;

#define MAX_CRED_BUFFER_SLOTS 200
struct cred_debug_buffer {
        int                             next_slot;
        cred_backtrace  stack_buffer[ MAX_CRED_BUFFER_SLOTS ];  
};
typedef struct cred_debug_buffer cred_debug_buffer;
cred_debug_buffer * cred_debug_buf_p = NULL;

#else   /* !DEBUG_CRED */

#define DEBUG_CRED_ENTER(fmt, ...)      do {} while (0)
#define DEBUG_CRED_CHANGE(fmt, ...)     do {} while (0)

#endif  /* !DEBUG_CRED */

/*
 * Interface to external identity resolver.
 *
 * The architecture of the interface is simple; the external resolver calls
 * in to get work, then calls back with completed work.  It also calls us
 * to let us know that it's (re)started, so that we can resubmit work if it
 * times out.
 */

static lck_mtx_t *kauth_resolver_mtx;
#define KAUTH_RESOLVER_LOCK()   lck_mtx_lock(kauth_resolver_mtx);
#define KAUTH_RESOLVER_UNLOCK() lck_mtx_unlock(kauth_resolver_mtx);

static volatile pid_t   kauth_resolver_identity;
static int      kauth_resolver_registered;
static uint32_t kauth_resolver_sequence;

struct kauth_resolver_work {
        TAILQ_ENTRY(kauth_resolver_work) kr_link;
        struct kauth_identity_extlookup kr_work;
        uint32_t        kr_seqno;
        int             kr_refs;
        int             kr_flags;
#define KAUTH_REQUEST_UNSUBMITTED       (1<<0)
#define KAUTH_REQUEST_SUBMITTED         (1<<1)
#define KAUTH_REQUEST_DONE              (1<<2)
        int             kr_result;
};

TAILQ_HEAD(kauth_resolver_unsubmitted_head, kauth_resolver_work) kauth_resolver_unsubmitted;
TAILQ_HEAD(kauth_resolver_submitted_head, kauth_resolver_work)  kauth_resolver_submitted;
TAILQ_HEAD(kauth_resolver_done_head, kauth_resolver_work)       kauth_resolver_done;

static int      kauth_resolver_submit(struct kauth_identity_extlookup *lkp);
static int      kauth_resolver_complete(user_addr_t message);
static int      kauth_resolver_getwork(user_addr_t message);
static int      kauth_resolver_getwork2(user_addr_t message);

static const int kauth_cred_primes[KAUTH_CRED_PRIMES_COUNT] = KAUTH_CRED_PRIMES;
static int      kauth_cred_primes_index = 0;
static int      kauth_cred_table_size = 0;

TAILQ_HEAD(kauth_cred_entry_head, ucred);
static struct kauth_cred_entry_head * kauth_cred_table_anchor = NULL;

#define KAUTH_CRED_HASH_DEBUG   0

static int kauth_cred_add(kauth_cred_t new_cred);
static void kauth_cred_remove(kauth_cred_t cred);
static inline u_long kauth_cred_hash(const uint8_t *datap, int data_len, u_long start_key);
static u_long kauth_cred_get_hashkey(kauth_cred_t cred);
static kauth_cred_t kauth_cred_update(kauth_cred_t old_cred, kauth_cred_t new_cred, boolean_t retain_auditinfo);
static void kauth_cred_unref_hashlocked(kauth_cred_t *credp);

#if KAUTH_CRED_HASH_DEBUG
static int      kauth_cred_count = 0;
static void kauth_cred_hash_print(void);
static void kauth_cred_print(kauth_cred_t cred);
#endif


/*
 * kauth_resolver_init
 *
 * Description: Initialize the daemon side of the credential identity resolver
 *
 * Parameters:  (void)
 *
 * Returns:     (void)
 *
 * Notes:       Intialize the credential identity resolver for use; the
 *              credential identity resolver is the KPI used by the user
 *              space credential identity resolver daemon to communicate
 *              with the kernel via the identitysvc() system call..
 *
 *              This is how membership in more than 16 groups (1 effective
 *              and 15 supplementary) is supported, and also how UID's,
 *              UUID's, and so on, are translated to/from POSIX credential
 *              values.
 *
 *              The credential identity resolver operates by attempting to
 *              determine identity first from the credential, then from
 *              the kernel credential identity cache, and finally by
 *              enqueueing a request to a user space daemon.
 *
 *              This function is called from kauth_init() in the file
 *              kern_authorization.c.
 */
void
kauth_resolver_init(void)
{
        TAILQ_INIT(&kauth_resolver_unsubmitted);
        TAILQ_INIT(&kauth_resolver_submitted);
        TAILQ_INIT(&kauth_resolver_done);
        kauth_resolver_sequence = 31337;
        kauth_resolver_mtx = lck_mtx_alloc_init(kauth_lck_grp, 0/*LCK_ATTR_NULL*/);
}


/*
 * kauth_resolver_submit
 *
 * Description: Submit an external credential identity resolution request to
 *              the user space daemon.
 *
 * Parameters:  lkp                             A pointer to an external
 *                                              lookup request
 *
 * Returns:     0                               Success
 *              EWOULDBLOCK                     No resolver registered
 *              EINTR                           Operation interrupted (e.g. by
 *                                              a signal)
 *              ENOMEM                          Could not allocate work item
 *              ???                             An error from the user space
 *                                              daemon
 *
 * Notes:       Allocate a work queue entry, submit the work and wait for
 *              the operation to either complete or time out.  Outstanding
 *              operations may also be cancelled.
 */
static int
kauth_resolver_submit(struct kauth_identity_extlookup *lkp)
{
        struct kauth_resolver_work *workp, *killp;
        struct timespec ts;
        int     error, shouldfree;
        
        /* no point actually blocking if the resolver isn't up yet */
        if (kauth_resolver_identity == 0) {
                /*
                 * We've already waited an initial 30 seconds with no result.
                 * Sleep on a stack address so no one wakes us before timeout;
                 * we sleep a half a second in case we are a high priority
                 * process, so that memberd doesn't starve while we are in a
                 * tight loop between user and kernel, eating all the CPU.
                 */
                error = tsleep(&ts, PZERO | PCATCH, "kr_submit", hz/2);
                if (kauth_resolver_identity == 0) {
                        /*
                         * if things haven't changed while we were asleep,
                         * tell the caller we couldn't get an authoritative
                         * answer.
                         */
                        return(EWOULDBLOCK);
                }
        }
                
        MALLOC(workp, struct kauth_resolver_work *, sizeof(*workp), M_KAUTH, M_WAITOK);
        if (workp == NULL)
                return(ENOMEM);

        workp->kr_work = *lkp;
        workp->kr_refs = 1;
        workp->kr_flags = KAUTH_REQUEST_UNSUBMITTED;
        workp->kr_result = 0;

        /*
         * We insert the request onto the unsubmitted queue, the call in from
         * the resolver will it to the submitted thread when appropriate.
         */
        KAUTH_RESOLVER_LOCK();
        workp->kr_seqno = workp->kr_work.el_seqno = kauth_resolver_sequence++;
        workp->kr_work.el_result = KAUTH_EXTLOOKUP_INPROG;

        /*
         * XXX As an optimisation, we could check the queue for identical
         * XXX items and coalesce them
         */
        TAILQ_INSERT_TAIL(&kauth_resolver_unsubmitted, workp, kr_link);

        wakeup_one((caddr_t)&kauth_resolver_unsubmitted);
        for (;;) {
                /* we could compute a better timeout here */
                ts.tv_sec = 30;
                ts.tv_nsec = 0;
                error = msleep(workp, kauth_resolver_mtx, PCATCH, "kr_submit", &ts);
                /* request has been completed? */
                if ((error == 0) && (workp->kr_flags & KAUTH_REQUEST_DONE))
                        break;
                /* woken because the resolver has died? */
                if (kauth_resolver_identity == 0) {
                        error = EIO;
                        break;
                }
                /* an error? */
                if (error != 0)
                        break;
        }
        /* if the request was processed, copy the result */
        if (error == 0)
                *lkp = workp->kr_work;
        
        /*
         * If the request timed out and was never collected, the resolver
         * is dead and probably not coming back anytime soon.  In this
         * case we revert to no-resolver behaviour, and punt all the other
         * sleeping requests to clear the backlog.
         */
        if ((error == EWOULDBLOCK) && (workp->kr_flags & KAUTH_REQUEST_UNSUBMITTED)) {
                KAUTH_DEBUG("RESOLVER - request timed out without being collected for processing, resolver dead");
                kauth_resolver_identity = 0;
                /* kill all the other requestes that are waiting as well */
                TAILQ_FOREACH(killp, &kauth_resolver_submitted, kr_link)
                    wakeup(killp);
                TAILQ_FOREACH(killp, &kauth_resolver_unsubmitted, kr_link)
                    wakeup(killp);
        }
        
        /*
         * drop our reference on the work item, and note whether we should
         * free it or not
         */
        if (--workp->kr_refs <= 0) {
                /* work out which list we have to remove it from */
                if (workp->kr_flags & KAUTH_REQUEST_DONE) {
                        TAILQ_REMOVE(&kauth_resolver_done, workp, kr_link);
                } else if (workp->kr_flags & KAUTH_REQUEST_SUBMITTED) {
                        TAILQ_REMOVE(&kauth_resolver_submitted, workp, kr_link);
                } else if (workp->kr_flags & KAUTH_REQUEST_UNSUBMITTED) {
                        TAILQ_REMOVE(&kauth_resolver_unsubmitted, workp, kr_link);
                } else {
                        KAUTH_DEBUG("RESOLVER - completed request has no valid queue");
                }
                shouldfree = 1;
        } else {
                /* someone else still has a reference on this request */
                shouldfree = 0;
        }
        /* collect request result */
        if (error == 0)
                error = workp->kr_result;
        KAUTH_RESOLVER_UNLOCK();
        /*
         * If we dropped the last reference, free the request.
         */
        if (shouldfree)
                FREE(workp, M_KAUTH);

        KAUTH_DEBUG("RESOLVER - returning %d", error);
        return(error);
}


/*
 * identitysvc
 *
 * Description: System call interface for the external identity resolver.
 *
 * Parameters:  uap->message                    Message from daemon to kernel
 *
 * Returns:     0                               Successfully became resolver
 *              EPERM                           Not the resolver process
 *      kauth_authorize_generic:EPERM           Not root user
 *      kauth_resolver_complete:EIO
 *      kauth_resolver_complete:EFAULT
 *      kauth_resolver_getwork:EINTR
 *      kauth_resolver_getwork:EFAULT
 *
 * Notes:       This system call blocks until there is work enqueued, at
 *              which time the kernel wakes it up, and a message from the
 *              kernel is copied out to the identity resolution daemon, which
 *              proceed to attempt to resolve it.  When the resolution has
 *              completed (successfully or not), the daemon called back into
 *              this system call to give the result to the kernel, and wait
 *              for the next request.
 */
int
identitysvc(__unused struct proc *p, struct identitysvc_args *uap, __unused register_t *retval)
{
        int opcode = uap->opcode;
        user_addr_t message = uap->message;
        struct kauth_resolver_work *workp;
        int error;
        pid_t new_id;

        /*
         * New server registering itself.
         */
        if (opcode == KAUTH_EXTLOOKUP_REGISTER) {
                new_id = current_proc()->p_pid;
                if ((error = kauth_authorize_generic(kauth_cred_get(), KAUTH_GENERIC_ISSUSER)) != 0) {
                        KAUTH_DEBUG("RESOLVER - pid %d refused permission to become identity resolver", new_id);
                        return(error);
                }
                KAUTH_RESOLVER_LOCK();
                if (kauth_resolver_identity != new_id) {
                        KAUTH_DEBUG("RESOLVER - new resolver %d taking over from old %d", new_id, kauth_resolver_identity);
                        /*
                         * We have a new server, so assume that all the old requests have been lost.
                         */
                        while ((workp = TAILQ_LAST(&kauth_resolver_submitted, kauth_resolver_submitted_head)) != NULL) {
                                TAILQ_REMOVE(&kauth_resolver_submitted, workp, kr_link);
                                workp->kr_flags &= ~KAUTH_REQUEST_SUBMITTED;
                                workp->kr_flags |= KAUTH_REQUEST_UNSUBMITTED;
                                TAILQ_INSERT_HEAD(&kauth_resolver_unsubmitted, workp, kr_link);
                        }
                        kauth_resolver_identity = new_id;
                        kauth_resolver_registered = 1;
                        wakeup(&kauth_resolver_unsubmitted);
                }
                KAUTH_RESOLVER_UNLOCK();
                return(0);
        }

        /*
         * Beyond this point, we must be the resolver process.
         */
        if (current_proc()->p_pid != kauth_resolver_identity) {
                KAUTH_DEBUG("RESOLVER - call from bogus resolver %d\n", current_proc()->p_pid);
                return(EPERM);
        }
        
        /*
         * Got a result returning?
         */
        if (opcode & KAUTH_EXTLOOKUP_RESULT) {
                if ((error = kauth_resolver_complete(message)) != 0)
                        return(error);
        }

        /*
         * Caller wants to take more work?
         */
        if (opcode & KAUTH_EXTLOOKUP_WORKER) {
                if ((error = kauth_resolver_getwork(message)) != 0)
                        return(error);
        }

        return(0);
}


/*
 * kauth_resolver_getwork_continue
 *              
 * Description: Continuation for kauth_resolver_getwork
 *
 * Parameters:  result                          Error code or 0 for the sleep
 *                                              that got us to this function
 *
 * Returns:     0                               Success
 *              EINTR                           Interrupted (e.g. by signal)
 *      kauth_resolver_getwork2:EFAULT
 *
 * Notes:       See kauth_resolver_getwork(0 and kauth_resolver_getwork2() for
 *              more information.
 */
static int
kauth_resolver_getwork_continue(int result)
{
        thread_t thread;
        struct uthread *ut;
        user_addr_t message;

        if (result) {
                KAUTH_RESOLVER_UNLOCK();
                return(result);
        }

        /*
         * If we lost a race with another thread/memberd restarting, then we
         * need to go back to sleep to look for more work.  If it was memberd
         * restarting, then the msleep0() will error out here, as our thread
         * will already be "dead".
         */
        if (TAILQ_FIRST(&kauth_resolver_unsubmitted) == NULL) {
                int error;

                error = msleep0(&kauth_resolver_unsubmitted, kauth_resolver_mtx, PCATCH, "GRGetWork", 0, kauth_resolver_getwork_continue);
                KAUTH_RESOLVER_UNLOCK();
                return(error);
        }

        thread = current_thread();
        ut = get_bsdthread_info(thread);
        message = ut->uu_kauth.message;
        return(kauth_resolver_getwork2(message));
}


/*
 * kauth_resolver_getwork2
 *
 * Decription:  Common utility function to copy out a identity resolver work
 *              item from the kernel to user space as part of the user space
 *              identity resolver requesting work.
 *
 * Parameters:  message                         message to user space
 *
 * Returns:     0                               Success
 *              EFAULT                          Bad user space message address
 *
 * Notes:       This common function exists to permit the use of continuations
 *              in the identity resoultion process.  This frees up the stack
 *              while we are waiting for the user space resolver to complete
 *              a request.  This is specifically used so that our per thread
 *              cost can be small, and we will therefore be willing to run a
 *              larger number of threads in the user space identity resolver.
 */
static int
kauth_resolver_getwork2(user_addr_t message)
{
        struct kauth_resolver_work *workp;
        int             error;

        /*
         * Note: We depend on the caller protecting us from a NULL work item
         * queue, since we must have the kauth resolver lock on entry to this
         * function.
         */
        workp = TAILQ_FIRST(&kauth_resolver_unsubmitted);

        if ((error = copyout(&workp->kr_work, message, sizeof(workp->kr_work))) != 0) {
                KAUTH_DEBUG("RESOLVER - error submitting work to resolve");
                goto out;
        }
        TAILQ_REMOVE(&kauth_resolver_unsubmitted, workp, kr_link);
        workp->kr_flags &= ~KAUTH_REQUEST_UNSUBMITTED;
        workp->kr_flags |= KAUTH_REQUEST_SUBMITTED;
        TAILQ_INSERT_TAIL(&kauth_resolver_submitted, workp, kr_link);

out:
        KAUTH_RESOLVER_UNLOCK();
        return(error);
}


/*
 * kauth_resolver_getwork
 *
 * Description: Get a work item from the enqueued requests from the kernel and
 *              give it to the user space daemon.
 *
 * Parameters:  message                         message to user space
 *
 * Returns:     0                               Success
 *              EINTR                           Interrupted (e.g. by signal)
 *      kauth_resolver_getwork2:EFAULT
 *
 * Notes:       This function blocks in a continuation if there are no work
 *              items available for processing at the time the user space
 *              identity resolution daemon makes a request for work.  This
 *              permits a large number of threads to be used by the daemon,
 *              without using a lot of wired kernel memory when there are no
 *              acctual request outstanding.
 */
static int
kauth_resolver_getwork(user_addr_t message)
{
        struct kauth_resolver_work *workp;
        int             error;

        KAUTH_RESOLVER_LOCK();
        error = 0;
        while ((workp = TAILQ_FIRST(&kauth_resolver_unsubmitted)) == NULL) {
                thread_t thread = current_thread();
                struct uthread *ut = get_bsdthread_info(thread);

                ut->uu_kauth.message = message;
                error = msleep0(&kauth_resolver_unsubmitted, kauth_resolver_mtx, PCATCH, "GRGetWork", 0, kauth_resolver_getwork_continue);
                KAUTH_RESOLVER_UNLOCK();
                return(error);
        }
        return kauth_resolver_getwork2(message);
}


/*
 * kauth_resolver_complete
 *
 * Description: Return a result from userspace.
 *
 * Parameters:  message                         message from user space
 *
 * Returns:     0                               Success
 *              EIO                             The resolver is dead
 *      copyin:EFAULT                           Bad message from user space
 */
static int
kauth_resolver_complete(user_addr_t message)
{
        struct kauth_identity_extlookup extl;
        struct kauth_resolver_work *workp;
        int error, result;

        if ((error = copyin(message, &extl, sizeof(extl))) != 0) {
                KAUTH_DEBUG("RESOLVER - error getting completed work\n");
                return(error);
        }

        KAUTH_RESOLVER_LOCK();

        error = 0;
        result = 0;
        switch (extl.el_result) {
        case KAUTH_EXTLOOKUP_INPROG:
        {
                static int once = 0;

                /* XXX this should go away once memberd is updated */
                if (!once) {
                        printf("kauth_resolver: memberd is not setting valid result codes (assuming always successful)\n");
                        once = 1;
                }
        }
        /* FALLTHROUGH */
        case KAUTH_EXTLOOKUP_SUCCESS:
                break;

        case KAUTH_EXTLOOKUP_FATAL:
                /* fatal error means the resolver is dead */
                KAUTH_DEBUG("RESOLVER - resolver %d died, waiting for a new one", kauth_resolver_identity);
                kauth_resolver_identity = 0;
                /* XXX should we terminate all outstanding requests? */
                error = EIO;
                break;
        case KAUTH_EXTLOOKUP_BADRQ:
                KAUTH_DEBUG("RESOLVER - resolver reported invalid request %d", extl.el_seqno);
                result = EINVAL;
                break;
        case KAUTH_EXTLOOKUP_FAILURE:
                KAUTH_DEBUG("RESOLVER - resolver reported transient failure for request %d", extl.el_seqno);
                result = EIO;
                break;
        default:
                KAUTH_DEBUG("RESOLVER - resolver returned unexpected status %d", extl.el_result);
                result = EIO;
                break;
        }

        /*
         * In the case of a fatal error, we assume that the resolver will restart
         * quickly and re-collect all of the outstanding requests.  Thus, we don't
         * complete the request which returned the fatal error status.
         */
        if (extl.el_result != KAUTH_EXTLOOKUP_FATAL) {
                /* scan our list for this request */
                TAILQ_FOREACH(workp, &kauth_resolver_submitted, kr_link) {
                        /* found it? */
                        if (workp->kr_seqno == extl.el_seqno) {
                                /* copy result */
                                workp->kr_work = extl;
                                /* move onto completed list and wake up requester(s) */
                                TAILQ_REMOVE(&kauth_resolver_submitted, workp, kr_link);
                                workp->kr_flags &= ~KAUTH_REQUEST_SUBMITTED;
                                workp->kr_flags |= KAUTH_REQUEST_DONE;
                                workp->kr_result = result;
                                TAILQ_INSERT_TAIL(&kauth_resolver_done, workp, kr_link);
                                wakeup(workp);
                                break;
                        }
                }
        }
        /*
         * Note that it's OK for us not to find anything; if the request has
         * timed out the work record will be gone.
         */
        KAUTH_RESOLVER_UNLOCK();
        
        return(error);
}


/*
 * Identity cache.
 */

struct kauth_identity {
        TAILQ_ENTRY(kauth_identity) ki_link;
        int     ki_valid;
#define KI_VALID_UID    (1<<0)          /* UID and GID are mutually exclusive */
#define KI_VALID_GID    (1<<1)
#define KI_VALID_GUID   (1<<2)
#define KI_VALID_NTSID  (1<<3)
        uid_t   ki_uid;
        gid_t   ki_gid;
        guid_t  ki_guid;
        ntsid_t ki_ntsid;
        /*
         * Expiry times are the earliest time at which we will disregard the cached state and go to
         * userland.  Before then if the valid bit is set, we will return the cached value.  If it's
         * not set, we will not go to userland to resolve, just assume that there is no answer
         * available.
         */
        time_t  ki_guid_expiry;
        time_t  ki_ntsid_expiry;
};

static TAILQ_HEAD(kauth_identity_head, kauth_identity) kauth_identities;
#define KAUTH_IDENTITY_CACHEMAX         100     /* XXX sizing? */
static int kauth_identity_count;

static lck_mtx_t *kauth_identity_mtx;
#define KAUTH_IDENTITY_LOCK()   lck_mtx_lock(kauth_identity_mtx);
#define KAUTH_IDENTITY_UNLOCK() lck_mtx_unlock(kauth_identity_mtx);


static struct kauth_identity *kauth_identity_alloc(uid_t uid, gid_t gid, guid_t *guidp, time_t guid_expiry,
    ntsid_t *ntsidp, time_t ntsid_expiry);
static void     kauth_identity_register_and_free(struct kauth_identity *kip);
static void     kauth_identity_updatecache(struct kauth_identity_extlookup *elp, struct kauth_identity *kip);
static void     kauth_identity_lru(struct kauth_identity *kip);
static int      kauth_identity_guid_expired(struct kauth_identity *kip);
static int      kauth_identity_ntsid_expired(struct kauth_identity *kip);
static int      kauth_identity_find_uid(uid_t uid, struct kauth_identity *kir);
static int      kauth_identity_find_gid(gid_t gid, struct kauth_identity *kir);
static int      kauth_identity_find_guid(guid_t *guidp, struct kauth_identity *kir);
static int      kauth_identity_find_ntsid(ntsid_t *ntsid, struct kauth_identity *kir);


/*
 * kauth_identity_init
 *
 * Description: Initialize the kernel side of the credential identity resolver
 *
 * Parameters:  (void)
 *
 * Returns:     (void)
 *
 * Notes:       Intialize the credential identity resolver for use; the
 *              credential identity resolver is the KPI used to communicate
 *              with a user space credential identity resolver daemon.
 *
 *              This function is called from kauth_init() in the file
 *              kern_authorization.c.
 */
void
kauth_identity_init(void)
{
        TAILQ_INIT(&kauth_identities);
        kauth_identity_mtx = lck_mtx_alloc_init(kauth_lck_grp, 0/*LCK_ATTR_NULL*/);
}


/*
 * kauth_identity_alloc
 *
 * Description: Allocate and fill out a kauth_identity structure for
 *              translation between {UID|GID}/GUID/NTSID
 *
 * Parameters:  uid
 *
 * Returns:     NULL                            Insufficient memory to satisfy
 *                                              the request
 *              !NULL                           A pointer to the applocated
 *                                              structure, filled in
 *
 * Notes:       It is illegal to translate between UID and GID; any given UUID
 *              or NTSID can oly refer to an NTSIDE or UUID (respectively),
 *              and *either* a UID *or* a GID, but not both.
 */
static struct kauth_identity *
kauth_identity_alloc(uid_t uid, gid_t gid, guid_t *guidp, time_t guid_expiry, ntsid_t *ntsidp, time_t ntsid_expiry)
{
        struct kauth_identity *kip;
        
        /* get and fill in a new identity */
        MALLOC(kip, struct kauth_identity *, sizeof(*kip), M_KAUTH, M_WAITOK | M_ZERO);
        if (kip != NULL) {
                if (gid != KAUTH_GID_NONE) {
                        kip->ki_gid = gid;
                        kip->ki_valid = KI_VALID_GID;
                }
                if (uid != KAUTH_UID_NONE) {
                        if (kip->ki_valid & KI_VALID_GID)
                                panic("can't allocate kauth identity with both uid and gid");
                        kip->ki_uid = uid;
                        kip->ki_valid = KI_VALID_UID;
                }
                if (guidp != NULL) {
                        kip->ki_guid = *guidp;
                        kip->ki_valid |= KI_VALID_GUID;
                }
                kip->ki_guid_expiry = guid_expiry;
                if (ntsidp != NULL) {
                        kip->ki_ntsid = *ntsidp;
                        kip->ki_valid |= KI_VALID_NTSID;
                }
                kip->ki_ntsid_expiry = ntsid_expiry;
        }
        return(kip);
}


/*
 * kauth_identity_register_and_free
 *
 * Description: Register an association between identity tokens.  The passed
 *              'kip' is freed by this function.
 *
 * Parameters:  kip                             Pointer to kauth_identity
 *                                              structure to register
 *
 * Returns:     (void)
 *
 * Notes:       The memory pointer to by 'kip' is assumed to have been
 *              previously allocated via kauth_identity_alloc().
 */
static void
kauth_identity_register_and_free(struct kauth_identity *kip)
{
        struct kauth_identity *ip;

        /*
         * We search the cache for the UID listed in the incoming association.
         * If we already have an entry, the new information is merged.
         */
        ip = NULL;
        KAUTH_IDENTITY_LOCK();
        if (kip->ki_valid & KI_VALID_UID) {
                if (kip->ki_valid & KI_VALID_GID)
                        panic("kauth_identity: can't insert record with both UID and GID as key");
                TAILQ_FOREACH(ip, &kauth_identities, ki_link)
                    if ((ip->ki_valid & KI_VALID_UID) && (ip->ki_uid == kip->ki_uid))
                                break;
        } else if (kip->ki_valid & KI_VALID_GID) {
                TAILQ_FOREACH(ip, &kauth_identities, ki_link)
                    if ((ip->ki_valid & KI_VALID_GID) && (ip->ki_gid == kip->ki_gid))
                                break;
        } else {
                panic("kauth_identity: can't insert record without UID or GID as key");
        }
                
        if (ip != NULL) {
                /* we already have an entry, merge/overwrite */
                if (kip->ki_valid & KI_VALID_GUID) {
                        ip->ki_guid = kip->ki_guid;
                        ip->ki_valid |= KI_VALID_GUID;
                }
                ip->ki_guid_expiry = kip->ki_guid_expiry;
                if (kip->ki_valid & KI_VALID_NTSID) {
                        ip->ki_ntsid = kip->ki_ntsid;
                        ip->ki_valid |= KI_VALID_NTSID;
                }
                ip->ki_ntsid_expiry = kip->ki_ntsid_expiry;
                /* and discard the incoming identity */
                FREE(kip, M_KAUTH);
                ip = NULL;
        } else {
                /* don't have any information on this identity, so just add it */
                TAILQ_INSERT_HEAD(&kauth_identities, kip, ki_link);
                if (++kauth_identity_count > KAUTH_IDENTITY_CACHEMAX) {
                        ip = TAILQ_LAST(&kauth_identities, kauth_identity_head);
                        TAILQ_REMOVE(&kauth_identities, ip, ki_link);
                        kauth_identity_count--;
                }
        }
        KAUTH_IDENTITY_UNLOCK();
        /* have to drop lock before freeing expired entry */
        if (ip != NULL)
                FREE(ip, M_KAUTH);
}


/*
 * kauth_identity_updatecache
 *
 * Description: Given a lookup result, add any associations that we don't
 *              currently have.
 *
 * Parameters:  elp                             External lookup result from
 *                                              user space daemon to kernel
 *              rkip                            pointer to returned kauth
 *                                              identity, or NULL
 *
 * Returns:     (void)
 *
 * Implicit returns:
 *              *rkip                           Modified (if non-NULL)
 */
static void
kauth_identity_updatecache(struct kauth_identity_extlookup *elp, struct kauth_identity *rkip)
{
        struct timeval tv;
        struct kauth_identity *kip;

        microuptime(&tv);
        
        /* user identity? */
        if (elp->el_flags & KAUTH_EXTLOOKUP_VALID_UID) {
                KAUTH_IDENTITY_LOCK();
                TAILQ_FOREACH(kip, &kauth_identities, ki_link) {
                        /* matching record */
                        if ((kip->ki_valid & KI_VALID_UID) && (kip->ki_uid == elp->el_uid)) {
                                if (elp->el_flags & KAUTH_EXTLOOKUP_VALID_UGUID) {
                                        kip->ki_guid = elp->el_uguid;
                                        kip->ki_valid |= KI_VALID_GUID;
                                }
                                kip->ki_guid_expiry = tv.tv_sec + elp->el_uguid_valid;
                                if (elp->el_flags & KAUTH_EXTLOOKUP_VALID_USID) {
                                        kip->ki_ntsid = elp->el_usid;
                                        kip->ki_valid |= KI_VALID_NTSID;
                                }
                                kip->ki_ntsid_expiry = tv.tv_sec + elp->el_usid_valid;
                                kauth_identity_lru(kip);
                                if (rkip != NULL)
                                        *rkip = *kip;
                                KAUTH_DEBUG("CACHE - refreshed %d is " K_UUID_FMT, kip->ki_uid, K_UUID_ARG(kip->ki_guid));
                                break;
                        }
                }
                KAUTH_IDENTITY_UNLOCK();
                /* not found in cache, add new record */
                if (kip == NULL) {
                        kip = kauth_identity_alloc(elp->el_uid, KAUTH_GID_NONE,
                            (elp->el_flags & KAUTH_EXTLOOKUP_VALID_UGUID) ? &elp->el_uguid : NULL,
                            tv.tv_sec + elp->el_uguid_valid,
                            (elp->el_flags & KAUTH_EXTLOOKUP_VALID_USID) ? &elp->el_usid : NULL,
                            tv.tv_sec + elp->el_usid_valid);
                        if (kip != NULL) {
                                if (rkip != NULL)
                                        *rkip = *kip;
                                KAUTH_DEBUG("CACHE - learned %d is " K_UUID_FMT, kip->ki_uid, K_UUID_ARG(kip->ki_guid));
                                kauth_identity_register_and_free(kip);
                        }
                }
        }

        /* group identity? */
        if (elp->el_flags & KAUTH_EXTLOOKUP_VALID_GID) {
                KAUTH_IDENTITY_LOCK();
                TAILQ_FOREACH(kip, &kauth_identities, ki_link) {
                        /* matching record */
                        if ((kip->ki_valid & KI_VALID_GID) && (kip->ki_gid == elp->el_gid)) {
                                if (elp->el_flags & KAUTH_EXTLOOKUP_VALID_GGUID) {
                                        kip->ki_guid = elp->el_gguid;
                                        kip->ki_valid |= KI_VALID_GUID;
                                }
                                kip->ki_guid_expiry = tv.tv_sec + elp->el_gguid_valid;
                                if (elp->el_flags & KAUTH_EXTLOOKUP_VALID_GSID) {
                                        kip->ki_ntsid = elp->el_gsid;
                                        kip->ki_valid |= KI_VALID_NTSID;
                                }
                                kip->ki_ntsid_expiry = tv.tv_sec + elp->el_gsid_valid;
                                kauth_identity_lru(kip);
                                if (rkip != NULL)
                                        *rkip = *kip;
                                KAUTH_DEBUG("CACHE - refreshed %d is " K_UUID_FMT, kip->ki_uid, K_UUID_ARG(kip->ki_guid));
                                break;
                        }
                }
                KAUTH_IDENTITY_UNLOCK();
                /* not found in cache, add new record */
                if (kip == NULL) {
                        kip = kauth_identity_alloc(KAUTH_UID_NONE, elp->el_gid,
                            (elp->el_flags & KAUTH_EXTLOOKUP_VALID_GGUID) ? &elp->el_gguid : NULL,
                            tv.tv_sec + elp->el_gguid_valid,
                            (elp->el_flags & KAUTH_EXTLOOKUP_VALID_GSID) ? &elp->el_gsid : NULL,
                            tv.tv_sec + elp->el_gsid_valid);
                        if (kip != NULL) {
                                if (rkip != NULL)
                                        *rkip = *kip;
                                KAUTH_DEBUG("CACHE - learned %d is " K_UUID_FMT, kip->ki_uid, K_UUID_ARG(kip->ki_guid));
                                kauth_identity_register_and_free(kip);
                        }
                }
        }

}


/*
 * kauth_identity_lru
 *
 * Description: Promote the entry to the head of the LRU, assumes the cache
 *              is locked.
 *
 * Parameters:  kip                             kauth identity to move to the
 *                                              head of the LRU list, if it's
 *                                              not already there
 *
 * Returns:     (void)
 *
 * Notes:       This is called even if the entry has expired; typically an
 *              expired entry that's been looked up is about to be revalidated,
 *              and having it closer to the head of the LRU means finding it
 *              quickly again when the revalidation comes through.
 */
static void
kauth_identity_lru(struct kauth_identity *kip)
{
        if (kip != TAILQ_FIRST(&kauth_identities)) {
                TAILQ_REMOVE(&kauth_identities, kip, ki_link);
                TAILQ_INSERT_HEAD(&kauth_identities, kip, ki_link);
        }
}


/*
 * kauth_identity_guid_expired
 *
 * Description: Handle lazy expiration of GUID translations.
 *
 * Parameters:  kip                             kauth identity to check for
 *                                              GUID expiration
 *
 * Returns:     1                               Expired
 *              0                               Not expired
 */
static int
kauth_identity_guid_expired(struct kauth_identity *kip)
{
        struct timeval tv;

        microuptime(&tv);
        KAUTH_DEBUG("CACHE - GUID expires @ %d now %d", kip->ki_guid_expiry, tv.tv_sec);
        return((kip->ki_guid_expiry <= tv.tv_sec) ? 1 : 0);
}


/*
 * kauth_identity_ntsid_expired
 *
 * Description: Handle lazy expiration of NTSID translations.
 *
 * Parameters:  kip                             kauth identity to check for
 *                                              NTSID expiration
 *
 * Returns:     1                               Expired
 *              0                               Not expired
 */
static int
kauth_identity_ntsid_expired(struct kauth_identity *kip)
{
        struct timeval tv;

        microuptime(&tv);
        KAUTH_DEBUG("CACHE - NTSID expires @ %d now %d", kip->ki_ntsid_expiry, tv.tv_sec);
        return((kip->ki_ntsid_expiry <= tv.tv_sec) ? 1 : 0);
}


/*
 * kauth_identity_find_uid
 *
 * Description: Search for an entry by UID
 *
 * Parameters:  uid                             UID to find
 *              kir                             Pointer to return area
 *
 * Returns:     0                               Found
 *              ENOENT                          Not found
 *
 * Implicit returns:
 *              *klr                            Modified, if found
 */
static int
kauth_identity_find_uid(uid_t uid, struct kauth_identity *kir)
{
        struct kauth_identity *kip;

        KAUTH_IDENTITY_LOCK();
        TAILQ_FOREACH(kip, &kauth_identities, ki_link) {
                if ((kip->ki_valid & KI_VALID_UID) && (uid == kip->ki_uid)) {
                        kauth_identity_lru(kip);
                        /* Copy via structure assignment */
                        *kir = *kip;
                        break;
                }
        }
        KAUTH_IDENTITY_UNLOCK();
        return((kip == NULL) ? ENOENT : 0);
}


/*
 * kauth_identity_find_uid
 *
 * Description: Search for an entry by GID
 *
 * Parameters:  gid                             GID to find
 *              kir                             Pointer to return area
 *
 * Returns:     0                               Found
 *              ENOENT                          Not found
 *
 * Implicit returns:
 *              *klr                            Modified, if found
 */
static int
kauth_identity_find_gid(uid_t gid, struct kauth_identity *kir)
{
        struct kauth_identity *kip;

        KAUTH_IDENTITY_LOCK();
        TAILQ_FOREACH(kip, &kauth_identities, ki_link) {
                if ((kip->ki_valid & KI_VALID_GID) && (gid == kip->ki_gid)) {
                        kauth_identity_lru(kip);
                        /* Copy via structure assignment */
                        *kir = *kip;
                        break;
                }
        }
        KAUTH_IDENTITY_UNLOCK();
        return((kip == NULL) ? ENOENT : 0);
}


/*
 * kauth_identity_find_guid
 *
 * Description: Search for an entry by GUID
 *
 * Parameters:  guidp                           Pointer to GUID to find
 *              kir                             Pointer to return area
 *
 * Returns:     0                               Found
 *              ENOENT                          Not found
 *
 * Implicit returns:
 *              *klr                            Modified, if found
 *
 * Note:        The association may be expired, in which case the caller
 *              may elect to call out to userland to revalidate.
 */
static int
kauth_identity_find_guid(guid_t *guidp, struct kauth_identity *kir)
{
        struct kauth_identity *kip;

        KAUTH_IDENTITY_LOCK();
        TAILQ_FOREACH(kip, &kauth_identities, ki_link) {
                if ((kip->ki_valid & KI_VALID_GUID) && (kauth_guid_equal(guidp, &kip->ki_guid))) {
                        kauth_identity_lru(kip);
                        /* Copy via structure assignment */
                        *kir = *kip;
                        break;
                }
        }
        KAUTH_IDENTITY_UNLOCK();
        return((kip == NULL) ? ENOENT : 0);
}


/*
 * kauth_identity_find_ntsid
 *
 * Description: Search for an entry by NTSID
 *
 * Parameters:  ntsid                           Pointer to NTSID to find
 *              kir                             Pointer to return area
 *
 * Returns:     0                               Found
 *              ENOENT                          Not found
 *
 * Implicit returns:
 *              *klr                            Modified, if found
 *
 * Note:        The association may be expired, in which case the caller
 *              may elect to call out to userland to revalidate.
 */
static int
kauth_identity_find_ntsid(ntsid_t *ntsid, struct kauth_identity *kir)
{
        struct kauth_identity *kip;

        KAUTH_IDENTITY_LOCK();
        TAILQ_FOREACH(kip, &kauth_identities, ki_link) {
                if ((kip->ki_valid & KI_VALID_NTSID) && (kauth_ntsid_equal(ntsid, &kip->ki_ntsid))) {
                        kauth_identity_lru(kip);
                        /* Copy via structure assignment */
                        *kir = *kip;
                        break;
                }
        }
        KAUTH_IDENTITY_UNLOCK();
        return((kip == NULL) ? ENOENT : 0);
}


/*
 * GUID handling.
 */
guid_t kauth_null_guid;


/*
 * kauth_guid_equal
 *
 * Description: Determine the equality of two GUIDs
 *
 * Parameters:  guid1                           Pointer to first GUID
 *              guid2                           Pointer to second GUID
 *
 * Returns:     0                               If GUIDs are inequal
 *              !0                              If GUIDs are equal
 */
int
kauth_guid_equal(guid_t *guid1, guid_t *guid2)
{
        return(bcmp(guid1, guid2, sizeof(*guid1)) == 0);
}


/*
 * kauth_wellknown_guid
 *
 * Description: Determine if a GUID is a well-known GUID
 *
 * Parameters:  guid                            Pointer to GUID to check
 *
 * Returns:     KAUTH_WKG_NOT                   Not a wel known GUID
 *              KAUTH_WKG_EVERYBODY             "Everybody"
 *              KAUTH_WKG_NOBODY                "Nobody"
 *              KAUTH_WKG_OWNER                 "Other"
 *              KAUTH_WKG_GROUP                 "Group"
 */
int
kauth_wellknown_guid(guid_t *guid)
{
        static char     fingerprint[] = {0xab, 0xcd, 0xef, 0xab, 0xcd, 0xef, 0xab, 0xcd, 0xef, 0xab, 0xcd, 0xef};
        int             code;
        /*
         * All WKGs begin with the same 12 bytes.
         */
        if (bcmp((void *)guid, fingerprint, 12) == 0) {
                /*
                 * The final 4 bytes are our code (in network byte order).
                 */
                code = OSSwapHostToBigInt32(*(u_int32_t *)&guid->g_guid[12]);
                switch(code) {
                case 0x0000000c:
                        return(KAUTH_WKG_EVERYBODY);
                case 0xfffffffe:
                        return(KAUTH_WKG_NOBODY);
                case 0x0000000a:
                        return(KAUTH_WKG_OWNER);
                case 0x00000010:
                        return(KAUTH_WKG_GROUP);
                }
        }
        return(KAUTH_WKG_NOT);
}


/*
 * kauth_ntsid_equal
 *
 * Description: Determine the equality of two NTSIDs (NT Security Identifiers) 
 *
 * Paramters:   sid1                            Pointer to first NTSID
 *              sid2                            Pointer to second NTSID
 *
 * Returns:     0                               If GUIDs are inequal
 *              !0                              If GUIDs are equal
 */
int
kauth_ntsid_equal(ntsid_t *sid1, ntsid_t *sid2)
{
        /* check sizes for equality, also sanity-check size while we're at it */
        if ((KAUTH_NTSID_SIZE(sid1) == KAUTH_NTSID_SIZE(sid2)) &&
            (KAUTH_NTSID_SIZE(sid1) <= sizeof(*sid1)) &&
            bcmp(sid1, sid2, KAUTH_NTSID_SIZE(sid1)) == 0)
                return(1);
        return(0);
}


/*
 * Identity KPI
 *
 * We support four tokens representing identity:
 *  - Credential reference
 *  - UID
 *  - GUID
 *  - NT security identifier
 *
 * Of these, the UID is the ubiquitous identifier; cross-referencing should
 * be done using it.
 */

static int      kauth_cred_cache_lookup(int from, int to, void *src, void *dst);


/*
 * kauth_cred_change_egid
 *
 * Description: Set EGID by changing the first element of cr_groups for the
 *              passed credential; if the new EGID exists in the list of
 *              groups already, then rotate the old EGID into its position,
 *              otherwise replace it
 *
 * Parameters:  cred                    Pointer to the credential to modify
 *              new_egid                The new EGID to set
 *
 * Returns:     0                       The egid did not displace a member of
 *                                      the supplementary group list
 *              1                       The egid being set displaced a member
 *                                      of the supplementary groups list
 *
 * Note:        Utility function; internal use only because of locking.
 *
 *              This function operates on the credential passed; the caller
 *              must operate either on a newly allocated credential (one for
 *              which there is no hash cache reference and no externally
 *              visible pointer reference), or a template credential.
 */
static int
kauth_cred_change_egid(kauth_cred_t cred, gid_t new_egid)
{
        int     i;
        int     displaced = 1;
#if radar_4600026
        int     is_member;
#endif  /* radar_4600026 */
        gid_t   old_egid = cred->cr_groups[0];

        /* Ignoring the first entry, scan for a match for the new egid */
        for (i = 1; i < cred->cr_ngroups; i++) {
                /*
                 * If we find a match, swap them so we don't lose overall
                 * group information
                 */
                if (cred->cr_groups[i] == new_egid) {
                        cred->cr_groups[i] = old_egid;
                        DEBUG_CRED_CHANGE("kauth_cred_change_egid: unset displaced\n");
                        displaced = 0;
                        break;
                }
        }

#if radar_4600026
#error Fix radar 4600026 first!!!

/*
This is correct for memberd behaviour, but incorrect for POSIX; to address
this, we would need to automatically opt-out any SUID/SGID binary, and force
it to use initgroups to opt back in.  We take the approach of considering it
opt'ed out in any group of 16 displacement instead, since it's a much more
conservative approach (i.e. less likely to cause things to break).
*/

        /*
         * If we displaced a member of the supplementary groups list of the
         * credential, and we have not opted out of memberd, then if memberd
         * says that the credential is a member of the group, then it has not
         * actually been displaced.
         *
         * NB:  This is typically a cold code path.
         */
        if (displaced && !(cred->cr_flags & CRF_NOMEMBERD) &&
            kauth_cred_ismember_gid(cred, new_egid, &is_member) == 0 &&
            is_member) {
                displaced = 0;
                DEBUG_CRED_CHANGE("kauth_cred_change_egid: reset displaced\n");
        }
#endif  /* radar_4600026 */

        /* set the new EGID into the old spot */
        cred->cr_groups[0] = new_egid;

        return (displaced);
}


/*
 * kauth_cred_getuid
 *
 * Description: Fetch UID from credential
 *
 * Parameters:  cred                            Credential to examine
 *
 * Returns:     (uid_t)                         UID associated with credential
 */
uid_t
kauth_cred_getuid(kauth_cred_t cred)
{
        NULLCRED_CHECK(cred);
        return(cred->cr_uid);
}


/*
 * kauth_cred_getgid
 *
 * Description: Fetch GID from credential
 *
 * Parameters:  cred                            Credential to examine
 *
 * Returns:     (gid_t)                         GID associated with credential
 */
uid_t
kauth_cred_getgid(kauth_cred_t cred)
{
        NULLCRED_CHECK(cred);
        return(cred->cr_gid);
}


/*
 * kauth_cred_guid2uid
 *
 * Description: Fetch UID from GUID
 *
 * Parameters:  guidp                           Pointer to GUID to examine
 *              uidp                            Pointer to buffer for UID
 *
 * Returns:     0                               Success
 *      kauth_cred_cache_lookup:EINVAL
 *
 * Implicit returns:
 *              *uidp                           Modified, if successful
 */
int
kauth_cred_guid2uid(guid_t *guidp, uid_t *uidp)
{
        return(kauth_cred_cache_lookup(KI_VALID_GUID, KI_VALID_UID, guidp, uidp));
}


/*
 * kauth_cred_guid2gid
 *
 * Description: Fetch GID from GUID
 *
 * Parameters:  guidp                           Pointer to GUID to examine
 *              gidp                            Pointer to buffer for GID
 *
 * Returns:     0                               Success
 *      kauth_cred_cache_lookup:EINVAL
 *
 * Implicit returns:
 *              *gidp                           Modified, if successful
 */
int
kauth_cred_guid2gid(guid_t *guidp, gid_t *gidp)
{
        return(kauth_cred_cache_lookup(KI_VALID_GUID, KI_VALID_GID, guidp, gidp));
}


/*
 * kauth_cred_ntsid2uid
 *
 * Description: Fetch UID from NTSID
 *
 * Parameters:  sidp                            Pointer to NTSID to examine
 *              uidp                            Pointer to buffer for UID
 *
 * Returns:     0                               Success
 *      kauth_cred_cache_lookup:EINVAL
 *
 * Implicit returns:
 *              *uidp                           Modified, if successful
 */
int
kauth_cred_ntsid2uid(ntsid_t *sidp, uid_t *uidp)
{
        return(kauth_cred_cache_lookup(KI_VALID_NTSID, KI_VALID_UID, sidp, uidp));
}


/*
 * kauth_cred_ntsid2gid
 *
 * Description: Fetch GID from NTSID
 *
 * Parameters:  sidp                            Pointer to NTSID to examine
 *              gidp                            Pointer to buffer for GID
 *
 * Returns:     0                               Success
 *      kauth_cred_cache_lookup:EINVAL
 *
 * Implicit returns:
 *              *gidp                           Modified, if successful
 */
int
kauth_cred_ntsid2gid(ntsid_t *sidp, gid_t *gidp)
{
        return(kauth_cred_cache_lookup(KI_VALID_NTSID, KI_VALID_GID, sidp, gidp));
}


/*
 * kauth_cred_ntsid2guid
 *
 * Description: Fetch GUID from NTSID
 *
 * Parameters:  sidp                            Pointer to NTSID to examine
 *              guidp                           Pointer to buffer for GUID
 *
 * Returns:     0                               Success
 *      kauth_cred_cache_lookup:EINVAL
 *
 * Implicit returns:
 *              *guidp                          Modified, if successful
 */
int
kauth_cred_ntsid2guid(ntsid_t *sidp, guid_t *guidp)
{
        return(kauth_cred_cache_lookup(KI_VALID_NTSID, KI_VALID_GUID, sidp, guidp));
}


/*
 * kauth_cred_uid2guid
 *
 * Description: Fetch GUID from UID
 *
 * Parameters:  uid                             UID to examine
 *              guidp                           Pointer to buffer for GUID
 *
 * Returns:     0                               Success
 *      kauth_cred_cache_lookup:EINVAL
 *
 * Implicit returns:
 *              *guidp                          Modified, if successful
 */
int
kauth_cred_uid2guid(uid_t uid, guid_t *guidp)
{
        return(kauth_cred_cache_lookup(KI_VALID_UID, KI_VALID_GUID, &uid, guidp));
}


/*
 * kauth_cred_getguid
 *
 * Description: Fetch GUID from credential
 *
 * Parameters:  cred                            Credential to examine
 *              guidp                           Pointer to buffer for GUID
 *
 * Returns:     0                               Success
 *      kauth_cred_cache_lookup:EINVAL
 *
 * Implicit returns:
 *              *guidp                          Modified, if successful
 */
int
kauth_cred_getguid(kauth_cred_t cred, guid_t *guidp)
{
        NULLCRED_CHECK(cred);
        return(kauth_cred_uid2guid(kauth_cred_getuid(cred), guidp));
}


/*
 * kauth_cred_getguid
 *
 * Description: Fetch GUID from GID
 *
 * Parameters:  gid                             GID to examine
 *              guidp                           Pointer to buffer for GUID
 *
 * Returns:     0                               Success
 *      kauth_cred_cache_lookup:EINVAL
 *
 * Implicit returns:
 *              *guidp                          Modified, if successful
 */
int
kauth_cred_gid2guid(gid_t gid, guid_t *guidp)
{
        return(kauth_cred_cache_lookup(KI_VALID_GID, KI_VALID_GUID, &gid, guidp));
}


/*
 * kauth_cred_uid2ntsid
 *
 * Description: Fetch NTSID from UID
 *
 * Parameters:  uid                             UID to examine
 *              sidp                            Pointer to buffer for NTSID
 *
 * Returns:     0                               Success
 *      kauth_cred_cache_lookup:EINVAL
 *
 * Implicit returns:
 *              *sidp                           Modified, if successful
 */
int
kauth_cred_uid2ntsid(uid_t uid, ntsid_t *sidp)
{
        return(kauth_cred_cache_lookup(KI_VALID_UID, KI_VALID_NTSID, &uid, sidp));
}


/*
 * kauth_cred_getntsid
 *
 * Description: Fetch NTSID from credential
 *
 * Parameters:  cred                            Credential to examine
 *              sidp                            Pointer to buffer for NTSID
 *
 * Returns:     0                               Success
 *      kauth_cred_cache_lookup:EINVAL
 *
 * Implicit returns:
 *              *sidp                           Modified, if successful
 */
int
kauth_cred_getntsid(kauth_cred_t cred, ntsid_t *sidp)
{
        NULLCRED_CHECK(cred);
        return(kauth_cred_uid2ntsid(kauth_cred_getuid(cred), sidp));
}


/*
 * kauth_cred_gid2ntsid
 *
 * Description: Fetch NTSID from GID
 *
 * Parameters:  gid                             GID to examine
 *              sidp                            Pointer to buffer for NTSID
 *
 * Returns:     0                               Success
 *      kauth_cred_cache_lookup:EINVAL
 *
 * Implicit returns:
 *              *sidp                           Modified, if successful
 */
int
kauth_cred_gid2ntsid(gid_t gid, ntsid_t *sidp)
{
        return(kauth_cred_cache_lookup(KI_VALID_GID, KI_VALID_NTSID, &gid, sidp));
}


/*
 * kauth_cred_guid2ntsid
 *
 * Description: Fetch NTSID from GUID
 *
 * Parameters:  guidp                           Pointer to GUID to examine
 *              sidp                            Pointer to buffer for NTSID
 *
 * Returns:     0                               Success
 *      kauth_cred_cache_lookup:EINVAL
 *
 * Implicit returns:
 *              *sidp                           Modified, if successful
 */
int
kauth_cred_guid2ntsid(guid_t *guidp, ntsid_t *sidp)
{
        return(kauth_cred_cache_lookup(KI_VALID_GUID, KI_VALID_NTSID, guidp, sidp));
}


/*
 * kauth_cred_cache_lookup
 *
 * Description: Lookup a translation in the cache; if one is not found, and
 *              the attempt was not fatal, submit the request to the resolver
 *              instead, and wait for it to complete or be aborted.
 *
 * Parameters:  from                            Identity information we have
 *              to                              Identity information we want
 *              src                             Pointer to buffer containing
 *                                              the source identity
 *              dst                             Pointer to buffer to receive
 *                                              the target identity
 *
 * Returns:     0                               Success
 *              EINVAL                          Unknown source identity type
 */
static int
kauth_cred_cache_lookup(int from, int to, void *src, void *dst)
{
        struct kauth_identity ki;
        struct kauth_identity_extlookup el;
        int error;
        int (* expired)(struct kauth_identity *kip);

        KAUTH_DEBUG("CACHE - translate %d to %d", from, to);
        
        /*
         * Look for an existing cache entry for this association.
         * If the entry has not expired, return the cached information.
         */
        ki.ki_valid = 0;
        switch(from) {
        case KI_VALID_UID:
                error = kauth_identity_find_uid(*(uid_t *)src, &ki);
                break;
        case KI_VALID_GID:
                error = kauth_identity_find_gid(*(gid_t *)src, &ki);
                break;
        case KI_VALID_GUID:
                error = kauth_identity_find_guid((guid_t *)src, &ki);
                break;
        case KI_VALID_NTSID:
                error = kauth_identity_find_ntsid((ntsid_t *)src, &ki);
                break;
        default:
                return(EINVAL);
        }
        /* lookup failure or error */
        if (error != 0) {
                /* any other error is fatal */
                if (error != ENOENT) {
                        /* XXX bogus check - this is not possible */
                        KAUTH_DEBUG("CACHE - cache search error %d", error);
                        return(error);
                }
        } else {
                /* do we have a translation? */
                if (ki.ki_valid & to) {
                        /* found a valid cached entry, check expiry */
                        switch(to) {
                        case KI_VALID_GUID:
                                expired = kauth_identity_guid_expired;
                                break;
                        case KI_VALID_NTSID:
                                expired = kauth_identity_ntsid_expired;
                                break;
                        default:
                                switch(from) {
                                case KI_VALID_GUID:
                                        expired = kauth_identity_guid_expired;
                                        break;
                                case KI_VALID_NTSID:
                                        expired = kauth_identity_ntsid_expired;
                                        break;
                                default:
                                        expired = NULL;
                                }
                        }
                        KAUTH_DEBUG("CACHE - found matching entry with valid %d", ki.ki_valid);
                        /*
                         * If no expiry function, or not expired, we have found
                         * a hit.
                         */
                        if (!expired) {
                                KAUTH_DEBUG("CACHE - no expiry function");
                                goto found;
                        }
                        if (!expired(&ki)) {
                                KAUTH_DEBUG("CACHE - entry valid, unexpired");
                                goto found;
                        }
                        /*
                         * We leave ki_valid set here; it contains a
                         * translation but the TTL has expired.  If we can't
                         * get a result from the resolver, we will use it as
                         * a better-than nothing alternative.
                         */
                        KAUTH_DEBUG("CACHE - expired entry found");
                }
        }

        /*
         * We failed to find a cache entry; call the resolver.
         *
         * Note:        We ask for as much data as we can get.
         */
        switch(from) {
        case KI_VALID_UID:
                el.el_flags = KAUTH_EXTLOOKUP_VALID_UID;
                el.el_uid = *(uid_t *)src;
                break;
        case KI_VALID_GID:
                el.el_flags = KAUTH_EXTLOOKUP_VALID_GID;
                el.el_gid = *(gid_t *)src;
                break;
        case KI_VALID_GUID:
                el.el_flags = KAUTH_EXTLOOKUP_VALID_UGUID | KAUTH_EXTLOOKUP_VALID_GGUID;
                el.el_uguid = *(guid_t *)src;
                el.el_gguid = *(guid_t *)src;
                break;
        case KI_VALID_NTSID:
                el.el_flags = KAUTH_EXTLOOKUP_VALID_USID | KAUTH_EXTLOOKUP_VALID_GSID;
                el.el_usid = *(ntsid_t *)src;
                el.el_gsid = *(ntsid_t *)src;
                break;
        default:
                return(EINVAL);
        }
        /*
         * Here we ask for everything all at once, to avoid having to work
         * out what we really want now, or might want soon.
         *
         * Asking for SID translations when we don't know we need them right
         * now is going to cause excess work to be done if we're connected
         * to a network that thinks it can translate them.  This list needs
         * to get smaller/smarter.
         */
        el.el_flags |= KAUTH_EXTLOOKUP_WANT_UID | KAUTH_EXTLOOKUP_WANT_GID |
            KAUTH_EXTLOOKUP_WANT_UGUID | KAUTH_EXTLOOKUP_WANT_GGUID |
            KAUTH_EXTLOOKUP_WANT_USID | KAUTH_EXTLOOKUP_WANT_GSID;
        KAUTH_DEBUG("CACHE - calling resolver for %x", el.el_flags);
        error = kauth_resolver_submit(&el);
        KAUTH_DEBUG("CACHE - resolver returned %d", error);
        /* was the lookup successful? */
        if (error == 0) {
                /*
                 * Save the results from the lookup - may have other
                 * information even if we didn't get a guid.
                 */
                kauth_identity_updatecache(&el, &ki);
        }
        /*
         * Check to see if we have a valid result.
         */
        if (!error && !(ki.ki_valid & to))
                error = ENOENT;
        if (error)
                return(error);
found:
        switch(to) {
        case KI_VALID_UID:
                *(uid_t *)dst = ki.ki_uid;
                break;
        case KI_VALID_GID:
                *(gid_t *)dst = ki.ki_gid;
                break;
        case KI_VALID_GUID:
                *(guid_t *)dst = ki.ki_guid;
                break;
        case KI_VALID_NTSID:
                *(ntsid_t *)dst = ki.ki_ntsid;
                break;
        default:
                return(EINVAL);
        }
        KAUTH_DEBUG("CACHE - returned successfully");
        return(0);
}


/*
 * Group membership cache.
 *
 * XXX the linked-list implementation here needs to be optimized.
 */

struct kauth_group_membership {
        TAILQ_ENTRY(kauth_group_membership) gm_link;
        uid_t   gm_uid;         /* the identity whose membership we're recording */
        gid_t   gm_gid;         /* group of which they are a member */
        time_t  gm_expiry;      /* TTL for the membership */
        int     gm_flags;
#define KAUTH_GROUP_ISMEMBER    (1<<0)
};

TAILQ_HEAD(kauth_groups_head, kauth_group_membership) kauth_groups;
#define KAUTH_GROUPS_CACHEMAX           100     /* XXX sizing? */
static int kauth_groups_count;

static lck_mtx_t *kauth_groups_mtx;
#define KAUTH_GROUPS_LOCK()     lck_mtx_lock(kauth_groups_mtx);
#define KAUTH_GROUPS_UNLOCK()   lck_mtx_unlock(kauth_groups_mtx);

static int      kauth_groups_expired(struct kauth_group_membership *gm);
static void     kauth_groups_lru(struct kauth_group_membership *gm);
static void     kauth_groups_updatecache(struct kauth_identity_extlookup *el);


/*
 * kauth_groups_init
 *
 * Description: Initialize the groups cache
 *
 * Parameters:  (void)
 *
 * Returns:     (void)
 *
 * Notes:       Intialize the groups cache for use; the group cache is used
 *              to avoid unnecessary calls out to user space.
 *
 *              This function is called from kauth_init() in the file
 *              kern_authorization.c.
 */
void
kauth_groups_init(void)
{
        TAILQ_INIT(&kauth_groups);
        kauth_groups_mtx = lck_mtx_alloc_init(kauth_lck_grp, 0/*LCK_ATTR_NULL*/);
}


/*
 * kauth_groups_expired
 *
 * Description: Handle lazy expiration of group membership cache entries
 *
 * Parameters:  gm                              group membership entry to
 *                                              check for expiration
 *
 * Returns:     1                               Expired
 *              0                               Not expired
 */
static int
kauth_groups_expired(struct kauth_group_membership *gm)
{
        struct timeval tv;

        microuptime(&tv);
        return((gm->gm_expiry <= tv.tv_sec) ? 1 : 0);
}


/*
 * kauth_groups_lru
 *
 * Description: Promote the entry to the head of the LRU, assumes the cache
 *              is locked.
 *
 * Parameters:  kip                             group membership entry to move
 *                                              to the head of the LRU list,
 *                                              if it's not already there
 *
 * Returns:     (void)
 *
 * Notes:       This is called even if the entry has expired; typically an
 *              expired entry that's been looked up is about to be revalidated,
 *              and having it closer to the head of the LRU means finding it
 *              quickly again when the revalidation comes through.
 */
static void
kauth_groups_lru(struct kauth_group_membership *gm)
{
        if (gm != TAILQ_FIRST(&kauth_groups)) {
                TAILQ_REMOVE(&kauth_groups, gm, gm_link);
                TAILQ_INSERT_HEAD(&kauth_groups, gm, gm_link);
        }
}


/*
 * kauth_groups_updatecache
 *
 * Description: Given a lookup result, add any group cache associations that
 *              we don't currently have.
 *
 * Parameters:  elp                             External lookup result from
 *                                              user space daemon to kernel
 *              rkip                            pointer to returned kauth
 *                                              identity, or NULL
 *
 * Returns:     (void)
 */
static void
kauth_groups_updatecache(struct kauth_identity_extlookup *el)
{
        struct kauth_group_membership *gm;
        struct timeval tv;
        
        /* need a valid response if we are to cache anything */
        if ((el->el_flags &
                (KAUTH_EXTLOOKUP_VALID_UID | KAUTH_EXTLOOKUP_VALID_GID | KAUTH_EXTLOOKUP_VALID_MEMBERSHIP)) !=
            (KAUTH_EXTLOOKUP_VALID_UID | KAUTH_EXTLOOKUP_VALID_GID | KAUTH_EXTLOOKUP_VALID_MEMBERSHIP))
                return;

        microuptime(&tv);

        /*
         * Search for an existing record for this association before inserting
         * a new one; if we find one, update it instead of creating a new one
         */
        KAUTH_GROUPS_LOCK();
        TAILQ_FOREACH(gm, &kauth_groups, gm_link) {
                if ((el->el_uid == gm->gm_uid) &&
                    (el->el_gid == gm->gm_gid)) {
                        if (el->el_flags & KAUTH_EXTLOOKUP_ISMEMBER) {
                                gm->gm_flags |= KAUTH_GROUP_ISMEMBER;
                        } else {
                                gm->gm_flags &= ~KAUTH_GROUP_ISMEMBER;
                        }
                        gm->gm_expiry = el->el_member_valid + tv.tv_sec;
                        kauth_groups_lru(gm);
                        break;
                }
        }
        KAUTH_GROUPS_UNLOCK();

        /* if we found an entry to update, stop here */
        if (gm != NULL)
                return;

        /* allocate a new record */
        MALLOC(gm, struct kauth_group_membership *, sizeof(*gm), M_KAUTH, M_WAITOK);
        if (gm != NULL) {
                gm->gm_uid = el->el_uid;
                gm->gm_gid = el->el_gid;
                if (el->el_flags & KAUTH_EXTLOOKUP_ISMEMBER) {
                        gm->gm_flags |= KAUTH_GROUP_ISMEMBER;
                } else {
                        gm->gm_flags &= ~KAUTH_GROUP_ISMEMBER;
                }
                gm->gm_expiry = el->el_member_valid + tv.tv_sec;
        }               

        /*
         * Insert the new entry.  Note that it's possible to race ourselves
         * here and end up with duplicate entries in the list.  Wasteful, but
         * harmless since the first into the list will never be looked up,
         * and thus will eventually just fall off the end.
         */
        KAUTH_GROUPS_LOCK();
        TAILQ_INSERT_HEAD(&kauth_groups, gm, gm_link);
        if (kauth_groups_count++ > KAUTH_GROUPS_CACHEMAX) {
                gm = TAILQ_LAST(&kauth_groups, kauth_groups_head);
                TAILQ_REMOVE(&kauth_groups, gm, gm_link);
                kauth_groups_count--;
        } else {
                gm = NULL;
        }
        KAUTH_GROUPS_UNLOCK();

        /* free expired cache entry */
        if (gm != NULL)
                FREE(gm, M_KAUTH);
}


/*
 * Group membership KPI
 */

/*
 * kauth_cred_ismember_gid
 *
 * Description: Given a credential and a GID, determine if the GID is a member
 *              of one of the supplementary groups associated with the given
 *              credential
 *
 * Parameters:  cred                            Credential to check in
 *              gid                             GID to check for membership
 *              resultp                         Pointer to int to contain the
 *                                              result of the call
 *
 * Returns:     0                               Success
 *              ENOENT                          Could not proform lookup
 *      kauth_resolver_submit:EWOULDBLOCK
 *      kauth_resolver_submit:EINTR
 *      kauth_resolver_submit:ENOMEM
 *      kauth_resolver_submit:???               Unlikely error from user space
 *
 * Implicit returns:
 *              *resultp (modified)     1       Is member
 *                                      0       Is not member
 *
 * Notes:       This function guarantees not to modify resultp when returning
 *              an error.
 *
 *              This function effectively checkes the EGID as well, since the
 *              EGID is cr_groups[0] as an implementation detail.
 */
int
kauth_cred_ismember_gid(kauth_cred_t cred, gid_t gid, int *resultp)
{
        struct kauth_group_membership *gm;
        struct kauth_identity_extlookup el;
        int i, error;

        /*
         * Check the per-credential list of override groups.
         *
         * We can conditionalise this on cred->cr_gmuid == KAUTH_UID_NONE since
         * the cache should be used for that case.
         */
        for (i = 0; i < cred->cr_ngroups; i++) {
                if (gid == cred->cr_groups[i]) {
                        *resultp = 1;
                        return(0);
                }
        }

        /*
         * If we don't have a UID for group membership checks, the in-cred list
         * was authoritative and we can stop here.
         */
        if (cred->cr_gmuid == KAUTH_UID_NONE) {
                *resultp = 0;
                return(0);
        }
                
        
        /*
         * If the resolver hasn't checked in yet, we are early in the boot
         * phase and the local group list is complete and authoritative.
         */
        if (!kauth_resolver_registered) {
                *resultp = 0;
                return(0);
        }
        
        /* TODO: */
        /* XXX check supplementary groups */
        /* XXX check whiteout groups */
        /* XXX nesting of supplementary/whiteout groups? */

        /*
         * Check the group cache.
         */
        KAUTH_GROUPS_LOCK();
        TAILQ_FOREACH(gm, &kauth_groups, gm_link) {
                if ((gm->gm_uid == cred->cr_gmuid) && (gm->gm_gid == gid) && !kauth_groups_expired(gm)) {
                        kauth_groups_lru(gm);
                        break;
                }
        }

        /* did we find a membership entry? */
        if (gm != NULL)
                *resultp = (gm->gm_flags & KAUTH_GROUP_ISMEMBER) ? 1 : 0;
        KAUTH_GROUPS_UNLOCK();

        /* if we did, we can return now */
        if (gm != NULL)
                return(0);
        
        /* nothing in the cache, need to go to userland */
        el.el_flags = KAUTH_EXTLOOKUP_VALID_UID | KAUTH_EXTLOOKUP_VALID_GID | KAUTH_EXTLOOKUP_WANT_MEMBERSHIP;
        el.el_uid = cred->cr_gmuid;
        el.el_gid = gid;
        el.el_member_valid = 0;         /* XXX set by resolver? */
        error = kauth_resolver_submit(&el);
        if (error != 0)
                return(error);
        /* save the results from the lookup */
        kauth_groups_updatecache(&el);

        /* if we successfully ascertained membership, report */
        if (el.el_flags & KAUTH_EXTLOOKUP_VALID_MEMBERSHIP) {
                *resultp = (el.el_flags & KAUTH_EXTLOOKUP_ISMEMBER) ? 1 : 0;
                return(0);
        }

        return(ENOENT);
}


/*
 * kauth_cred_ismember_guid
 *
 * Description: Determine whether the supplied credential is a member of the
 *              group nominated by GUID.
 *
 * Parameters:  cred                            Credential to check in
 *              guidp                           Pointer to GUID whose group
 *                                              we are testing for membership
 *              resultp                         Pointer to int to contain the
 *                                              result of the call
 *
 * Returns:     0                               Success
 *      kauth_cred_guid2gid:EINVAL
 *      kauth_cred_ismember_gid:ENOENT
 *      kauth_cred_ismember_gid:EWOULDBLOCK
 *      kauth_cred_ismember_gid:EINTR
 *      kauth_cred_ismember_gid:ENOMEM
 *      kauth_cred_ismember_gid:???             Unlikely error from user space
 *
 * Implicit returns:
 *              *resultp (modified)     1       Is member
 *                                      0       Is not member
 */
int
kauth_cred_ismember_guid(kauth_cred_t cred, guid_t *guidp, int *resultp)
{
        gid_t gid;
        int error, wkg;

        error = 0;
        wkg = kauth_wellknown_guid(guidp);
        switch(wkg) {
        case KAUTH_WKG_NOBODY:
                *resultp = 0;
                break;
        case KAUTH_WKG_EVERYBODY:
                *resultp = 1;
                break;
        default:
                /* translate guid to gid */
                if ((error = kauth_cred_guid2gid(guidp, &gid)) != 0) {
                        /*
                         * If we have no guid -> gid translation, it's not a group and
                         * thus the cred can't be a member.
                         */
                        if (error == ENOENT) {
                                *resultp = 0;
                                error = 0;
                        }
                } else {
                        error = kauth_cred_ismember_gid(cred, gid, resultp);
                }
        }
        return(error);
}

/*
 * kauth_cred_gid_subset
 *
 * Description: Given two credentials, determine if all GIDs associated with 
 *              the first are also associated with the second
 *
 * Parameters:  cred1                           Credential to check for
 *              cred2                           Credential to check in
 *              resultp                         Pointer to int to contain the
 *                                              result of the call
 *
 * Returns:     0                               Success
 *              non-zero                        See kauth_cred_ismember_gid for
 *                                              error codes
 *
 * Implicit returns:
 *              *resultp (modified)     1       Is subset
 *                                      0       Is not subset
 *
 * Notes:       This function guarantees not to modify resultp when returning
 *              an error.
 */
int     
kauth_cred_gid_subset(kauth_cred_t cred1, kauth_cred_t cred2, int *resultp)
{
        int i, err, res = 1;
        gid_t gid;

        /* First, check the local list of groups */
        for (i = 0; i < cred1->cr_ngroups; i++) {
                gid = cred1->cr_groups[i];
                if ((err = kauth_cred_ismember_gid(cred2, gid, &res)) != 0) {
                        return err;
                }

                if (!res && gid != cred2->cr_rgid && gid != cred2->cr_svgid) {
                        *resultp = 0;
                        return 0;
                }
        }

        /* Check real gid */
        if ((err = kauth_cred_ismember_gid(cred2, cred1->cr_rgid, &res)) != 0) {
                return err;
        }

        if (!res && cred1->cr_rgid != cred2->cr_rgid &&
                        cred1->cr_rgid != cred2->cr_svgid) {
                *resultp = 0;
                return 0;
        }

        /* Finally, check saved gid */
        if ((err = kauth_cred_ismember_gid(cred2, cred1->cr_svgid, &res)) != 0){
                return err;
        }

        if (!res && cred1->cr_svgid != cred2->cr_rgid &&
                        cred1->cr_svgid != cred2->cr_svgid) {
                *resultp = 0;
                return 0;
        }

        *resultp = 1;
        return 0;
}


/*
 * kauth_cred_issuser
 *
 * Description: Fast replacement for issuser()
 *
 * Parameters:  cred                            Credential to check for super
 *                                              user privileges
 *
 * Returns:     0                               Not super user
 *              !0                              Is super user
 *
 * Notes:       This function uses a magic number which is not a manifest
 *              constant; this is bad practice.
 */
int
kauth_cred_issuser(kauth_cred_t cred)
{
        return(cred->cr_uid == 0);
}


/*
 * Credential KPI
 */

/* lock protecting credential hash table */
static lck_mtx_t *kauth_cred_hash_mtx;
#define KAUTH_CRED_HASH_LOCK()          lck_mtx_lock(kauth_cred_hash_mtx);
#define KAUTH_CRED_HASH_UNLOCK()        lck_mtx_unlock(kauth_cred_hash_mtx);
#if KAUTH_CRED_HASH_DEBUG
#define KAUTH_CRED_HASH_LOCK_ASSERT()   _mutex_assert(kauth_cred_hash_mtx, MA_OWNED)
#else   /* !KAUTH_CRED_HASH_DEBUG */
#define KAUTH_CRED_HASH_LOCK_ASSERT()
#endif  /* !KAUTH_CRED_HASH_DEBUG */


/*
 * kauth_cred_init
 *
 * Description: Initialize the credential hash cache
 *
 * Parameters:  (void)
 *
 * Returns:     (void)
 *
 * Notes:       Intialize the credential hash cache for use; the credential
 *              hash cache is used convert duplicate credentials into a
 *              single reference counted credential in order to save wired
 *              kernel memory.  In practice, this generally means a desktop
 *              system runs with a few tens of credentials, instead of one
 *              per process, one per thread, one per vnode cache entry, and
 *              so on.  This generally results in savings of 200K or more
 *              (potentially much more on server systems).
 *
 *              The hash cache internally has a reference on the credential
 *              for itself as a means of avoiding a reclaim race for a
 *              credential in the process of having it's last non-hash
 *              reference released.  This would otherwise result in the
 *              possibility of a freed credential that was still in uses due
 *              a race.  This use is protected by the KAUTH_CRED_HASH_LOCK.
 *
 *              On final release, the hash reference is droped, and the
 *              credential is freed back to the system.
 *
 *              This function is called from kauth_init() in the file
 *              kern_authorization.c.
 */
void
kauth_cred_init(void)
{
        int             i;
        
        kauth_cred_hash_mtx = lck_mtx_alloc_init(kauth_lck_grp, 0/*LCK_ATTR_NULL*/);
        kauth_cred_table_size = kauth_cred_primes[kauth_cred_primes_index];

        /*allocate credential hash table */
        MALLOC(kauth_cred_table_anchor, struct kauth_cred_entry_head *, 
                        (sizeof(struct kauth_cred_entry_head) * kauth_cred_table_size), 
                        M_KAUTH, M_WAITOK | M_ZERO);
        if (kauth_cred_table_anchor == NULL)
                panic("startup: kauth_cred_init");
        for (i = 0; i < kauth_cred_table_size; i++) {
                TAILQ_INIT(&kauth_cred_table_anchor[i]);
        }
}


/*
 * kauth_getuid
 *
 * Description: Get the current thread's effective UID.
 *
 * Parameters:  (void)
 *
 * Returns:     (uid_t)                         The effective UID of the
 *                                              current thread
 */
uid_t
kauth_getuid(void)
{
        return(kauth_cred_get()->cr_uid);
}


/*
 * kauth_getruid
 *
 * Description: Get the current thread's real UID.
 *
 * Parameters:  (void)
 *
 * Returns:     (uid_t)                         The real UID of the current
 *                                              thread
 */
uid_t
kauth_getruid(void)
{
        return(kauth_cred_get()->cr_ruid);
}


/*
 * kauth_getgid
 *
 * Description: Get the current thread's effective GID.
 *
 * Parameters:  (void)
 *
 * Returns:     (gid_t)                         The effective GID of the
 *                                              current thread
 */
gid_t
kauth_getgid(void)
{
        return(kauth_cred_get()->cr_groups[0]);
}


/*
 * kauth_getgid
 *
 * Description: Get the current thread's real GID.
 *
 * Parameters:  (void)
 *
 * Returns:     (gid_t)                         The real GID of the current
 *                                              thread
 */
gid_t
kauth_getrgid(void)
{
        return(kauth_cred_get()->cr_rgid);
}


/*
 * kauth_cred_get
 *
 * Description: Returns a pointer to the current thread's credential
 *
 * Parameters:  (void)
 *
 * Returns:     (kauth_cred_t)                  Pointer to the current thread's
 *                                              credential
 *
 * Notes:       This function does not take a reference; because of this, the
 *              caller MUST NOT do anything that would let the thread's
 *              credential change while using the returned value, without
 *              first explicitly taking their own reference.
 *
 *              If a caller intends to take a reference on the resulting
 *              credential pointer from calling this function, it is strongly
 *              recommended that the caller use kauth_cred_get_with_ref()
 *              instead, to protect against any future changes to the cred
 *              locking protocols; such changes could otherwise potentially
 *              introduce race windows in the callers code.
 */
kauth_cred_t
kauth_cred_get(void)
{
        struct proc *p;
        struct uthread *uthread;

        uthread = get_bsdthread_info(current_thread());
        /* sanity */
        if (uthread == NULL)
                panic("thread wants credential but has no BSD thread info");
        /*
         * We can lazy-bind credentials to threads, as long as their processes
         * have them.
         *
         * XXX If we later inline this function, the code in this block
         * XXX should probably be called out in a function.
         */
        if (uthread->uu_ucred == NOCRED) {
                if ((p = (proc_t) get_bsdtask_info(get_threadtask(current_thread()))) == NULL)
                        panic("thread wants credential but has no BSD process");
                uthread->uu_ucred = kauth_cred_proc_ref(p);
        }
        return(uthread->uu_ucred);
}


/*
 * kauth_cred_uthread_update
 *
 * Description: Given a uthread, a proc, and whether or not the proc is locked,
 *              late-bind the uthread cred to the proc cred.
 *
 * Parameters:  uthread_t                       The uthread to update
 *              proc_t                          The process to update to
 *
 * Returns:     (void)
 *
 * Notes:       This code is common code called from system call or trap entry
 *              in the case that the process thread may have been changed
 *              since the last time the thread entered the kernel.  It is
 *              generally only called with the current uthread and process as
 *              parameters.
 */
void
kauth_cred_uthread_update(uthread_t uthread, proc_t proc)
{
        if (uthread->uu_ucred != proc->p_ucred &&
            (uthread->uu_flag & UT_SETUID) == 0) {
                kauth_cred_t old = uthread->uu_ucred;
                uthread->uu_ucred = kauth_cred_proc_ref(proc);
                if (IS_VALID_CRED(old))
                        kauth_cred_unref(&old);
        }
}


/*
 * kauth_cred_get_with_ref
 *
 * Description: Takes a reference on the current thread's credential, and then
 *              returns a pointer to it to the caller.
 *
 * Parameters:  (void)
 *
 * Returns:     (kauth_cred_t)                  Pointer to the current thread's
 *                                              newly referenced credential
 *
 * Notes:       This function takes a reference on the credential before
 *              returning it to the caller.
 *
 *              It is the responsibility of the calling code to release this
 *              reference when the credential is no longer in use.
 *
 *              Since the returned reference may be a persistent reference
 *              (e.g. one cached in another data structure with a lifetime
 *              longer than the calling function), this release may be delayed
 *              until such time as the persistent reference is to be destroyed.
 *              An example of this would be the per vnode credential cache used
 *              to accelerate lookup operations.
 */
kauth_cred_t
kauth_cred_get_with_ref(void)
{
        struct proc *procp;
        struct uthread *uthread;

        uthread = get_bsdthread_info(current_thread());
        /* sanity checks */
        if (uthread == NULL)
                panic("%s - thread wants credential but has no BSD thread info", __FUNCTION__);
        if ((procp = (proc_t) get_bsdtask_info(get_threadtask(current_thread()))) == NULL)
                panic("%s - thread wants credential but has no BSD process", __FUNCTION__);

        /*
         * We can lazy-bind credentials to threads, as long as their processes
         * have them.
         *
         * XXX If we later inline this function, the code in this block
         * XXX should probably be called out in a function.
         */
        if (uthread->uu_ucred == NOCRED) {
                /* take reference for new cred in thread */
                uthread->uu_ucred = kauth_cred_proc_ref(procp);
        }
        /* take a reference for our caller */
        kauth_cred_ref(uthread->uu_ucred);
        return(uthread->uu_ucred);
}


/*
 * kauth_cred_proc_ref
 *
 * Description: Takes a reference on the current process's credential, and
 *              then returns a pointer to it to the caller.
 *
 * Parameters:  procp                           Process whose credential we
 *                                              intend to take a reference on
 *
 * Returns:     (kauth_cred_t)                  Pointer to the process's
 *                                              newly referenced credential
 *
 * Locks:       PROC_LOCK is held before taking the reference and released
 *              after the refeence is taken to protect the p_ucred field of
 *              the process referred to by procp.
 *
 * Notes:       This function takes a reference on the credential before
 *              returning it to the caller.
 *
 *              It is the responsibility of the calling code to release this
 *              reference when the credential is no longer in use.
 *
 *              Since the returned reference may be a persistent reference
 *              (e.g. one cached in another data structure with a lifetime
 *              longer than the calling function), this release may be delayed
 *              until such time as the persistent reference is to be destroyed.
 *              An example of this would be the per vnode credential cache used
 *              to accelerate lookup operations.
 */
kauth_cred_t
kauth_cred_proc_ref(proc_t procp)
{
        kauth_cred_t    cred;
        
        proc_lock(procp);
        cred = proc_ucred(procp);
        kauth_cred_ref(cred);
        proc_unlock(procp);
        return(cred);
}


/*
 * kauth_cred_alloc
 *
 * Description: Allocate a new credential
 *
 * Parameters:  (void)
 *
 * Returns:     !NULL                           Newly allocated credential
 *              NULL                            Insufficient memory
 *
 * Notes:       The newly allocated credential is zero'ed as part of the
 *              allocation process, with the exception of the reference
 *              count, which is set to 1 to indicate a single reference
 *              held by the caller.
 *
 *              Since newly allocated credentials have no external pointers
 *              referencing them, prior to making them visible in an externally
 *              visible pointer (e.g. by adding them to the credential hash
 *              cache) is the only legal time in which an existing credential
 *              can be safely iinitialized or modified directly.
 *
 *              After initialization, the caller is expected to call the
 *              function kauth_cred_add() to add the credential to the hash
 *              cache, after which time it's frozen and becomes publically
 *              visible.
 *
 *              The release protocol depends on kauth_hash_add() being called
 *              before kauth_cred_rele() (there is a diagnostic panic which
 *              will trigger if this protocol is not observed).
 *
 * XXX:         This function really ought to be static, rather than being
 *              exported as KPI, since a failure of kauth_cred_add() can only
 *              be handled by an explicit free of the credential; such frees
 *              depend on knowlegdge of the allocation method used, which is
 *              permitted to change between kernel revisions.
 *
 * XXX:         In the insufficient resource case, this code panic's rather
 *              than returning a NULL pointer; the code that calls this
 *              function needs to be audited before this can be changed.
 */
kauth_cred_t
kauth_cred_alloc(void)
{
        kauth_cred_t newcred;
        
        MALLOC_ZONE(newcred, kauth_cred_t, sizeof(*newcred), M_CRED, M_WAITOK);
        if (newcred != 0) {
                bzero(newcred, sizeof(*newcred));
                newcred->cr_ref = 1;
                /* must do this, or cred has same group membership as uid 0 */
                newcred->cr_gmuid = KAUTH_UID_NONE;
#if CRED_DIAGNOSTIC
        } else {
                panic("kauth_cred_alloc: couldn't allocate credential");
#endif          
        }

#if KAUTH_CRED_HASH_DEBUG
        kauth_cred_count++;
#endif

#if CONFIG_MACF
        mac_cred_label_init(newcred);
#endif

        return(newcred);
}


/*
 * kauth_cred_create
 *
 * Description: Look to see if we already have a known credential in the hash
 *              cache; if one is found, bump the reference count and return
 *              it.  If there are no credentials that match the given
 *              credential, then allocate a new credential.
 *
 * Parameters:  cred                            Template for credential to
 *                                              be created
 *
 * Returns:     (kauth_cred_t)                  The credential that was found
 *                                              in the hash or created
 *              NULL                            kauth_cred_add() failed, or
 *                                              there was not an egid specified
 *
 * Notes:       The gmuid is hard-defaulted to the UID specified.  Since we
 *              maintain this field, we can't expect callers to know how it
 *              needs to be set.  Callers should be prepared for this field
 *              to be overwritten.
 *
 * XXX:         This code will tight-loop if memory for a new credential is
 *              persistently unavailable; this is perhaps not the wisest way
 *              to handle this condition, but current callers do not expect
 *              a failure.
 */
kauth_cred_t
kauth_cred_create(kauth_cred_t cred)
{
        kauth_cred_t    found_cred, new_cred = NULL;

        KAUTH_CRED_HASH_LOCK_ASSERT();

        if (cred->cr_flags & CRF_NOMEMBERD)
                cred->cr_gmuid = KAUTH_UID_NONE;
        else
                cred->cr_gmuid = cred->cr_uid;

        /* Caller *must* specify at least the egid in cr_groups[0] */
        if (cred->cr_ngroups < 1)
                return(NULL);
        
        for (;;) {
                KAUTH_CRED_HASH_LOCK();
                found_cred = kauth_cred_find(cred);
                if (found_cred != NULL) {
                        /*
                         * Found an existing credential so we'll bump
                         * reference count and return
                         */
                        kauth_cred_ref(found_cred);
                        KAUTH_CRED_HASH_UNLOCK();
                        return(found_cred);
                }
                KAUTH_CRED_HASH_UNLOCK();
        
                /*
                 * No existing credential found.  Create one and add it to
                 * our hash table.
                 */
                new_cred = kauth_cred_alloc();
                if (new_cred != NULL) {
                        int             err;
                        new_cred->cr_uid = cred->cr_uid;
                        new_cred->cr_ruid = cred->cr_ruid;
                        new_cred->cr_svuid = cred->cr_svuid;
                        new_cred->cr_rgid = cred->cr_rgid;
                        new_cred->cr_svgid = cred->cr_svgid;
                        new_cred->cr_gmuid = cred->cr_gmuid;
                        new_cred->cr_ngroups = cred->cr_ngroups;        
                        bcopy(&cred->cr_groups[0], &new_cred->cr_groups[0], sizeof(new_cred->cr_groups));
                        new_cred->cr_flags = cred->cr_flags;
                        
                        KAUTH_CRED_HASH_LOCK();
                        err = kauth_cred_add(new_cred);
                        KAUTH_CRED_HASH_UNLOCK();
                        
                        /* Retry if kauth_cred_add returns non zero value */
                        if (err == 0)
                                break;
#if CONFIG_MACF
                        mac_cred_label_destroy(new_cred);
#endif
                        FREE_ZONE(new_cred, sizeof(*new_cred), M_CRED);
                        new_cred = NULL;
                }
        }

        return(new_cred);
}


/*
 * kauth_cred_setresuid
 *
 * Description: Update the given credential using the UID arguments.  The given
 *              UIDs are used to set the effective UID, real UID, saved UID,
 *              and GMUID (used for group membership checking).
 *
 * Parameters:  cred                            The original credential
 *              ruid                            The new real UID
 *              euid                            The new effective UID
 *              svuid                           The new saved UID
 *              gmuid                           KAUTH_UID_NONE -or- the new
 *                                              group membership UID
 *
 * Returns:     (kauth_cred_t)                  The updated credential
 *
 * Note:        gmuid is different in that a KAUTH_UID_NONE is a valid
 *              setting, so if you don't want it to change, pass it the
 *              previous value, explicitly.
 *
 * IMPORTANT:   This function is implemented via kauth_cred_update(), which,
 *              if it returns a credential other than the one it is passed,
 *              will have dropped the reference on the passed credential.  All
 *              callers should be aware of this, and treat this function as an
 *              unref + ref, potentially on different credentials.
 *
 *              Because of this, the caller is expected to take its own
 *              reference on the credential passed as the first parameter,
 *              and be prepared to release the reference on the credential
 *              that is returned to them, if it is not intended to be a
 *              persistent reference.
 */
kauth_cred_t
kauth_cred_setresuid(kauth_cred_t cred, uid_t ruid, uid_t euid, uid_t svuid, uid_t gmuid)
{
        struct ucred temp_cred;

        NULLCRED_CHECK(cred);

        /*
         * We don't need to do anything if the UIDs we are changing are
         * already the same as the UIDs passed in
         */
        if ((euid == KAUTH_UID_NONE || cred->cr_uid == euid) &&
            (ruid == KAUTH_UID_NONE || cred->cr_ruid == ruid) &&
            (svuid == KAUTH_UID_NONE || cred->cr_svuid == svuid) &&
            (cred->cr_gmuid == gmuid)) {
                /* no change needed */
                return(cred);
        }

        /*
         * Look up in cred hash table to see if we have a matching credential
         * with the new values; this is done by calling kauth_cred_update().
         */
        bcopy(cred, &temp_cred, sizeof(temp_cred));
        if (euid != KAUTH_UID_NONE) {
                temp_cred.cr_uid = euid;
        }
        if (ruid != KAUTH_UID_NONE) {
                temp_cred.cr_ruid = ruid;
        }
        if (svuid != KAUTH_UID_NONE) {
                temp_cred.cr_svuid = svuid;
        }

        /*
         * If we are setting the gmuid to KAUTH_UID_NONE, then we want to
         * opt out of participation in external group resolution, unless we
         * unless we explicitly opt back in later.
         */
        if ((temp_cred.cr_gmuid = gmuid) == KAUTH_UID_NONE) {
                temp_cred.cr_flags |= CRF_NOMEMBERD;
        }

        return(kauth_cred_update(cred, &temp_cred, TRUE));
}


/*
 * kauth_cred_setresgid
 *
 * Description: Update the given credential using the GID arguments.  The given
 *              GIDs are used to set the effective GID, real GID, and saved
 *              GID.
 *
 * Parameters:  cred                            The original credential
 *              rgid                            The new real GID
 *              egid                            The new effective GID
 *              svgid                           The new saved GID
 *
 * Returns:     (kauth_cred_t)                  The updated credential
 *
 * IMPORTANT:   This function is implemented via kauth_cred_update(), which,
 *              if it returns a credential other than the one it is passed,
 *              will have dropped the reference on the passed credential.  All
 *              callers should be aware of this, and treat this function as an
 *              unref + ref, potentially on different credentials.
 *
 *              Because of this, the caller is expected to take its own
 *              reference on the credential passed as the first parameter,
 *              and be prepared to release the reference on the credential
 *              that is returned to them, if it is not intended to be a
 *              persistent reference.
 */
kauth_cred_t
kauth_cred_setresgid(kauth_cred_t cred, gid_t rgid, gid_t egid, gid_t svgid)
{
        struct ucred    temp_cred;

        NULLCRED_CHECK(cred);
        DEBUG_CRED_ENTER("kauth_cred_setresgid %p %d %d %d\n", cred, rgid, egid, svgid);

        /*
         * We don't need to do anything if the given GID are already the 
         * same as the GIDs in the credential.
         */
        if (cred->cr_groups[0] == egid &&
            cred->cr_rgid == rgid &&
            cred->cr_svgid == svgid) {
                /* no change needed */
                return(cred);
        }

        /*
         * Look up in cred hash table to see if we have a matching credential
         * with the new values; this is done by calling kauth_cred_update().
         */
        bcopy(cred, &temp_cred, sizeof(temp_cred));
        if (egid != KAUTH_GID_NONE) {
                /* displacing a supplementary group opts us out of memberd */
                if (kauth_cred_change_egid(&temp_cred, egid)) {
                        DEBUG_CRED_CHANGE("displaced!\n");
                        temp_cred.cr_flags |= CRF_NOMEMBERD;
                        temp_cred.cr_gmuid = KAUTH_UID_NONE;
                } else {
                        DEBUG_CRED_CHANGE("not displaced\n");
                }
        }
        if (rgid != KAUTH_GID_NONE) {
                temp_cred.cr_rgid = rgid;
        }
        if (svgid != KAUTH_GID_NONE) {
                temp_cred.cr_svgid = svgid;
        }

        return(kauth_cred_update(cred, &temp_cred, TRUE));
}


/*
 * Update the given credential with the given groups.  We only allocate a new 
 *      credential when the given gid actually results in changes to the existing 
 *      credential.
 *      The gmuid argument supplies a new uid (or KAUTH_UID_NONE to opt out)
 *      which will be used for group membership checking.
 */
/*
 * kauth_cred_setgroups
 *
 * Description: Update the given credential using the provide supplementary
 *              group list and group membership UID
 *
 * Parameters:  cred                            The original credential
 *              groups                          Pointer to gid_t array which
 *                                              contains the new group list
 *              groupcount                      The cound of valid groups which
 *                                              are contained in 'groups'
 *              gmuid                           KAUTH_UID_NONE -or- the new
 *                                              group membership UID
 *
 * Returns:     (kauth_cred_t)                  The updated credential
 *
 * Note:        gmuid is different in that a KAUTH_UID_NONE is a valid
 *              setting, so if you don't want it to change, pass it the
 *              previous value, explicitly.
 *
 * IMPORTANT:   This function is implemented via kauth_cred_update(), which,
 *              if it returns a credential other than the one it is passed,
 *              will have dropped the reference on the passed credential.  All
 *              callers should be aware of this, and treat this function as an
 *              unref + ref, potentially on different credentials.
 *
 *              Because of this, the caller is expected to take its own
 *              reference on the credential passed as the first parameter,
 *              and be prepared to release the reference on the credential
 *              that is returned to them, if it is not intended to be a
 *              persistent reference.
 *
 * XXX:         Changes are determined in ordinal order - if the caller pasess
 *              in the same groups list that is already present in the
 *              credential, but the members are in a different order, even if
 *              the EGID is not modified (i.e. cr_groups[0] is the same), it
 *              is considered a modification to the credential, and a new
 *              credential is created.
 *
 *              This should perhaps be better optimized, but it is considered
 *              to be the caller's problem.
 */
kauth_cred_t
kauth_cred_setgroups(kauth_cred_t cred, gid_t *groups, int groupcount, uid_t gmuid)
{
        int             i;
        struct ucred temp_cred;

        NULLCRED_CHECK(cred);

        /*
         * We don't need to do anything if the given list of groups does not
         * change.
         */
        if ((cred->cr_gmuid == gmuid) && (cred->cr_ngroups == groupcount)) {
                for (i = 0; i < groupcount; i++) {
                        if (cred->cr_groups[i] != groups[i])
                                break;
                }
                if (i == groupcount) {
                        /* no change needed */
                        return(cred);
                }
        }

        /*
         * Look up in cred hash table to see if we have a matching credential
         * with new values.  If we are setting or clearing the gmuid, then
         * update the cr_flags, since clearing it is sticky.  This permits an
         * opt-out of memberd processing using setgroups(), and an opt-in
         * using initgroups().  This is required for POSIX conformance.
         */
        bcopy(cred, &temp_cred, sizeof(temp_cred));
        temp_cred.cr_ngroups = groupcount;
        bcopy(groups, temp_cred.cr_groups, sizeof(temp_cred.cr_groups));
        temp_cred.cr_gmuid = gmuid;
        if (gmuid == KAUTH_UID_NONE)
                temp_cred.cr_flags |= CRF_NOMEMBERD;
        else
                temp_cred.cr_flags &= ~CRF_NOMEMBERD;

        return(kauth_cred_update(cred, &temp_cred, TRUE));
}


/*
 * kauth_cred_setuidgid
 *
 * Description: Update the given credential using the UID and GID arguments.
 *              The given UID is used to set the effective UID, real UID, and
 *              saved UID.  The given GID is used to set the effective GID,
 *              real GID, and saved GID.
 *
 * Parameters:  cred                            The original credential
 *              uid                             The new UID to use
 *              gid                             The new GID to use
 *
 * Returns:     (kauth_cred_t)                  The updated credential
 *
 * Notes:       We set the gmuid to uid if the credential we are inheriting
 *              from has not opted out of memberd participation; otherwise
 *              we set it to KAUTH_UID_NONE
 *
 *              This code is only ever called from the per-thread credential
 *              code path in the "set per thread credential" case; and in
 *              posix_spawn() in the case that the POSIX_SPAWN_RESETIDS
 *              flag is set.
 *
 * IMPORTANT:   This function is implemented via kauth_cred_update(), which,
 *              if it returns a credential other than the one it is passed,
 *              will have dropped the reference on the passed credential.  All
 *              callers should be aware of this, and treat this function as an
 *              unref + ref, potentially on different credentials.
 *
 *              Because of this, the caller is expected to take its own
 *              reference on the credential passed as the first parameter,
 *              and be prepared to release the reference on the credential
 *              that is returned to them, if it is not intended to be a
 *              persistent reference.
 */
kauth_cred_t
kauth_cred_setuidgid(kauth_cred_t cred, uid_t uid, gid_t gid)
{
        struct ucred temp_cred;

        NULLCRED_CHECK(cred);

        /*
         * We don't need to do anything if the effective, real and saved
         * user IDs are already the same as the user ID passed into us.
         */
        if (cred->cr_uid == uid && cred->cr_ruid == uid && cred->cr_svuid == uid &&
                cred->cr_groups[0] == gid && cred->cr_rgid == gid && cred->cr_svgid == gid) {
                /* no change needed */
                return(cred);
        }

        /*
         * Look up in cred hash table to see if we have a matching credential
         * with the new values.
         */
        bzero(&temp_cred, sizeof(temp_cred));
        temp_cred.cr_uid = uid;
        temp_cred.cr_ruid = uid;
        temp_cred.cr_svuid = uid;
        /* inherit the opt-out of memberd */
        if (cred->cr_flags & CRF_NOMEMBERD) {
                temp_cred.cr_gmuid = KAUTH_UID_NONE;
                temp_cred.cr_flags |= CRF_NOMEMBERD;
        } else {
                temp_cred.cr_gmuid = uid;
                temp_cred.cr_flags &= ~CRF_NOMEMBERD;
        }
        temp_cred.cr_ngroups = 1;
        /* displacing a supplementary group opts us out of memberd */
        if (kauth_cred_change_egid(&temp_cred, gid)) {
                temp_cred.cr_gmuid = KAUTH_UID_NONE;
                temp_cred.cr_flags |= CRF_NOMEMBERD;
        }
        temp_cred.cr_rgid = gid;
        temp_cred.cr_svgid = gid;
#if CONFIG_MACF
        temp_cred.cr_label = cred->cr_label;
#endif

        return(kauth_cred_update(cred, &temp_cred, TRUE));
}


/*
 * kauth_cred_setsvuidgid
 *
 * Description: Function used by execve to set the saved uid and gid values
 *              for suid/sgid programs
 *
 * Parameters:  cred                            The credential to update
 *              uid                             The saved uid to set
 *              gid                             The saved gid to set
 *
 * Returns:     (kauth_cred_t)                  The updated credential
 *
 * IMPORTANT:   This function is implemented via kauth_cred_update(), which,
 *              if it returns a credential other than the one it is passed,
 *              will have dropped the reference on the passed credential.  All
 *              callers should be aware of this, and treat this function as an
 *              unref + ref, potentially on different credentials.
 *
 *              Because of this, the caller is expected to take its own
 *              reference on the credential passed as the first parameter,
 *              and be prepared to release the reference on the credential
 *              that is returned to them, if it is not intended to be a
 *              persistent reference.
 */
kauth_cred_t
kauth_cred_setsvuidgid(kauth_cred_t cred, uid_t uid, gid_t gid)
{
        struct ucred temp_cred;

        NULLCRED_CHECK(cred);
        DEBUG_CRED_ENTER("kauth_cred_setsvuidgid: %p u%d->%d g%d->%d\n", cred, cred->cr_svuid, uid, cred->cr_svgid, gid);

        /*
         * We don't need to do anything if the effective, real and saved
         * uids are already the same as the uid provided.  This check is
         * likely insufficient.
         */
        if (cred->cr_svuid == uid && cred->cr_svgid == gid) {
                /* no change needed */
                return(cred);
        }
        DEBUG_CRED_CHANGE("kauth_cred_setsvuidgid: cred change\n");

        /* look up in cred hash table to see if we have a matching credential
         * with new values.
         */
        bcopy(cred, &temp_cred, sizeof(temp_cred));
        temp_cred.cr_svuid = uid;
        temp_cred.cr_svgid = gid;

        return(kauth_cred_update(cred, &temp_cred, TRUE));
}


/*
 * kauth_cred_setauditinfo
 * 
 * Description: Update the given credential using the given auditinfo_t.
 *
 * Parameters:  cred                            The original credential
 *              auditinfo_p                     Pointer to ne audit information
 *
 * Returns:     (kauth_cred_t)                  The updated credential
 *
 * IMPORTANT:   This function is implemented via kauth_cred_update(), which,
 *              if it returns a credential other than the one it is passed,
 *              will have dropped the reference on the passed credential.  All
 *              callers should be aware of this, and treat this function as an
 *              unref + ref, potentially on different credentials.
 *
 *              Because of this, the caller is expected to take its own
 *              reference on the credential passed as the first parameter,
 *              and be prepared to release the reference on the credential
 *              that is returned to them, if it is not intended to be a
 *              persistent reference.
 */
kauth_cred_t
kauth_cred_setauditinfo(kauth_cred_t cred, auditinfo_t *auditinfo_p)
{
        struct ucred temp_cred;

        NULLCRED_CHECK(cred);

        /*
         * We don't need to do anything if the audit info is already the
         * same as the audit info in the credential provided.
         */
        if (bcmp(&cred->cr_au, auditinfo_p, sizeof(cred->cr_au)) == 0) {
                /* no change needed */
                return(cred);
        }

        bcopy(cred, &temp_cred, sizeof(temp_cred));
        bcopy(auditinfo_p, &temp_cred.cr_au, sizeof(temp_cred.cr_au));

        return(kauth_cred_update(cred, &temp_cred, FALSE));
}

#if CONFIG_MACF
/*
 * kauth_cred_label_update
 * 
 * Description: Update the MAC label associated with a credential
 *
 * Parameters:  cred                            The original credential
 *              label                           The MAC label to set
 *
 * Returns:     (kauth_cred_t)                  The updated credential
 *
 * IMPORTANT:   This function is implemented via kauth_cred_update(), which,
 *              if it returns a credential other than the one it is passed,
 *              will have dropped the reference on the passed credential.  All
 *              callers should be aware of this, and treat this function as an
 *              unref + ref, potentially on different credentials.
 *
 *              Because of this, the caller is expected to take its own
 *              reference on the credential passed as the first parameter,
 *              and be prepared to release the reference on the credential
 *              that is returned to them, if it is not intended to be a
 *              persistent reference.
 */
kauth_cred_t
kauth_cred_label_update(kauth_cred_t cred, struct label *label)
{
        kauth_cred_t newcred;
        struct ucred temp_cred;

        bcopy(cred, &temp_cred, sizeof(temp_cred));

        mac_cred_label_init(&temp_cred);
        mac_cred_label_associate(cred, &temp_cred);
        mac_cred_label_update(&temp_cred, label);

        newcred = kauth_cred_update(cred, &temp_cred, TRUE);
        mac_cred_label_destroy(&temp_cred);
        return (newcred);
}

/*
 * kauth_cred_label_update_execve
 * 
 * Description: Update the MAC label associated with a credential as
 *              part of exec
 *
 * Parameters:  cred                            The original credential
 *              vp                              The exec vnode
 *              scriptl                         The script MAC label
 *              execl                           The executable MAC label
 *
 * Returns:     (kauth_cred_t)                  The updated credential
 *
 * IMPORTANT:   This function is implemented via kauth_cred_update(), which,
 *              if it returns a credential other than the one it is passed,
 *              will have dropped the reference on the passed credential.  All
 *              callers should be aware of this, and treat this function as an
 *              unref + ref, potentially on different credentials.
 *
 *              Because of this, the caller is expected to take its own
 *              reference on the credential passed as the first parameter,
 *              and be prepared to release the reference on the credential
 *              that is returned to them, if it is not intended to be a
 *              persistent reference.
 */
static
kauth_cred_t
kauth_cred_label_update_execve(kauth_cred_t cred, vfs_context_t ctx,
        struct vnode *vp, struct label *scriptl, struct label *execl)
{
        kauth_cred_t newcred;
        struct ucred temp_cred;

        bcopy(cred, &temp_cred, sizeof(temp_cred));

        mac_cred_label_init(&temp_cred);
        mac_cred_label_associate(cred, &temp_cred);
        mac_cred_label_update_execve(ctx, &temp_cred, 
                                     vp, scriptl, execl);

        newcred = kauth_cred_update(cred, &temp_cred, TRUE);
        mac_cred_label_destroy(&temp_cred);
        return (newcred);
}

/*
 *  kauth_proc_label_update
 *
 * Description:  Update the label inside the credential associated with the process.
 *
 * Parameters:  p                       The process to modify
 *                              label           The label to place in the process credential
 *
 * Notes:               The credential associated with the process may change as a result
 *                              of this call.  The caller should not assume the process reference to
 *                              the old credential still exists.
 */
int kauth_proc_label_update(struct proc *p, struct label *label)
{
        kauth_cred_t my_cred, my_new_cred;

        my_cred = kauth_cred_proc_ref(p);

        DEBUG_CRED_ENTER("kauth_proc_label_update: %p\n", my_cred);

        /* get current credential and take a reference while we muck with it */
        for (;;) {

                /* 
                 * Set the credential with new info.  If there is no change,
                 * we get back the same credential we passed in; if there is
                 * a change, we drop the reference on the credential we
                 * passed in.  The subsequent compare is safe, because it is
                 * a pointer compare rather than a contents compare.
                 */
                my_new_cred = kauth_cred_label_update(my_cred, label);
                if (my_cred != my_new_cred) {

                        DEBUG_CRED_CHANGE("kauth_proc_setlabel_unlocked CH(%d): %p/0x%08x -> %p/0x%08x\n", p->p_pid, my_cred, my_cred->cr_flags, my_new_cred, my_new_cred->cr_flags);

                        proc_lock(p);
                        /*
                         * We need to protect for a race where another thread
                         * also changed the credential after we took our
                         * reference.  If p_ucred has changed then we should
                         * restart this again with the new cred.
                         */
                        if (p->p_ucred != my_cred) {
                                proc_unlock(p);
                                kauth_cred_unref(&my_new_cred);
                                my_cred = kauth_cred_proc_ref(p);
                                /* try again */
                                continue;
                        }
                        p->p_ucred = my_new_cred;
                        mac_proc_set_enforce(p, MAC_ALL_ENFORCE);
                        proc_unlock(p);
                }
                break;
        }
        /* Drop old proc reference or our extra reference */
        kauth_cred_unref(&my_cred);
        
        return (0);
}

/*
 *  kauth_proc_label_update_execve
 *
 * Description: Update the label inside the credential associated with the
 *              process as part of a transitioning execve.  The label will
 *              be updated by the policies as part of this processing, not
 *              provided up front.
 *
 * Parameters:  p                       The process to modify
 *              ctx                     The context of the exec
 *              vp                      The vnode being exec'ed
 *              scriptl                 The script MAC label
 *              execl                   The executable MAC label
 *
 * Notes:       The credential associated with the process WILL change as a
 *              result of this call.  The caller should not assume the process
 *              reference to the old credential still exists.
 */
int kauth_proc_label_update_execve(struct proc *p, vfs_context_t ctx,
        struct vnode *vp, struct label *scriptl, struct label *execl)
{
        kauth_cred_t my_cred, my_new_cred;

        my_cred = kauth_cred_proc_ref(p);

        DEBUG_CRED_ENTER("kauth_proc_label_update_execve: %p\n", my_cred);

        /* get current credential and take a reference while we muck with it */
        for (;;) {

                /* 
                 * Set the credential with new info.  If there is no change,
                 * we get back the same credential we passed in; if there is
                 * a change, we drop the reference on the credential we
                 * passed in.  The subsequent compare is safe, because it is
                 * a pointer compare rather than a contents compare.
                 */
                my_new_cred = kauth_cred_label_update_execve(my_cred, ctx, vp, scriptl, execl);
                if (my_cred != my_new_cred) {

                        DEBUG_CRED_CHANGE("kauth_proc_label_update_execve_unlocked CH(%d): %p/0x%08x -> %p/0x%08x\n", p->p_pid, my_cred, my_cred->cr_flags, my_new_cred, my_new_cred->cr_flags);

                        proc_lock(p);
                        /*
                         * We need to protect for a race where another thread
                         * also changed the credential after we took our
                         * reference.  If p_ucred has changed then we should
                         * restart this again with the new cred.
                         */
                        if (p->p_ucred != my_cred) {
                                proc_unlock(p);
                                kauth_cred_unref(&my_new_cred);
                                my_cred = kauth_cred_proc_ref(p);
                                /* try again */
                                continue;
                        }
                        p->p_ucred = my_new_cred;
                        mac_proc_set_enforce(p, MAC_ALL_ENFORCE);
                        proc_unlock(p);
                }
                break;
        }
        /* Drop old proc reference or our extra reference */
        kauth_cred_unref(&my_cred);
        
        return (0);
}

#if 1
/*
 * for temporary binary compatibility
 */
kauth_cred_t    kauth_cred_setlabel(kauth_cred_t cred, struct label *label);
kauth_cred_t
kauth_cred_setlabel(kauth_cred_t cred, struct label *label)
{
        return kauth_cred_label_update(cred, label);
}

int kauth_proc_setlabel(struct proc *p, struct label *label);
int
kauth_proc_setlabel(struct proc *p, struct label *label)
{
        return kauth_proc_label_update(p, label);
}
#endif

#else

/* this is a temp hack to cover us when MACF is not built in a kernel configuration. 
 * Since we cannot build our export lists based on the kernel configuration we need
 * to define a stub. 
 */
kauth_cred_t
kauth_cred_label_update(__unused kauth_cred_t cred, __unused void *label)
{
        return(NULL);
}

int
kauth_proc_label_update(__unused struct proc *p, __unused void *label)
{
        return (0);
}

#if 1
/*
 * for temporary binary compatibility
 */
kauth_cred_t    kauth_cred_setlabel(kauth_cred_t cred, void *label);
kauth_cred_t
kauth_cred_setlabel(__unused kauth_cred_t cred, __unused void *label)
{
        return NULL;
}

int kauth_proc_setlabel(struct proc *p, void *label);
int
kauth_proc_setlabel(__unused struct proc *p, __unused void *label)
{
        return (0);
}
#endif
#endif

/*
 * kauth_cred_ref
 *
 * Description: Add a reference to the passed credential
 *
 * Parameters:  cred                            The credential to reference
 *
 * Returns:     (void)
 *
 * Notes:       This function adds a reference to the provided credential;
 *              the existing reference on the credential is assumed to be
 *              held stable over this operation by taking the appropriate
 *              lock to protect the pointer from which it is being referenced,
 *              if necessary (e.g. the proc lock is held over the call if the
 *              credential being referenced is from p_ucred, the vnode lock
 *              if from the per vnode name cache cred cache, and so on).
 *
 *              This is safe from the kauth_cred_unref() path, since an atomic
 *              add is used, and the unref path specifically checks to see that
 *              the value has not been changed to add a reference between the
 *              time the credential is unreferenced by another pointer and the
 *              time it is unreferenced from the cred hash cache.
 */
void
kauth_cred_ref(kauth_cred_t cred)
{
        int             old_value;
        
        NULLCRED_CHECK(cred);

        // XXX SInt32 not safe for an LP64 kernel
        old_value = OSAddAtomic(1, (SInt32 *)&cred->cr_ref);

        if (old_value < 1)
                panic("kauth_cred_ref: trying to take a reference on a cred with no references");

#if 0 // use this to watch a specific credential
        if ( is_target_cred( cred ) != 0 ) {
                get_backtrace( );
        }
#endif
                
        return;
}


/*
 * kauth_cred_unref_hashlocked
 *
 * Description: release a credential reference; when the last reference is
 *              released, the credential will be freed.
 *
 * Parameters:  credp                           Pointer to address containing
 *                                              credential to be freed
 *
 * Returns:     (void)
 *
 * Implicit returns:
 *              *credp                          Set to NOCRED
 *
 * Notes:       This function assumes the credential hash lock is held.
 *
 *              This function is internal use only, since the hash lock is
 *              scoped to this compilation unit.
 *
 *              This function destroys the contents of the pointer passed by
 *              the caller to prevent the caller accidently attempting to
 *              release a given reference twice in error.
 *
 *              The last reference is considered to be released when a release
 *              of a credential of a reference count of 2 occurs; this is an
 *              intended effect, to take into accout the reference held by
 *              the credential hash, which is released at the same time.
 */
static void
kauth_cred_unref_hashlocked(kauth_cred_t *credp)
{
        int             old_value;

        KAUTH_CRED_HASH_LOCK_ASSERT();
        NULLCRED_CHECK(*credp);

        // XXX SInt32 not safe for an LP64 kernel
        old_value = OSAddAtomic(-1, (SInt32 *)&(*credp)->cr_ref);

#if DIAGNOSTIC
        if (old_value == 0)
                panic("%s:0x%08x kauth_cred_unref_hashlocked: dropping a reference on a cred with no references", current_proc()->p_comm, *credp);
        if (old_value == 1)
                panic("%s:0x%08x kauth_cred_unref_hashlocked: dropping a reference on a cred with no hash entry", current_proc()->p_comm, *credp);
#endif

#if 0 // use this to watch a specific credential
        if ( is_target_cred( *credp ) != 0 ) {
                get_backtrace( );
        }
#endif

        /*
         * If the old_value is 2, then we have just released the last external
         * reference to this credential
         */
        if (old_value < 3) {
                /* The last absolute reference is our credential hash table */
                kauth_cred_remove(*credp);
        }
        *credp = NOCRED;
}


/*
 * kauth_cred_unref
 *
 * Description: Release a credential reference while holding the credential
 *              hash lock; when the last reference is released, the credential
 *              will be freed.
 *
 * Parameters:  credp                           Pointer to address containing
 *                                              credential to be freed
 *
 * Returns:     (void)
 *
 * Implicit returns:
 *              *credp                          Set to NOCRED
 *
 * Notes:       See kauth_cred_unref_hashlocked() for more information.
 *
 */
void
kauth_cred_unref(kauth_cred_t *credp)
{
        KAUTH_CRED_HASH_LOCK();
        kauth_cred_unref_hashlocked(credp);
        KAUTH_CRED_HASH_UNLOCK();
}


/*
 * kauth_cred_rele
 *
 * Description: release a credential reference; when the last reference is
 *              released, the credential will be freed
 *
 * Parameters:  cred                            Credential to release
 *
 * Returns:     (void)
 *
 * DEPRECATED:  This interface is obsolete due to a failure to clear out the
 *              clear the pointer in the caller to avoid multiple releases of
 *              the same credential.  The currently recommended interface is
 *              kauth_cred_unref().
 */
void
kauth_cred_rele(kauth_cred_t cred)
{
        kauth_cred_unref(&cred);
}


/*
 * kauth_cred_dup
 *
 * Description: Duplicate a credential via alloc and copy; the new credential
 *              has only it's own
 *
 * Parameters:  cred                            The credential to duplicate
 *
 * Returns:     (kauth_cred_t)                  The duplicate credential
 *
 * Notes:       The typical value to calling this routine is if you are going
 *              to modify an existing credential, and expect to need a new one
 *              from the hash cache.
 *
 *              This should probably not be used in the majority of cases;
 *              if you are using it instead of kauth_cred_create(), you are
 *              likely making a mistake.
 *
 *              The newly allocated credential is copied as part of the
 *              allocation process, with the exception of the reference
 *              count, which is set to 1 to indicate a single reference
 *              held by the caller.
 *
 *              Since newly allocated credentials have no external pointers
 *              referencing them, prior to making them visible in an externally
 *              visible pointer (e.g. by adding them to the credential hash
 *              cache) is the only legal time in which an existing credential
 *              can be safely iinitialized or modified directly.
 *
 *              After initialization, the caller is expected to call the
 *              function kauth_cred_add() to add the credential to the hash
 *              cache, after which time it's frozen and becomes publically
 *              visible.
 *
 *              The release protocol depends on kauth_hash_add() being called
 *              before kauth_cred_rele() (there is a diagnostic panic which
 *              will trigger if this protocol is not observed).
 *
 */
kauth_cred_t
kauth_cred_dup(kauth_cred_t cred)
{
        kauth_cred_t newcred;
#if CONFIG_MACF
        struct label *temp_label;
#endif
        
#if CRED_DIAGNOSTIC
        if (cred == NOCRED || cred == FSCRED)
                panic("kauth_cred_dup: bad credential");
#endif
        newcred = kauth_cred_alloc();
        if (newcred != NULL) {
#if CONFIG_MACF
                temp_label = newcred->cr_label;
#endif
                bcopy(cred, newcred, sizeof(*newcred));
#if CONFIG_MACF
                newcred->cr_label = temp_label;
                mac_cred_label_associate(cred, newcred);
#endif
                newcred->cr_ref = 1;
        }
        return(newcred);
}

/*
 * kauth_cred_copy_real
 *
 * Description: Returns a credential based on the passed credential but which
 *              reflects the real rather than effective UID and GID.
 *
 * Parameters:  cred                            The credential from which to
 *                                              derive the new credential
 *
 * Returns:     (kauth_cred_t)                  The copied credential
 *
 * IMPORTANT:   This function DOES NOT utilize kauth_cred_update(); as a
 *              result, the caller is responsible for dropping BOTH the
 *              additional reference on the passed cred (if any), and the
 *              credential returned by this function.  The drop should be
 *              via the satnadr kauth_cred_unref() KPI.
 */
kauth_cred_t
kauth_cred_copy_real(kauth_cred_t cred)
{
        kauth_cred_t newcred = NULL, found_cred;
        struct ucred temp_cred;

        /* if the credential is already 'real', just take a reference */
        if ((cred->cr_ruid == cred->cr_uid) &&
            (cred->cr_rgid == cred->cr_gid)) {
                kauth_cred_ref(cred);
                return(cred);
        }

        /*
         * Look up in cred hash table to see if we have a matching credential
         * with the new values.
         */
        bcopy(cred, &temp_cred, sizeof(temp_cred));
        temp_cred.cr_uid = cred->cr_ruid;
        /* displacing a supplementary group opts us out of memberd */
        if (kauth_cred_change_egid(&temp_cred, cred->cr_rgid)) {
                temp_cred.cr_flags |= CRF_NOMEMBERD;
                temp_cred.cr_gmuid = KAUTH_UID_NONE;
        }
        /*
         * If the cred is not opted out, make sure we are using the r/euid
         * for group checks
         */
        if (temp_cred.cr_gmuid != KAUTH_UID_NONE)
                temp_cred.cr_gmuid = cred->cr_ruid;

        for (;;) {
                int             err;
                
                KAUTH_CRED_HASH_LOCK();
                found_cred = kauth_cred_find(&temp_cred);
                if (found_cred == cred) {
                        /* same cred so just bail */
                        KAUTH_CRED_HASH_UNLOCK();
                        return(cred); 
                }
                if (found_cred != NULL) {
                        /*
                         * Found a match so we bump reference count on new
                         * one.  We leave the old one alone.
                         */
                        kauth_cred_ref(found_cred);
                        KAUTH_CRED_HASH_UNLOCK();
                        return(found_cred);
                }
        
                /*
                 * Must allocate a new credential, copy in old credential
                 * data and update the real user and group IDs.
                 */
                newcred = kauth_cred_dup(&temp_cred);
                err = kauth_cred_add(newcred);
                KAUTH_CRED_HASH_UNLOCK();

                /* Retry if kauth_cred_add() fails */
                if (err == 0)
                        break;
#if CONFIG_MACF
                mac_cred_label_destroy(newcred);
#endif
                FREE_ZONE(newcred, sizeof(*newcred), M_CRED);
                newcred = NULL;
        }
        
        return(newcred);
}


/*
 * kauth_cred_update
 *
 * Description: Common code to update a credential
 *
 * Parameters:  old_cred                        Reference counted credential
 *                                              to update
 *              model_cred                      Non-reference counted model
 *                                              credential to apply to the
 *                                              credential to be updated
 *              retain_auditinfo                Flag as to whether or not the
 *                                              audit information should be
 *                                              copied from the old_cred into
 *                                              the model_cred
 *
 * Returns:     (kauth_cred_t)                  The updated credential
 *
 * IMPORTANT:   This function will potentially return a credential other than
 *              the one it is passed, and if so, it will have dropped the
 *              reference on the passed credential.  All callers should be
 *              aware of this, and treat this function as an unref + ref,
 *              potentially on different credentials.
 *
 *              Because of this, the caller is expected to take its own
 *              reference on the credential passed as the first parameter,
 *              and be prepared to release the reference on the credential
 *              that is returned to them, if it is not intended to be a
 *              persistent reference.
 */
static kauth_cred_t
kauth_cred_update(kauth_cred_t old_cred, kauth_cred_t model_cred,
        boolean_t retain_auditinfo)
{       
        kauth_cred_t found_cred, new_cred = NULL;
        
        /*
         * Make sure we carry the auditinfo forward to the new credential
         * unless we are actually updating the auditinfo.
         */
        if (retain_auditinfo)
                bcopy(&old_cred->cr_au, &model_cred->cr_au, sizeof(model_cred->cr_au));
        
        for (;;) {
                int             err;

                KAUTH_CRED_HASH_LOCK();
                found_cred = kauth_cred_find(model_cred);
                if (found_cred == old_cred) {
                        /* same cred so just bail */
                        KAUTH_CRED_HASH_UNLOCK();
                        return(old_cred); 
                }
                if (found_cred != NULL) {
                        DEBUG_CRED_CHANGE("kauth_cred_update(cache hit): %p -> %p\n", old_cred, found_cred);
                        /*
                         * Found a match so we bump reference count on new
                         * one and decrement reference count on the old one.
                         */
                        kauth_cred_ref(found_cred);
                        kauth_cred_unref_hashlocked(&old_cred);
                        KAUTH_CRED_HASH_UNLOCK();
                        return(found_cred);
                }
        
                /*
                 * Must allocate a new credential using the model.  also
                 * adds the new credential to the credential hash table.
                 */
                new_cred = kauth_cred_dup(model_cred);
                err = kauth_cred_add(new_cred);
                KAUTH_CRED_HASH_UNLOCK();

                /* retry if kauth_cred_add returns non zero value */
                if (err == 0)
                        break;
#if CONFIG_MACF
                mac_cred_label_destroy(new_cred);
#endif
                FREE_ZONE(new_cred, sizeof(*new_cred), M_CRED);
                new_cred = NULL;
        }

        DEBUG_CRED_CHANGE("kauth_cred_update(cache miss): %p -> %p\n", old_cred, new_cred);
        kauth_cred_unref(&old_cred);
        return(new_cred);
}


/*
 * kauth_cred_add
 *
 * Description: Add the given credential to our credential hash table and
 *              take an additional reference to account for our use of the
 *              credential in the hash table
 *
 * Parameters:  new_cred                        Credential to insert into cred
 *                                              hash cache
 *
 * Returns:     0                               Success
 *              -1                              Hash insertion failed: caller
 *                                              should retry
 *
 * Locks:       Caller is expected to hold KAUTH_CRED_HASH_LOCK
 *
 * Notes:       The 'new_cred' MUST NOT already be in the cred hash cache
 */
static int
kauth_cred_add(kauth_cred_t new_cred)
{
        u_long                  hash_key;

        KAUTH_CRED_HASH_LOCK_ASSERT();

        hash_key = kauth_cred_get_hashkey(new_cred);
        hash_key %= kauth_cred_table_size;

        /* race fix - there is a window where another matching credential 
         * could have been inserted between the time this one was created and we
         * got the hash lock.  If we find a match return an error and have the 
         * the caller retry.
         */
        if (kauth_cred_find(new_cred) != NULL) {
                return(-1);
        }
        
        /* take a reference for our use in credential hash table */ 
        kauth_cred_ref(new_cred);

        /* insert the credential into the hash table */
        TAILQ_INSERT_HEAD(&kauth_cred_table_anchor[hash_key], new_cred, cr_link);
        
        return(0);
}


/* 
 * kauth_cred_remove
 *
 * Description: Remove the given credential from our credential hash table
 *
 * Parameters:  cred                            Credential to remove from cred
 *                                              hash cache
 *
 * Returns:     (void)
 *
 * Locks:       Caller is expected to hold KAUTH_CRED_HASH_LOCK
 *
 * Notes:       The check for the reference increment after entry is generally
 *              agree to be safe, since we use atomic operations, and the
 *              following code occurs with the hash lock held; in theory, this
 *              protects us from the 2->1 reference that gets us here.
 */
static void
kauth_cred_remove(kauth_cred_t cred)
{
        u_long                  hash_key;
        kauth_cred_t    found_cred;

        hash_key = kauth_cred_get_hashkey(cred);
        hash_key %= kauth_cred_table_size;

        /* Avoid race */
        if (cred->cr_ref < 1)
                panic("cred reference underflow");
        if (cred->cr_ref > 1)
                return;         /* someone else got a ref */
                
        /* Find cred in the credential hash table */
        TAILQ_FOREACH(found_cred, &kauth_cred_table_anchor[hash_key], cr_link) {
                if (found_cred == cred) {
                        /* found a match, remove it from the hash table */
                        TAILQ_REMOVE(&kauth_cred_table_anchor[hash_key], found_cred, cr_link);
#if CONFIG_MACF
                        mac_cred_label_destroy(cred);
#endif
                        cred->cr_ref = 0;
                        FREE_ZONE(cred, sizeof(*cred), M_CRED);
#if KAUTH_CRED_HASH_DEBUG
                        kauth_cred_count--;
#endif
                        return;
                }
        }

        /* Did not find a match... this should not happen! XXX Make panic? */
        printf("%s:%d - %s - %s - did not find a match for %p\n", __FILE__, __LINE__, __FUNCTION__, current_proc()->p_comm, cred);
        return;
}


/* 
 * kauth_cred_find
 *
 * Description: Using the given credential data, look for a match in our
 *              credential hash table
 *
 * Parameters:  cred                            Credential to lookup in cred
 *                                              hash cache
 *
 * Returns:     NULL                            Not found
 *              !NULL                           Matching cedential already in
 *                                              cred hash cache
 *
 * Locks:       Caller is expected to hold KAUTH_CRED_HASH_LOCK
 */
kauth_cred_t
kauth_cred_find(kauth_cred_t cred)
{
        u_long                  hash_key;
        kauth_cred_t    found_cred;

        KAUTH_CRED_HASH_LOCK_ASSERT();

#if KAUTH_CRED_HASH_DEBUG
        static int              test_count = 0; 

        test_count++;
        if ((test_count % 200) == 0) {
                kauth_cred_hash_print();
        }
#endif

        hash_key = kauth_cred_get_hashkey(cred);
        hash_key %= kauth_cred_table_size;

        /* Find cred in the credential hash table */
        TAILQ_FOREACH(found_cred, &kauth_cred_table_anchor[hash_key], cr_link) {
                boolean_t match;

                /*
                 * don't worry about the label unless the flags in
                 * either credential tell us to.
                 */
                if ((found_cred->cr_flags & CRF_MAC_ENFORCE) != 0 ||
                    (cred->cr_flags & CRF_MAC_ENFORCE) != 0) {
                        /* include the label pointer in the compare */
                        match = (bcmp(&found_cred->cr_uid, &cred->cr_uid,
                                 (sizeof(struct ucred) -
                                  offsetof(struct ucred, cr_uid))) == 0);
                } else {
                        /* flags have to match, but skip the label in bcmp */
                        match = (found_cred->cr_flags == cred->cr_flags &&
                                 bcmp(&found_cred->cr_uid, &cred->cr_uid,
                                      (offsetof(struct ucred, cr_label) -
                                       offsetof(struct ucred, cr_uid))) == 0);
                }
                if (match) {
                        /* found a match */
                        return(found_cred);
                }
        }
        /* No match found */

        return(NULL);
}


/*
 * kauth_cred_hash
 *
 * Description: Generates a hash key using data that makes up a credential;
 *              based on ElfHash
 *
 * Parameters:  datap                           Pointer to data to hash
 *              data_len                        Count of bytes to hash
 *              start_key                       Start key value
 *
 * Returns:     (u_long)                        Returned hash key
 */
static inline u_long
kauth_cred_hash(const uint8_t *datap, int data_len, u_long start_key)
{
        u_long  hash_key = start_key;
        u_long  temp;

        while (data_len > 0) {
                hash_key = (hash_key << 4) + *datap++;
                temp = hash_key & 0xF0000000;
                if (temp) {
                        hash_key ^= temp >> 24;
                }
                hash_key &= ~temp;
                data_len--;
        }
        return(hash_key);
}


/*
 * kauth_cred_get_hashkey
 *
 * Description: Generate a hash key using data that makes up a credential;
 *              based on ElfHash.  We hash on the entire credential data,
 *              not including the ref count or the TAILQ, which are mutable;
 *              everything else isn't.
 *
 *              We also avoid the label (if the flag is not set saying the
 *              label is actually enforced).
 *
 * Parameters:  cred                            Credential for which hash is
 *                                              desired
 *
 * Returns:     (u_long)                        Returned hash key
 */
static u_long
kauth_cred_get_hashkey(kauth_cred_t cred)
{
        u_long  hash_key = 0;
        
        hash_key = kauth_cred_hash((uint8_t *)&cred->cr_uid, 
                        ((cred->cr_flags & CRF_MAC_ENFORCE) ? 
                            sizeof(struct ucred) : offsetof(struct ucred, cr_label)) -
                            offsetof(struct ucred, cr_uid),
                        hash_key);
        return(hash_key);
}


#if KAUTH_CRED_HASH_DEBUG
/*
 * kauth_cred_hash_print
 *
 * Description: Print out cred hash cache table information for debugging
 *              purposes, including the credential contents
 *
 * Parameters:  (void)
 *
 * Returns:     (void)
 *
 * Implicit returns:    Results in console output
 */
static void
kauth_cred_hash_print(void) 
{
        int                     i, j;
        kauth_cred_t    found_cred;
                
        printf("\n\t kauth credential hash table statistics - current cred count %d \n", kauth_cred_count);
        /* count slot hits, misses, collisions, and max depth */
        for (i = 0; i < kauth_cred_table_size; i++) {
                printf("[%02d] ", i);
                j = 0;
                TAILQ_FOREACH(found_cred, &kauth_cred_table_anchor[i], cr_link) {
                        if (j > 0) {
                                printf("---- ");
                        }
                        j++;
                        kauth_cred_print(found_cred);
                        printf("\n");
                }
                if (j == 0) {
                        printf("NOCRED \n");
                }
        }
}
#endif  /* KAUTH_CRED_HASH_DEBUG */


#if (defined(KAUTH_CRED_HASH_DEBUG) && (KAUTH_CRED_HASH_DEBUG != 0)) || defined(DEBUG_CRED)
/*
 * kauth_cred_print
 *
 * Description: Print out an individual credential's contents for debugging
 *              purposes
 *
 * Parameters:  cred                            The credential to print out
 *
 * Returns:     (void)
 *
 * Implicit returns:    Results in console output
 */
void
kauth_cred_print(kauth_cred_t cred) 
{
        int     i;

        printf("%p - refs %lu flags 0x%08x uids e%d r%d sv%d gm%d ", cred, cred->cr_ref, cred->cr_flags, cred->cr_uid, cred->cr_ruid, cred->cr_svuid, cred->cr_gmuid);
        printf("group count %d gids ", cred->cr_ngroups);
        for (i = 0; i < NGROUPS; i++) {
                if (i == 0)
                        printf("e");
                printf("%d ", cred->cr_groups[i]);
        }
        printf("r%d sv%d ", cred->cr_rgid, cred->cr_svgid);
        printf("auditinfo %d %d %d %d %d %d\n", 
                cred->cr_au.ai_auid, cred->cr_au.ai_mask.am_success, cred->cr_au.ai_mask.am_failure, 
                cred->cr_au.ai_termid.port, cred->cr_au.ai_termid.machine, cred->cr_au.ai_asid);
}

int is_target_cred( kauth_cred_t the_cred )
{
        if ( the_cred->cr_uid != 0 ) 
                return( 0 );
        if ( the_cred->cr_ruid != 0 ) 
                return( 0 );
        if ( the_cred->cr_svuid != 0 ) 
                return( 0 );
        if ( the_cred->cr_ngroups != 11 ) 
                return( 0 );
        if ( the_cred->cr_groups[0] != 11 ) 
                return( 0 );
        if ( the_cred->cr_groups[1] != 81 ) 
                return( 0 );
        if ( the_cred->cr_groups[2] != 63947 ) 
                return( 0 );
        if ( the_cred->cr_groups[3] != 80288 ) 
                return( 0 );
        if ( the_cred->cr_groups[4] != 89006 ) 
                return( 0 );
        if ( the_cred->cr_groups[5] != 52173 ) 
                return( 0 );
        if ( the_cred->cr_groups[6] != 84524 ) 
                return( 0 );
        if ( the_cred->cr_groups[7] != 79 ) 
                return( 0 );
        if ( the_cred->cr_groups[8] != 80292 ) 
                return( 0 );
        if ( the_cred->cr_groups[9] != 80 ) 
                return( 0 );
        if ( the_cred->cr_groups[10] != 90824 ) 
                return( 0 );
        if ( the_cred->cr_rgid != 11 ) 
                return( 0 );
        if ( the_cred->cr_svgid != 11 ) 
                return( 0 );
        if ( the_cred->cr_gmuid != 3475 ) 
                return( 0 );
        if ( the_cred->cr_au.ai_auid != 3475 ) 
                return( 0 );
/*
        if ( the_cred->cr_au.ai_mask.am_success != 0 ) 
                return( 0 );
        if ( the_cred->cr_au.ai_mask.am_failure != 0 ) 
                return( 0 );
        if ( the_cred->cr_au.ai_termid.port != 0 ) 
                return( 0 );
        if ( the_cred->cr_au.ai_termid.machine != 0 ) 
                return( 0 );
        if ( the_cred->cr_au.ai_asid != 0 ) 
                return( 0 );
        if ( the_cred->cr_flags != 0 ) 
                return( 0 );
*/
        return( -1 ); // found target cred
}

void get_backtrace( void )
{
        int                             my_slot;
        void *                  my_stack[ MAX_STACK_DEPTH ];
        int                             i, my_depth;
        
        if ( cred_debug_buf_p == NULL ) {
                MALLOC(cred_debug_buf_p, cred_debug_buffer *, sizeof(*cred_debug_buf_p), M_KAUTH, M_WAITOK);
                bzero(cred_debug_buf_p, sizeof(*cred_debug_buf_p));
        }       

        if ( cred_debug_buf_p->next_slot > (MAX_CRED_BUFFER_SLOTS - 1) ) {
                /* buffer is full */
                return;
        }
        
        my_depth = OSBacktrace(&my_stack[0], MAX_STACK_DEPTH);
        if ( my_depth == 0 ) {
                printf("%s - OSBacktrace failed \n", __FUNCTION__);
                return;
        }
        
        /* fill new backtrace */
        my_slot = cred_debug_buf_p->next_slot;
        cred_debug_buf_p->next_slot++;
        cred_debug_buf_p->stack_buffer[ my_slot ].depth = my_depth;
        for ( i = 0; i < my_depth; i++ ) {
                cred_debug_buf_p->stack_buffer[ my_slot ].stack[ i ] = my_stack[ i ];
        }

        return;
}


/* subset of struct ucred for use in sysctl_dump_creds */
struct debug_ucred {
        void    *credp;
        u_long  cr_ref;                         /* reference count */
        uid_t   cr_uid;                         /* effective user id */
        uid_t   cr_ruid;                        /* real user id */
        uid_t   cr_svuid;                       /* saved user id */
        short   cr_ngroups;                     /* number of groups in advisory list */
        gid_t   cr_groups[NGROUPS];     /* advisory group list */
        gid_t   cr_rgid;                        /* real group id */
        gid_t   cr_svgid;                       /* saved group id */
        uid_t   cr_gmuid;                       /* UID for group membership purposes */
        struct auditinfo cr_au;         /* user auditing data */
        void    *cr_label;                      /* MACF label */
        int             cr_flags;                       /* flags on credential */
};
typedef struct debug_ucred debug_ucred;

SYSCTL_PROC(_kern, OID_AUTO, dump_creds, CTLFLAG_RD,
    NULL, 0, sysctl_dump_creds, "S,debug_ucred", "List of credentials in the cred hash");

/*      accessed by:      
 *      err = sysctlbyname( "kern.dump_creds", bufp, &len, NULL, 0 );
 */

static int
sysctl_dump_creds( __unused struct sysctl_oid *oidp, __unused void *arg1, __unused int arg2, struct sysctl_req *req )
{
        int                     i, j, counter = 0;
        int                             error;
        size_t                  space;
        kauth_cred_t    found_cred;
        debug_ucred *   cred_listp;
        debug_ucred *   nextp;

        /* This is a readonly node. */
        if (req->newptr != USER_ADDR_NULL)
                return (EPERM);

        /* calculate space needed */
        for (i = 0; i < kauth_cred_table_size; i++) {
                TAILQ_FOREACH(found_cred, &kauth_cred_table_anchor[i], cr_link) {
                        counter++;
                }
        }

        /* they are querying us so just return the space required. */
        if (req->oldptr == USER_ADDR_NULL) {
                counter += 10; // add in some padding;
                req->oldidx = counter * sizeof(debug_ucred);
                return 0;
        }

        MALLOC( cred_listp, debug_ucred *, req->oldlen, M_TEMP, M_WAITOK );
        if ( cred_listp == NULL ) {
                return (ENOMEM);
        }
        
        /* fill in creds to send back */
        nextp = cred_listp;
        space = 0;
        for (i = 0; i < kauth_cred_table_size; i++) {
                TAILQ_FOREACH(found_cred, &kauth_cred_table_anchor[i], cr_link) {
                        nextp->credp = found_cred;
                        nextp->cr_ref = found_cred->cr_ref;
                        nextp->cr_uid = found_cred->cr_uid;
                        nextp->cr_ruid = found_cred->cr_ruid;
                        nextp->cr_svuid = found_cred->cr_svuid;
                        nextp->cr_ngroups = found_cred->cr_ngroups;
                        for ( j = 0; j < nextp->cr_ngroups; j++ ) {
                                nextp->cr_groups[ j ] = found_cred->cr_groups[ j ];
                        }
                        nextp->cr_rgid = found_cred->cr_rgid;
                        nextp->cr_svgid = found_cred->cr_svgid;
                        nextp->cr_gmuid = found_cred->cr_gmuid;
                        nextp->cr_au.ai_auid = found_cred->cr_au.ai_auid;
                        nextp->cr_au.ai_mask.am_success = found_cred->cr_au.ai_mask.am_success;
                        nextp->cr_au.ai_mask.am_failure = found_cred->cr_au.ai_mask.am_failure;
                        nextp->cr_au.ai_termid.port = found_cred->cr_au.ai_termid.port;
                        nextp->cr_au.ai_termid.machine = found_cred->cr_au.ai_termid.machine;
                        nextp->cr_au.ai_asid = found_cred->cr_au.ai_asid;
                        nextp->cr_label = found_cred->cr_label;
                        nextp->cr_flags = found_cred->cr_flags;
                        nextp++;
                        space += sizeof(debug_ucred);
                        if ( space > req->oldlen ) {
                                FREE(cred_listp, M_TEMP);
                                return (ENOMEM);
                        }
                }
        }
        req->oldlen = space;
        error = SYSCTL_OUT(req, cred_listp, req->oldlen);
        FREE(cred_listp, M_TEMP);
        return (error);
}


SYSCTL_PROC(_kern, OID_AUTO, cred_bt, CTLFLAG_RD,
    NULL, 0, sysctl_dump_cred_backtraces, "S,cred_debug_buffer", "dump credential backtrace");

/*      accessed by:      
 *      err = sysctlbyname( "kern.cred_bt", bufp, &len, NULL, 0 );
 */

static int
sysctl_dump_cred_backtraces( __unused struct sysctl_oid *oidp, __unused void *arg1, __unused int arg2, struct sysctl_req *req )
{
        int                     i, j;
        int                             error;
        size_t                  space;
        cred_debug_buffer *     bt_bufp;
        cred_backtrace *        nextp;

        /* This is a readonly node. */
        if (req->newptr != USER_ADDR_NULL)
                return (EPERM);

        if ( cred_debug_buf_p == NULL ) {
                return (EAGAIN);
        }

        /* calculate space needed */
        space = sizeof( cred_debug_buf_p->next_slot );
        space += (sizeof( cred_backtrace ) * cred_debug_buf_p->next_slot);

        /* they are querying us so just return the space required. */
        if (req->oldptr == USER_ADDR_NULL) {
                req->oldidx = space;
                return 0;
        }

        if ( space > req->oldlen ) {
                return (ENOMEM);
        }

        MALLOC( bt_bufp, cred_debug_buffer *, req->oldlen, M_TEMP, M_WAITOK );
        if ( bt_bufp == NULL ) {
                return (ENOMEM);
        }
        
        /* fill in backtrace info to send back */
        bt_bufp->next_slot = cred_debug_buf_p->next_slot;
        space = sizeof(bt_bufp->next_slot);
        
        nextp = &bt_bufp->stack_buffer[ 0 ];
        for (i = 0; i < cred_debug_buf_p->next_slot; i++) {
                nextp->depth = cred_debug_buf_p->stack_buffer[ i ].depth;
                for ( j = 0; j < nextp->depth; j++ ) {
                        nextp->stack[ j ] = cred_debug_buf_p->stack_buffer[ i ].stack[ j ];
                }
                space += sizeof(*nextp);
                nextp++;
        }
        req->oldlen = space;
        error = SYSCTL_OUT(req, bt_bufp, req->oldlen);
        FREE(bt_bufp, M_TEMP);
        return (error);
}

#endif  /* KAUTH_CRED_HASH_DEBUG || DEBUG_CRED */